CPLEX-OPL:新边界为 0，添加新约束时无结果

Question

我尝试在 CPLEX 12.8.0 上运行 MILP (OPL(。将此附件添加到模型并运行后，引擎日志如图所示，并且没有其他重用。如何解决此问题？谢谢。

EQ11 : // 1TruckPourAtSameCustomer&Time;
forall(c in customer, m in delivery : m > 1)
sum(k in truck, j in truck)
EP[k][j]*x[c][m-1][k][j] <=
sum(k in truck, j in truck)
SP[k][j]*x[c][m][k][j];

发动机日志

! ----------------------------------------------------------------------------
! Minimization problem - 94 variables, 143 constraints
! Presolve      : 44 extractables eliminated
! TimeLimit            = 600
! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
!  . Log search space  : 2,101.1 (before), 2,101.1 (after)
!  . Memory usage      : 521.5 kB (before), 521.5 kB (after)
! Using parallel search with 16 workers.
! ----------------------------------------------------------------------------
!          Best Branches  Non-fixed    W       Branch decision
0         94                 -
+ New bound is 0

编辑。

这是我的模型，预拌混凝土消遣问题。它类似于作业车间调度问题。

using CP;

execute
{
cp.param.timelimit=600;
}

int c =...;
int m =...;
int k =...;
int j =...;
range customer     =   1..c;
range delivery     =   1..m;
range truck        =   1..k;
range job          =   1..j;

float Cost_Dist=...;
float Cost_Delay=...;
float Wash_T=...;
float Velocity=...;
float Pro_Rate=...;

float Demand[customer]=...;
float ETW[customer]=...;
float LTW[customer]=...;
float Unload_W[customer]=...;
float Unload_R[customer]=...;
float Dist_C[customer]=...;
float CAP[truck]=...;
float Access[customer][truck]=...;

dvar int+ Delay[customer];
dvar int+ Travel_C[customer];
dvar int+ SL[truck][job];
dvar int+ Dep_P[truck][job];
dvar int+ Arr_C[truck][job];
dvar int+ SP[truck][job];
dvar int+ EP[truck][job];
dvar int+ Arr_P[truck][job];
dvar int+ LQ[truck][job];
dvar int+ LT[truck][job];
dvar int+ UT[truck][job];
dvar boolean x[customer][delivery][truck][job];


//////////////////////////////////////////////////////////////////////;

minimize   (Cost_Dist*2*(sum(c in customer, m in delivery, k in truck, j in job)
Dist_C[c]*x[c][m][k][j]))+
(Cost_Delay* (sum(c in customer)
Delay[c]));


//////////////////////////////////////////////////////////////////////;

subject to { 
EQ2 : //AssignmentCM
forall(c in customer, m in delivery)
sum(k in truck, j in job)
x[c][m][k][j] <= 1 ;

EQ3 : //AssignmentKJ
forall(k in truck, j in job)
sum(c in customer, m in delivery)
x[c][m][k][j] <= 1 ;

EQ4 : //Access
forall(c in customer, m in delivery,k in truck, j in job)
x[c][m][k][j] <= Access[c][k];

EQ5 : //PrecedenceCM
forall(c in customer, m in delivery : m > 1)
sum(k in truck, j in job)
x[c][m][k][j] <=
sum(k in truck, j in job)
x[c][m-1][k][j];

EQ6 : //PrecedenceKJ
forall(k in truck, j in job : j > 1)
sum(c in customer, m in delivery)
x[c][m][k][j] <=
sum(c in customer, m in delivery)
x[c][m][k][j-1];

EQ7 : //Demand <= Supply
forall(c in customer)
Demand[c] <= 
sum(m in delivery,k in truck, j in job)
LQ[k][j]*x[c][m][k][j];

EQ8 : //Load <= Capacity
forall(k in truck, j in job)
LQ[k][j] <= CAP[k];

EQ9 : //EarliestTimeWindow
forall(c in customer, m in delivery : m == 1)
ETW[c] <= 
sum(k in truck, j in job)
SP[k][j]*x[c][m][k][j];
EQ11 : // 1TruckPourAtSameCustomerTime;
forall(c in customer, m in delivery : m > 1)
sum(k in truck, j in truck)
EP[k][j]*x[c][m-1][k][j] <=
sum(k in truck, j in truck)
SP[k][j]*x[c][m][k][j];

//-----------------TruckTimelineConstraints-----------------//


EQ14 : //StartLoad
forall(k in truck, j in job : j > 1)
SL[k][j] >= Arr_P[k][j-1];
EQ15 : //DepartPlant
forall(k in truck, j in job)
Dep_P[k][j] == SL[k][j]+LT[k][j];

EQ16 : //ArriveCustomer
forall(k in truck, j in job)
Arr_C[k][j] == Dep_P[k][j]+
sum(c in customer, m in delivery)
Travel_C[c]*x[c][m][k][j];

EQ17 : //StartPour
forall(k in truck, j in job)
SP[k][j] == Arr_C[k][j]+
sum(c in customer, m in delivery)
Unload_W[c]*x[c][m][k][j];

EQ18 : //EndPour
forall(k in truck, j in job)
EP[k][j] == SP[k][j]+UT[k][j];

EQ19 : //ArrivePlant
forall(k in truck, j in job)
Arr_P[k][j] == EP[k][j]+
sum(c in customer, m in delivery)
Travel_C[c]*x[c][m][k][j];


//-----------------VariableCalculations-----------------//


EQ21 : //TravelTimeP-C
forall(c in customer)
Travel_C[c] == ceil(Dist_C[c]/Velocity);

EQ22 : //ConcreteLoadingTime
forall(k in truck, j in job)
LT[k][j] == ceil(LQ[k][j]/Pro_Rate);

EQ23 : //ConcreteUnloadingTime
forall(k in truck, j in job)
UT[k][j] == ceil(
sum(c in customer, m in delivery)
(LQ[k][j]/Unload_R[c]*x[c][m][k][j]));

EQ24 : //Delay
forall(c in customer, m in delivery)
Delay[c] == maxl(0,ceil(sum(k in truck, j in job)
(Arr_C[k][j]-(LTW[c]*x[c][m][k][j]))));


} 

和数据。

c=2;
m=3;
k=2;
j=3;

Cost_Dist=10;
Cost_Delay=10;
Wash_T=5;
Velocity=1.3;
Pro_Rate=1;

Demand=[15 15];
ETW=[60 90];
LTW=[300 600];
Unload_W=[5 5];
Unload_R=[0.5 0.5];
Dist_C=[5 10];
CAP=[5 5];
Access=
[[1 1] 
[1 1]];

Answer 1

这里的问题是约束编程中有时称为传播乒乓球(循环(。约束传播从变量域中删除不可行的值。假设约束 c1 从 x 的域中删除值 1。由于 x 的域已更改，因此与 x 相关的其他约束将再次传播。让我们假设其中一个约束 c2 从 x 的域中删除值 2。这将触发增益约束 c1，该约束删除值 3，然后 c2 删除值 4，依此类推。根据 x 域的大小，c1 和 c2 之间的乒乓球可能会很长。

当然，求解器会尝试在预求解过程中识别乒乓球的常见来源。但是他们通常无法删除所有这些。

有两种方法可以处理乒乓球：

1. 减小域的大小。乒乓球比赛结束得更快。在您的示例中，我试图将域限制为 0..10000，然后立即找到目标值为 900 的最佳解决方案。即不要只使用"dvar int+"，而是指定较小的域。
2. 确定循环中的约束(可能不仅仅是 2 个约束(并重新建模此部分。例如，添加一个冗余约束，该约束在一个步骤中传播原始约束在循环中传播的内容。

方法2.适用于专家，它需要相当多的求解器和对模型的洞察力。