时间戳

首页 > 解决方案 > CPLEX-OPL：新界限为 0，添加新约束时无结果

cplex - CPLEX-OPL：新界限为 0，添加新约束时无结果

问题描述

我尝试在 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]];

标签： cplexoplcp-optimizer

解决方案

这里的问题是它有时在约束编程中称为传播乒乓（循环）。约束传播从变量域中删除不可行的值。假设约束 c1 从 x 的域中删除值 1。因为 x 的域发生了变化，所以对 x 感兴趣的其他约束再次传播。让我们假设其中一个约束 c2 从 x 的域中删除值 2。这会触发增益约束 c1 删除值 3，然后 c2 删除值 4 等。根据 x 域的大小，c1 和 c2 之间的这个乒乓球可能很长。

当然，求解器会在预求解过程中尝试识别常见的乒乓源。但他们一般不能全部删除。

处理乒乓球有两种方法：

  1. 减小域的大小。那会更快地结束乒乓球。在您的示例中，我尝试将域限制为 0..10000，然后立即找到目标值为 900 的最佳解决方案。即不要只使用“dvar int+”，而是指定更小的域。
  2. 识别循环中的约束（它可能不仅仅是 2 个约束）并重塑这部分。例如，添加一个冗余约束，该约束在一个步骤中传播原始约束在循环中传播的内容。

方法 2. 虽然适用于专家，但它需要对求解器有相当的了解并深入了解您的模型。

推荐阅读