Originally posted by: JorisK

Dear,

I'm currently trying to solve a problem involving a complex mixture of a routing and a scheduling problem.

Some (but not all) features of my problem are:

-heterogeneous fleet of vehicles

-split deliveries (i.e. customer is visited by multiple vehicles, a single vehicle may visit the same customer more than once)

-time windows, time lags and sequence dependent setup times

One of our solution approaches utilizes a Mixed Integer Programming (MIP) model. I would like to strengthen the model by tightening bounds and adding a number of valid inequalities. For example:

-The number of required deliveries to a single customer are unknown and depend on the capacity of the vehicles. A weak upper bound on the number of required deliveries is the demand of the customer divided by the capacity of the smallest vehicle.

-A time window is associated with each customer. Currently, each individual delivery for a customer inherits this time window. It would however be better to tighten the time windows associated with individual deliveries. E.g. setting the time windows of deliveries d1, d2 for customer c1 (time window [0,10]) to d1=[0,5], d2=[5,10] is better than setting d1=d2=[0,10]. 

-Certain customers are incompatible with each other, i.e. it is not possible to satisfy the demand of all customers due to capacity and time constraints. For two incompatible customers c1, c2, this could lead to a cut like: c1+c2 <= 1

Reasoning about the variable domains in the context of my problem is notoriously difficult. Hence I was wondering whether I could use constraint programming to do the job for me. Would it be possible to do the following:

a. model my problem using Ilog constraint programming (java interface)

b. apply constraint propagation (but NO branching)

c. query the domains of the variables after all constraints have been propagated and adjust the variable domains of my MIP model accordingly

1. Are steps b, c possible using IloCP+Java? Is there a way to query the variable domains after constraint propagation?

2. Does this make sense, or is this a rather ridiculous idea (I'm for example not sure whether or not Cplex already implements domain reductions or whether cplex would benefit from the strengthened domains)? As I'm not an expert in constraint programming, it would take me a considerable amount of time to implement my problem, so basically I'm trying to determine whether it is worth the effort :)

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Petr Vilím

Hello,

what you suggest makes perfect sense and the API of CP Optimizer supports it. And possible to do even more, in particular you can inject solution found by CPLEX a starting point for CP Optimizer search and try to improve it.

You can get the maximum from both solvers by modelling the problem in completely different ways. In CP Optimizer you can use interval variables for actions/activities, noOverlap constraint with setup times for activities that cannot overlap. There are also optional interval variables for activities that may but doesn't have to be executed what allows to model alternatives in the schedule (using constraint 'alternative'). A good starting point to read about modeling scheduling problems using CP Optimizer may be the following in the documentation:

CP Optimizer > CP Optimizer C++ API Reference Manual > Concepts (on the top of the right page) > Introduction to Scheduling Concepts in CP Optimizer

Those mathematical modeling concepts are the same for C++ and Java, so don't mind that it is inside C++ documentation.

That would be for the part (a). For (b), to apply propagation but do not search, just call propagate() on IloCP. It returns true if the model was not found infeasible during the propagation. After propagate, to answer part (c), you can call functions on IloCP to check variable domains, for example getStartMin(intervalVariable), getMax(integerVariable), isPresent(intervalVariable) etc.

Finally, give a try to CP Optimizer search. I understand that your goal is to improve your MIP model, but I believe that CP Optimizer may find some pretty good solutions for this kind of problem too. Or it can improve a solution found by CPLEX if the solution is passed to IloCP using setStartingPoint function.

Best, Petr

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: JorisK

Dear,

Note: in my experiments, I have set: cp.setParameter(IloCP.IntParam.DefaultInferenceLevel, IloCP.ParameterValues.Extended);

for every combination of customers C:

forall(c in C)

  c.setPresent()

forall(c not in C)

  c.setOptional();

Next you can propagate the model again and see whether the result is infeasible. This approach seems however rather expensive, especially since you would have to run this approach for every combination of customers? Is there a smarter approach?

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: Petr Vilím

Hello Joris,

you made very good analysis!

I'll start with a detailed explanation of propagation in CP Optimizer (CPO for short). CPO gathers all constraints such as "presenceOf(x) => presenceOf(y)" into "logical network". Logical network contains all kind of implications between presence statuses, in particular negations are also allowed. Logical network is basically a 2-SAT and it is also propagated this way.

Precedence constraints fooBeforeFoo (for example endBeforeStart) are gathered in a similar way into "temporal network". Propagation of temporal network is using logical network to know what intervals variables influence each other. You can find more details about this propagation in the paper by P. Laborie and J.Rogerie: Reasoning with Conditional Time-intervals. This is the propagation that is able to see that customer cannot be satistfied in the instance 2. The paper can help you to better understand what's going on behind the scene.

The important fact is that for a constraint to be included in logical network, it must be written in the form: [!]presenceOf(x)=>[!]presenceOf(y). So the constraint to satisfy customers: precenceOf(customer[c]) ==  (sum(d in Deliveries: d.customer==c) (precenceOf(delivery[d])*d.capacity) >= c.demand) is not included in logical network. And currently there is no presolve step that would derive some redundant implications form this constraint.

So, if you think that there may be some redundant implications derived from this constraint, then it may help to add those implications into the model manually. The advantage is that temporal network will be able to take those implications into account and therefore propagate better.

To the instance 1:

As you say to have a non-zero objective, interval c1 must be present. However there is no constraint that forces objective to be non-zero. The purpose of objective is to propagate that the objective value must be better than objective value of the best solution found so far. As only propagate() and not solve() is called, there is no previous solution and therefore objective is completely ignored.

So, to get better propagation, it would be necessary to add a constraint saying that objective expression is > 0. The more you constraint the objective value the more propagation you may get. So it may help to wait until some initial solution is found. And also it may pay off to redo the propagation when a better solution was found.

To the instance 2:

Your idea to set some intervals as present and propagate is perfect. However I'm not sure whether you have to do it for every combination of customers C. Lets say that we try to set only one optional interval X to be present and call propagate(). If it fails then X must be absent. If it doesn't fail, then some other optional interval Y may become absent and yet another interval Z may become present. Then it is possible to add the following implications both into MIP and CP models:

presenceOf(X) => !presenceOf(Y)

presenceOf(X) => presenceOf(Z)

Of course, it will capture only binary disjunctions. It is possible to go further, but it will be more costly: set two interval variables X and Y to be present at the same time. And depending on the outcome add into the model:

if propagation fails: !presenceOf(X) ||  !presenceOf(Y) (will be included in logical network)

if Z becomes absent: (presenceOf(X) && presenceOf(Y)) => !presenceOf(Z)

if Z becomes present: (presenceOf(X) && presenceOf(Y)) => presenceOf(Z)

Best, Petr

#ConstraintProgramming-General
#DecisionOptimization