Originally posted by: mdelorme

Hello,

I'm working on the Resource Constrained Project Scheduling Problem (RCPSP), and I'm right now using the file"sched_rcpsp.cpp" available in the examples for CP optimizer to solve the problem (I removed the failLimit so that I solve exactly the problem).

The model is working really well on litterature instances. However, I try (for experimental purposes)  to "help" him on a specific instance by giving him a valid UB (in that case, UB = optimal solution), and the time spent to solve this specific instance goes from 8 seconds with the basic program to 1200 seconds if I add the instruction "model.add(IloMax(ends) <= UB)", or whatever the way I am using to give him the valid UB. This is not likely due to randomness, as absolutely all the instances of the set I am solving are solved in less than 100 seconds.

I really don't understand such a behavior, as even in the basic program, once the cp optimizer finds a solution of value 58, it should continue the exploration tree with a UB equal to 58 right ? So what is the difference ? 

I would really appreciate some explanations, or a pointer on a documentation that could explain me this phenomenon.

Best regards,

Max

Originally posted by: PhilippeLaborie

Hi,

CP Optimizer uses two concurrent search strategies, one (LNS) that aims at producing feasible solutions of good quality and one (FDS) that aims at proving optimality (in fact, infeasibility of a solution strictly better than the current solution). The first strategy works by iterative improvement of the current solution, but for that it needs ... a current solution. When you constrain "UB=optimal solution" you make it much harder to find a feasible solution and in any case, harder than for LNS to iteratively improve an initial (may be not so good) solution up to (well, down to) UB=optimal solution. That is probably part of the explanation.

Originally posted by: mdelorme

Hello,

Thank you for your answer. It makes sense.

I have a related question thought. If I understood correctly, in the basic program, once a solution of value UB has been found, FDS will prove the infeasibility of value UB-1. For the specific instance I'm trying, the whole thing is done in 8 seconds.

Right now, I am trying to solve the instance by putting "UB = optimal solution -1", that should lead to infeasibility. However, the time required to solve the instance (detect infeasibility) is way bigger (nothing after 300 seconds).

So my question is, what is the difference between setting "UB = optimal solution -1" and letting CP optimizer find itself a solution of value UB and then detect infeasibility for value UB -1. If it is because FDS cannot be called if no initial solution has been found, is there a way to go over it ?

Thanks a lot for your help,

Max

Originally posted by: Petr Vilím

Hello Max,

the default search of CP Optimizer first tries very hard to find a feasible solution. FDS is used for only very small fraction of time until the first solution is found and optimized a little (using LNS). This is hardwired behavior that you (as the user) cannot change at the moment (even by FailureDirectedSearchEmphasis parameter).

There are two options though how to circumvent this problem:

1. Instead of giving upper bound, you can pass a valid solution to CP Optimizer using function IloCP::setStartingPoint. This way, CP Optimizer will have a solution and it will allocate more time to failure-directed search. If you pass an optimal solution then CP Optimizer will automatically start to look only for better solution, i.e. it will use UB = optimum-1 (assuming integer cost like in RCPSP).

2. Don't use default search and instead in C++ call: cp.solve(IloFailureDirectedSearchGoal(env))

IloFailureDirectedSearchGoal is an undocumented function (it can disappear or change the name in the future). It will run pure FDS using one thread (there is currently no way to run FDS on more threads outside the default search).

FDS is described in more detail in paper "Failure-Directed Search for Constraint-Based Scheduling".

Best regards, Petr

Originally posted by: mdelorme

Hello,

Ok, thanks a lot for the clear answers, 

Best,

Max