CODEWITHSUNDEEP
cplexoplcp-optimizer
Natdanai I.
Natdanai I.

Reputation: 49

CPLEX-OPL: New bound is 0 and no result when adding a new constraint

I tried to run a MILP (OPL) on CPLEX 12.8.0. After add this constaint to the model and run, engine log as showed and get no other reuslt. how do i fix this problem ? Thank you.

 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];

Engine Log

 ! ----------------------------------------------------------------------------
 ! 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

EDITED.

This is my model, ready-mixed concrete dispacthing problem. It is similar to job shop scheduling problem.

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]))));





}

and data.

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]];

Upvotes: 0

Views: 203

Answers (1)

Petr Vil&#237;m
Petr Vil&#237;m

Reputation: 175

The problem here is what it sometimes called propagation ping-pong (loop) in constraint programming. Constraint propagation removes infeasible values from domains of variables. Suppose that constraint c1 removes value 1 from domain of x. Because domain of x has changed, other constraints interested in x are propagated again. And lets suppose that one of those constraints, c2, removes value 2 from domain of x. That triggers gain constraint c1 which removes value 3, then c2 removes value 4 etc. Depending on the size of the domain of x this ping-pong between c1 and c2 could be very long.

Of course, solvers try to recognize common sources of ping-pong during presolve. But they cannot remove all of them in general.

There are two ways to deal with a ping-pong:

  1. Decrease size of domains. That ends ping-pong sooner. In your example, I tried to limit the domains to 0..10000 and then optimal solution with objective value 900 is found immediately. I.e. don't use only "dvar int+" but specify smaller domains.
  2. Identify constraints that are in the loop (it could be more than just 2 constraints) and remodel this part. For example add a redundant constraint that propagates in one step what the original constraints propagated in the loop.

Approach 2. is for experts though, it requires quite a knowledge of the solver and insight into your model.

Upvotes: 2

Related Questions