Hi everyone,
I faced a ridiculous bug I can't figure out. I have 5 series of constraints in my model for which I've written both classes and equivalent codes in the main function. For 4 constraints the result is exactly the same no matter I use the first one or the latter. However, for the 5th constraint, the solution is surprisingly different and violating most of the other constraints and thus returning an infeasible solution. I've been checking everything but I could not understand where the bug source is and fix it? Would you help me out with this, please?
Here are the objects and the one in the main function:
The constraint class:
#include<ilcp/cp.h>
#include<ilcp/cpext.h>
#include<ilconcert/ilomodel.h>
IloInt nbCustomers=5;
IloInt nbVehicles=2;
class FixingDepotsI: public IlcConstraintI {
IlcIntVarArray successor;
public:
FixingDepotsI(IloCP cp, IlcIntVarArray _successor);
void propagate();
void post();
};
FixingDepotsI::FixingDepotsI(IloCP cp, IlcIntVarArray _successor): IlcConstraintI(cp), successor(_successor)
{
}
void FixingDepotsI::propagate(){
IloInt k;
for (k=0; k < nbVehicles; k++){
successornbCustomers+nbVehicles+k.setValue(nbCustomers+k);
}
}
void FixingDepotsI::post(){
for (IloInt k=0; k<nbVehicles; k++)
successor[k].whenValue(this);
}
ILOCPCONSTRAINTWRAPPER1(Ilo_FixingDepots, cp, IloIntVarArray, successor)
{
use(cp, successor);
return new (cp.getHeap()) FixingDepotsI(cp, cp.getIntVarArray(successor));
}
The equivalent code in the main model:
for (IloInt k=0; k < nbVehicles; k++){
model.add(successornbCustomers+nbVehicles+k==nbCustomers+k);
}
Thanks!
Topic
This topic has been locked.
6 replies
Latest Post
 20130214T14:53:50Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic Constraints as objects VS Constraints in the main model
20130206T23:50:09Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20130214T14:53:50Z at 20130214T14:53:50Z by SystemAdmin

ACCEPTED ANSWER
Re: Constraints as objects VS Constraints in the main model
20130207T15:09:15Z in response to SystemAdminHello,
Do you have a small but complete and compilable code that shows the problem?
On the code you attached, it is not easy to see what happens. Some things I noticed, but that may be ok as I do not know the semantics of your variables and constraints :
 the array successor is accessed with indexes that I do not really understand (nbCustomers+nbVehicles+k) but why not
 the code in the post function of the constraint is not really useful as the propagate will do all the propagation work at initial propagation
Also, which version leads to an infeasible problem: the one using your FixingDepot constraint or the one using predefined constraints in the model?
Do you use the automatic search of CP Optimizer in both cases?
Philippe
ACCEPTED ANSWER
Re: Constraints as objects VS Constraints in the main model
20130207T16:29:20Z in response to SystemAdminThanks for the reply. These are answers:
***Do you have a small but complete and compilable code that shows the problem?
 Here it is:
int main(int argc, const char* argv[]){
IloEnv env;
try{
IloModel model(env);
IloInt i, j;
const char* filename = "/home/.../VRPTW.data";
if (argc > 1)
{filename = argv[1];
std::cout << argv[1];}
std::ifstream file(filename);
if (!file){
env.out() << "usage: " << argv[0] << " <file>" << std::endl;
throw FileError();
}
IloIntArray servicetime(env), tlb(env), tub(env);
IloArray<IloIntArray> distance(env);
IloIntArray demand;
IloInt nbCustomers;
IloInt nbVehicles;
// Data retrieving%
file >> nbCustomers;
file >> nbVehicles;
IloInt nbDepotsAndCustomers=2*nbVehicles+nbCustomers;
//Variables%
IloIntVarArray successor(env, nbDepotsAndCustomers, 0, nbDepotsAndCustomers1);
IloIntVarArray VisitTime(env, nbDepotsAndCustomers, 0, 4000);
IloIntVarArray vehicle(env, nbDepotsAndCustomers, 0, nbVehicles1);
//Constraints%
//model.add(successor);
model.add(IloAllDiff(env, successor));
//connecting final depots to their corresponding initial depots
//model.add(Ilo_FixingDepots(env, successor));
for (IloInt k=0; k < nbVehicles; k++){
model.add(successornbCustomers+nbVehicles+k==nbCustomers+k);
}
//Subtour Elimination
model.add(Ilo_NoSubtour(env, successor));
//Time windows
//model.add(Ilo_TimeWindows(env, VisitTime, tlb,tub));
for (i=0; i < nbDepotsAndCustomers; i++){
model.add(VisitTime[i]<=tub[i]);
model.add(VisitTime[i]>=tlb[i]);
}
//Precedence
for (i=0; i < nbCustomers+nbVehicles; i++) {
model.add(VisitTime[i] <= VisitTime[successori]distance[i][successori]servicetime[i]);
}
//Assigning vehicles to routes (initial depots)
for (i=0; i < nbVehicles; i++){
model.add(vehiclenbCustomers+i==i);
model.add(vehiclenbCustomers+nbVehicles+i==i);
}
//nodes on the same route traversed by the same vehicle
for (i=0; i < nbCustomers; i++){
model.add(vehicle[successori]==vehicle[i]);
}
//Objective function%
IloIntExpr obj = IloIntExpr(env,0);
for (i = 0; i < nbDepotsAndCustomers1; i++)
obj += distance[i][successori];
model.add(IloMinimize(env, obj));
IloCP cp(model);
cp.out()<< model ;
cp.solve())
}
catch(IloException& e){
env.out() << " error: " << e.getMessage() << std::endl;
}
env.end();
return 0;
}
***On the code you attached, it is not easy to see what happens. Some things I noticed, but that may be ok as I do not know the semantics of your variables and constraints : the array successor is accessed with indexes that I do not really understand (nbCustomers+nbVehicles+k) but why not
 nbCustomers and nbVehicles are constants already declared and showing the number of customers and the number of vehicles, respectively. nbCustomers+nbVehicles+k (k:0,1,..,nbVehicles) stands for the final depots in the VRP (to each vehicle or route are associated to dummy depots, an initial one, and a destination one). And thus, nbCustomers+k (k:0,1,..,nbVehicles) shows the initial depot of every vehicle. The constraint simply connects the two corresponding initial and final depots, and in fact states that every vehicle should be directed to the corresponding initial depot after traversing its route.
 the code in the post function of the constraint is not really useful as the propagate will do all the propagation work at initial propagation
 Well, when I change the code in propagation, it does not work properly any more. So I thing that code must be there, and is working well already.
 Also, which version leads to an infeasible problem: the one using your FixingDepot constraint or the one using predefined constraints in the model?

The FixingDepot works properly. This is the identical one in the main model which ruins the feasibility, and goes crazy :) It's weird since adding it to the main model leads to a solution violating many other constraints in the main model, such as allDifferent(env, successor) constraint!
 Do you use the automatic search of CP Optimizer in both cases?
 Yes, in both. However, I have another constraint, as defined class, to eliminate subtours. In this constraint, I stipulate that no node, except the final depots (which returns to the corresponding initial depot), can get back to any other node already visited by any of the vehicles in the fleet.
The crazy thing is that when I put the identical code for other constraints, such as time window and precedence constraints, in the main model, the result is the same! But I cannot figure out why the solver is sensitive to this particular constraint?!?
Thanks.
ACCEPTED ANSWER
Re: Constraints as objects VS Constraints in the main model
20130208T09:13:31Z in response to SystemAdminIt would be surprising if CP Optimizer comes up with a solution that violates the allDifferent constraint.
What does the log says? Is it really finding a solution or is it saying that the model is infeasible?
Unfortunately I was not able to run your code and reproduce the problem because (1) the code of constraint 'Ilo_NoSubtour' is missing, (2) matrix 'distance' is not initialized in the code and (3) there is no data.
Philippe
ACCEPTED ANSWER
Re: Constraints as objects VS Constraints in the main model
20130208T14:13:16Z in response to SystemAdminIt return a "really infeasible solution" as a solution. However, it's quite clear that it is not feasible at the first glance. Please see the outcome for a small instance in either case:
Case 1) When it's an object. It respects all the constraints, e.g. allDifferent;
Optimal value: 263
Successor(0)=3, Visit Time(0)=159; Vehicle(0)=0;
Successor(1)=8, Visit Time(1)=278; Vehicle(1)=1;
Successor(2)=0, Visit Time(2)=117; Vehicle(2)=0;
Successor(3)=7, Visit Time(3)=283; Vehicle(3)=0;
Successor(4)=1, Visit Time(4)=74; Vehicle(4)=1;
Successor(5)=4, Visit Time(5)=0; Vehicle(5)=0;
Successor(6)=2, Visit Time(6)=0; Vehicle(6)=1;
Successor(7)=5, Visit Time(7)=354; Vehicle(7)=0;
Successor(8)=6, Visit Time(8)=852; Vehicle(8)=1;
Case 2) When I put that constraint in the main model:
Optimal value: 298
Successor(0)=2, Visit Time(0)=122; Vehicle(0)=0;
Successor(1)=8, Visit Time(1)=59; Vehicle(1)=1;
Successor(2)=7, Visit Time(2)=154; Vehicle(2)=0;
Successor(3)=0, Visit Time(3)=70; Vehicle(3)=0;
Successor(4)=1, Visit Time(4)=20; Vehicle(4)=1;
Successor(5)=3, Visit Time(5)=0; Vehicle(5)=0;
Successor(6)=4, Visit Time(6)=0; Vehicle(6)=1;
Successor(7)=1, Visit Time(7)=188; Vehicle(7)=0;
Successor(8)=0, Visit Time(8)=95; Vehicle(8)=1;
As you see, in the case II, Successor(3)=Successor(8)=0 and Successor(4)=Successor(7)=1 which ignores allDifferent(successor) constraint! Moreover, Successor(7) must equal 5, and Successor(8)=6 according to the same constraint I'd put in the main model (connecting corresponding initial and final depots).
Can I email you my compact code and data?
Thanks
ACCEPTED ANSWER
Re: Constraints as objects VS Constraints in the main model
20130212T13:25:07Z in response to SystemAdminHello,
This is indeed a bug in last version of CP Optimizer (V12.5). This bug may occur when you are using both:
 a userdefined constraint (like the constraint Ilo_NoSubtour you have implemented), and
 some constraints that fix the value of some integer variables in the model (like the constraints successor[nbCustomers+nbVehicles+k]==nbCustomers+k in your model)
Philippe
ACCEPTED ANSWER
Re: Constraints as objects VS Constraints in the main model
20130214T14:53:50Z in response to SystemAdminThanks Philippe,
Yes, as you said the problem was due to the initial search. When I put cp.setParameter(IloCP::Presolve, IloCP::Off) in the main model, any of the both versions work and the result is the same.
Hossein

