Originally posted by: Arnaud M.

Hi,

Is it possible to define a custom goal directly within OPL or do we need to define it thanks to the OPL interface ?

I did not find anything in the documentation about it, but I prefer to be sure before starting with the interface.

Best regards,

Arnaud

Originally posted by: ChrisBr

Hello Arnaud,

Custom goals are not available within OPL, only by using OPL interface.

But a lot of useful features are available using searchPhases.
Here is the documentation page on how using searchPhases in OPL, and you might have a look at sports sample and timetabling sample which both use such searchPhases.
For a better understanding of searchPhases, see the C++ reference manual for IloCP, IloSearchPhase, IloVarSelector, IloValueSelector.

Regards,

Chris.

Originally posted by: Arnaud M.

Hi Chris,

Thank you for the answer.

I have already defined a search phase on an array of sequence variables, but is is not working.

In my model, the tasks have variable duration that must sometimes be increased to enforce that a cumulative resource is available.

My guess is that the durations are fixed too early and that the partial assignment cannot be extended any more to a solution. But, in my problem, any permutation is feasible (I have removed the objective function).

So when are fixed the task duration when using search phases ?

Best regards, Arnaud

Originally posted by: PhilippeLaborie

Hi Arnaud.

The search phases on arrays of sequence variables is a bit primitive in that it just take the sequences in a certain order and then fully sequence them, one by one. Then once all sequences in the phase are sequenced, it fixes the start / end values of interval variables (and thus, indirectly, their length).

Could you explain a bit more how the tasks variable duration is related with the cumulative resources? Maybe there are ways to reformulate the problem so that you get more propagation on the interval variables and their length ...

Philippe

Originally posted by: Arnaud M.

Hi Philippe,

Of course, I have enclosed the model and two instances to illustrate my issue.

In my opinion, the solver should find a first solution without failing.

With the small instance, the solver finds a solution but fails a little bit.

oplrun lofas.mod m_05_n_010_mp_50_mo_50.txt.dat 

! ----------------------------------------------------------------------------
! Satisfiability problem - 61 variables, 14 constraints, 1 phase
! TimeLimit            = 60
! Workers              = 1
! CumulFunctionInferenceLevel = Extended
! LogVerbosity         = Terse
! Initial process time : 0,00s (0,00s extraction + 0,00s propagation)
!  . Log search space  : 564,4 (before), 564,4 (after)
!  . Memory usage      : 791,0 kB (before), 791,0 kB (after)
! Using sequential search.
! ----------------------------------------------------------------------------
!               Branches  Non-fixed            Branch decision
*                    900  0,05s                     -
! ----------------------------------------------------------------------------
! Search completed, 1 solution found.
! ----------------------------------------------------------------------------
! Number of branches     : 900
! Number of fails        : 20
! Total memory usage     : 2,1 MB (1,5 MB CP Optimizer + 0,6 MB Concert)
! Time spent in solve    : 0,05s (0,04s engine + 0,00s extraction)
! Search speed (br. / s) : 18�000,0
! ----------------------------------------------------------------------------

With a larger instance, the solver does not find any solution and fails massively.

oplrun lofas.mod m_25_n_120_mp_50_mo_50.txt.dat 

! ----------------------------------------------------------------------------
! Satisfiability problem - 3�051 variables, 54 constraints, 1 phase
! TimeLimit            = 60
! Workers              = 1
! CumulFunctionInferenceLevel = Extended
! LogVerbosity         = Terse
! Initial process time : 0,16s (0,16s extraction + 0,00s propagation)
!  . Log search space  : 69�304,5 (before), 69�304,5 (after)
!  . Memory usage      : 17,6 MB (before), 17,6 MB (after)
! Using sequential search.
! ----------------------------------------------------------------------------
!               Branches  Non-fixed            Branch decision
! ----------------------------------------------------------------------------
! Search terminated by limit, no solution found.
! ----------------------------------------------------------------------------
! Number of branches     : 295�524
! Number of fails        : 69�954
! Total memory usage     : 213,4 MB (158,8 MB CP Optimizer + 54,5 MB Concert)
! Time spent in solve    : 60,00s (59,84s engine + 0,16s extraction)
! Search speed (br. / s) : 4�937,7
! ----------------------------------------------------------------------------

Thank you very much for your help.

Arnaud

Originally posted by: PhilippeLaborie

Very interesting and unusual scheduling problem! 

I think the difficulty for CP Optimizer is that the search tries to schedule too many of the machines as early as possible which results in an infeasibility because of the machine setters usage.

One thing that could help is to compute a (bad) starting point, for instance where each machines are scheduled on different time windows (this way, they do not interact with the machine setters limited capacity).

I did that in your model and it helps, at least for finding a solution of course. The small model manages to prove optimality (387) but on the large one there is not much improvement. I'll try to look why.

Also, in your model I reformulated the cumul function to factorize the stepAtStart-stepAtEnd as pulse, this can only help.

Originally posted by: Arnaud M.

Hi Philippe,

One thing that could help is to compute a (bad) starting point,

We are gonna try with better starting points.

Also, in your model I reformulated the cumul function to factorize the stepAtStart-stepAtEnd as pulse, this can only help.

It is such a natural formulation ! I was satisfied to remove the optional variables of the previous model and I have stopped halfway.

I will keep you updated.

Arnaud

Originally posted by: PhilippeLaborie

Here is another idea to formulate the problem in CP Optimizer. In the attached model, I added an explicit interval variable to represent the 'gap' between two consecutive tasks on a machine. The 'tasks[m][j]' and 'gap[m][j]' are constrained to be contiguous so that 'gap[m][j]' starts at the end of 'tasks[m][j]' and ends at the start time of the next task. Then of course, the machineSetter cumul function is directly the sum of pulses on the gaps.

I also tried a few redundant constraints on this model but they do not seem to help much.

With this model, the starting point does not seem to be necessary (at least on the two instances you sent). And the solutions are of better quality. I attach for instance a solution to the larger problem with makespan 7484 found in a couple of minutes. As you see the machines seem to be quite compacted with small setup times. It would be interesting to compare this solution to a lower bound, for instance computed by solving each of the individual machine as a TSP (This will only relax the machineSetter constraint).

I'm not saying this model will magically solve all your instances, but for sure this type of model may worth considering. Maybe it can be mixed with the previous model ...

Philippe

Originally posted by: Arnaud M.

Hi Philippe,

I have also thought to introducing gap variables, but I did not found the startOfNext function whereas I was aware of typeOfNext !

It is clearly my mistake, but the documentation was not so helpful : the opl doc misses related references ; the cpo doc is more complete.

I have tested on a few other instances and the new model improves the performance again. In the overall approach, we are already using TSP for various steps (starting points, lower bound, post-optimization), but I did not mention it.

Thank you very much for your help. I will eventually post updates later.