Topic
  • 6 replies
  • Latest Post - ‏2013-02-14T14:53:50Z by SystemAdmin
SystemAdmin
SystemAdmin
554 Posts

Pinned topic Constraints as objects VS Constraints in the main model

‏2013-02-06T23:50:09Z |
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!
Updated on 2013-02-14T14:53:50Z at 2013-02-14T14:53:50Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Constraints as objects VS Constraints in the main model

    ‏2013-02-07T15:09:15Z  
    Hello,
    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
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Constraints as objects VS Constraints in the main model

    ‏2013-02-07T16:29:20Z  
    Hello,
    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
    Thanks 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, nbDepotsAndCustomers-1);
    IloIntVarArray VisitTime(env, nbDepotsAndCustomers, 0, 4000);
    IloIntVarArray vehicle(env, nbDepotsAndCustomers, 0, nbVehicles-1);
    //-------------------------------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 < nbDepotsAndCustomers-1; 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.
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Constraints as objects VS Constraints in the main model

    ‏2013-02-08T09:13:31Z  
    Thanks 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, nbDepotsAndCustomers-1);
    IloIntVarArray VisitTime(env, nbDepotsAndCustomers, 0, 4000);
    IloIntVarArray vehicle(env, nbDepotsAndCustomers, 0, nbVehicles-1);
    //-------------------------------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 < nbDepotsAndCustomers-1; 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.
    It 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
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Constraints as objects VS Constraints in the main model

    ‏2013-02-08T14:13:16Z  
    It 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
    It 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
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Constraints as objects VS Constraints in the main model

    ‏2013-02-12T13:25:07Z  
    It 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
    Hello,
    This is indeed a bug in last version of CP Optimizer (V12.5). This bug may occur when you are using both:
    • a user-defined 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)
    In this case, a work-around consists in switching off CP Optimizer's presolve by calling cp.setParameter(IloCP::Presolve,IloCP::Off).

    Philippe
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Constraints as objects VS Constraints in the main model

    ‏2013-02-14T14:53:50Z  
    Hello,
    This is indeed a bug in last version of CP Optimizer (V12.5). This bug may occur when you are using both:
    • a user-defined 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)
    In this case, a work-around consists in switching off CP Optimizer's presolve by calling cp.setParameter(IloCP::Presolve,IloCP::Off).

    Philippe
    Thanks 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