Originally posted by: AshishS

Hi,

I have a rather complex CP scheduling model and I would like to start it off with a heuristically obtained initial / starting solution.  While I am able to use IloSolution to provide values of all IloInterval variables to the model, CP Optimizer (12.4 and 12.5.1) does not recognize it as a proper feasible solution right away and starts branching.

I believe the issue will get resolved if there was a way for me to specify values of CumulFunction expressions as part of the starting solution, but unfortunately I don't see a way to do it.

Here is the setup in more detail:

Not only do I have a simple heuristic to find a starting solution, the model can be simplified to various extents by removing some scheduling flexibility and then solved faster, so I am trying to solve it in multiple stages by solving "easier" stages first and then passing on the solution obtained as a starting point for the next stage.  This starting point is always guaranteed to be a proper feasible solution.

The issue, I believe, is the fact that several of the resource constraints on these interval variables are specified using CumulFunctions, which sum up resource usage in each 'service region' and make sure it never exceeds the time-dependent (and itself dynamic) resource availability in that service region.  The resource availability per service region itself is a CumulFunction which, when summed over all regions, must not exceed a time-dependent (but fixed and provided as input) overall global resource availability.

The value of these regional cumulative functions for resource availability, unfortunately, cannot be inferred from values of the IloInterval variables provided through IloSolution.  (Regional resource usage can be inferred, of course, but not availability.)  My guess is that CP Optimizer is unable to realize that, given the IloInterval variable values, the regional resource availability CumulFunctions can in fact be set in such a way so as to satisfy the overall global availability constraint.

Any suggestions on how to make CPO realize it is getting a feasible starting solution would be greatly appreciated!

Thanks,

Ashish

PS.  If the description of CumulFunctions for resource usage and availability seem overly complex, I would be happy to provide clarification.  If there is an easier way to model all this, that would be much appreciated too!

Originally posted by: PhilippeLaborie

Hello,

If you specify in your starting point solution a value for all the "variables" of your problem and if the solution is feasible, then this solution should be the first one explored by the search.

In the sentence above, "variable" means:

• Interval variables (start, end, presence status)
• Integer variables
• Heights of elementary cumul functions when those functions are created with a range (for instance pulse(interval, hmin, hmax))
• Sequence variables (although in most of the cases, the value of the sequence variable can be inferred from the start/end/presence value of its interval variables; but this is not true if for instance the sequence contains interval variables of null length fixed at the same value)

Note that there is currently no way to directly specify the height value of an elementary cumul function in an IloSolution so if you want to do that you will need to create an integer variable and relate it with the height of the elementary cumul function (using heightAtStart/End expression).

So you should maybe check if some variable values are not missing in the solution. A cumul function defined as the sum of elementary cumul function is not a "variable", it is in fact an expression that become fixed as soon as the variables it depends on (interval variables, elementary cumul function heights) are fixed, so there is no need to put the values of a cumul function in the starting point.

Another remark: it is not always easy to see if a starting point solution has been restored in the engine. In particular if you are using multiple workers, it may be that the first bound that is displayed in the log is not really the one of the first solution but the one of another solution found a bit later. In this case, the best is to see what happens in single worker (IloCP::Workers=1).

Philippe

Originally posted by: AshishS

Thanks, Philippe.  This is very useful information (what all needs to be specified for IloSolution) and could perhaps even be added to the CP Optimizer documentation around IloSolution.

The issue is precisely caused by cumulative functions with variable height, created using pulse(interval, hmin, hmax).  Specifying their solution value using a new variable that captures their heightAtStart, as you suggest, is something I could try.  However, I'll be introducing IloInt variables, in addition to IloInterval variables, which used to trigger a bug in the CPO propagator for an earlier version of the same model (as documented in this DeveloperWorks thread).  To avoid triggering that bug, I had changed the model to post constraints directly using the heightAtStart expression instead of IloInt variables capturing the height.

Presumably no other way out to have CPO "quickly" recognize the provided values as a feasible solution without introducing IloInt vars?  Would it make sense to have a search phase defined which makes CPO branch first on all IloInterval vars and only then on the new IloInt ones (which will be unnecessary anyway after IloInterval variable heights are fixed)?

Thanks much!

Ashish

Originally posted by: PhilippeLaborie

The bug mentioned in the other thread has no real link with the introduction of integer variables in the model. It is even quite strange that removing the integer variables solved the problem; this work-around is probably not safe. The best will be to use the new version 12.6 that will soon be released and fixes this problem (availability of CPLEX Optimization Studio V12.6 is planned for December 6, 2013).

I do not see other ways to specify the value of heights in the starting point solution. I would try using the integer variables. Note that it is also possible that the starting point solution cannot be restored because of the propagation issue with the cumul function.

Philippe