Originally posted by: hubsi

hi,

i'm currently modelling a scheduling problem for a university course on constraint programming and since i got a license over ibm onthehub program, i wanted to try the cplex CP solver.

So far I have successfully modelled the problem and small instances can be solved optimally  in just a few moments. However, even though  larger instances can be decided, i am not able to get an optimal solution (actually not necessarily optimal, just compared to the fitness achieved by some colleagues - even though my solutions are already quite good :) ).

of course i know that i have to improve my model, but since i'm using a highly sophisticated commercial tool, i also want to test other approaches (also to discuss these techniques in my report). 

i know that there is always a tradeoff between number of variables and constraints and hence i tried to minimize both.. but of course that is not always possible. 

the decision part is rather easy (scheduling with some precedence constraints) and i modelled this with 2n variables and element constraints + lessthan

however the optimization goal is rather complex and i had to introduce several new variables (some binary maps & co roughly O(n^2) variables per map and some arrays with O(n) with a rather small integer domain ) and several constraints (element, min, max, and, ...).

so to finally get to the point:

- i have used the ifthenelse constraint. how expensive is it in practice? should it be avoided? what about logical combination of constraints? i avoided 'or' for obvious reasons but what about 'and'? it made my model much simpler but are these combined constraints expensive in the cplex cp implementation?

- i tried to improve my model by removing some auxiliary variables by using more complex terms in the constraints. it seemed to speed up the search a little bit. of course there is no general answere to this question since this highly depends on the scenario at hand, but are there any practical tips for the cplex cp solver?

- some of my variables directly depend on the value of others. eg when assigning one job to a slot, a variable for some location has a fixed value. of course this should be handled by constraint propagation but are there any possibilities to tune this/ configure this for some pairs. eg. if variable x is set then automatically consider variable y for constraint prop first?

- i also tried to use phases to first consider my decision variables and then the 'optimization vars'. however the improvement was negligible.. can someone give me some tips on how to use the phases properly?

- some time ago i also modelled a similar problem with the milp solver and using a shared memory machine with >8 cores seemed to be super fast. however for the cp solver my notebook with a 6th gen i7 dual core is faster than these machines.. i also played a little with the parallel mode config (deterministic or not ..) but without success. any tips on that?

best regards

Hi,

could

https://www.ibm.com/developerworks/community/forums/html/topic?id=de52cac0-be5c-4106-8dcf-767b1b7a65b7&ps=25

and

https://twitter.com/PhiLaborie/status/879383664940986368

help ?

regards

Originally posted by: PhilippeLaborie

Hello,
Indeed, a far as CP Optimizer is concerned, the main source of improvement should be the model itself (playing with search phases and search parameters like parallelism etc. should be considered only in a second step).

From the description of your model, I think that you should try to find a way to avoid the quadratic behaviour in the formulation of the objective and the "ifthenelse" or "or" in the logical combination of constraints. Of course it may turn out to be difficult or even impossible but if you can describe the objective function and more generally, why you need these features in the model, maybe we could help with some advice.

Also, you say: "the decision part is rather easy (scheduling with some precedence constraints) and i modelled this with 2n variables and element constraints + lessthan". Are you using interval variables or only integer variables in your model? Usually in CP Optimizer, scheduling problems are modelled with interval variables and, typically, precedence constraints with constrains like endBeforeStart(intervalVar1, intervalVar2) and, at least for scheduling with precedence constraints, one does not need to use element constraints ...

Philippe

Originally posted by: hubsi

hi,

at first: alex thank you for this link & philippe thank you for this exhaustive answere in this post :)

Since it's a project for university I don't want to state too much information about the scenario to avoid getting too elegant solution hints from experts like you :D

I know that the solver has some special scheduling features, however, i think ordinary decision variables are sufficient for my scenario since the optimization goal is not a typical scheduling target function like makespan or something like this, but the goal function can be constructed by this simple job order sequence. But is the element constraint expensive compared to using interval variables + endBeforeStart? At the moment, I simply use an array with job-IDs that specifies the order of the jobs and an array with the indices of the jobs - connected via the element constraint. the precedence constraints are modelled simply by indexarray[i] < indexarry[j].

I also invested some time to improve my model and managed to remove a major part of the IfThenElse Constraints by some fiddling with arithemtic operations (mostly product, min, max and abs) and i am confident to remove the other part of the IfThenElse constraints as well. I haven't benchmarked yet but for a small sample of 20 decision variables i managed to remove the number of constraints from 60 (with if then else) to 40. However, the constraints look something like: min(1, abs( max(0,x*y)) * min(0, x * z)) ... since i don't have any real experience in CP on what 'real-world' constraints look like - is such a constraint considered to be 'expensive' or is such a construct easily be evaluated/handled by the solver?

best regards

Originally posted by: PhilippeLaborie

If you do not have durations or numerical temporal constraints between your jobs (involving some numerical delays) then indeed maybe you do not need to use interval variables. Your problem looks more like a purely sequencing problem (find a "good" sequence of items) rather than a scheduling problem. And when you say your a posting constraints like indexarray[i] < indexarry[j], I suppose these are not really involving |element" constraints because the i and j are not decision variables here, they are fixed, right?

Concerning the IfThenElse constraints, it is not clear whether your reformulation is better. In fact as soon as you have constraints involving several times the same variables inside (like min(1, abs( max(0,x*y)) * min(0, x * z)) ... that involves several times the variable x), then it would help to find a formulation that somehow factorizes the variables. I'm also not sure why you need the "abs" here as you know the sign of the term but this is a detail. What is clear is that a keypoint in your model will be to find a good formulation for the objective. "Good" here means that the formulation should be able to back-propagate as much as possible the bounds on the objective (upper bound if you have a minimization objective) on the decision variables. But without more information of the objective function it is hard to help. Try to look if global constraints (like all_different, pack, sequence, all_min_distance, inverse, or "table" constraints like allowed/forbidden_assignments) can help.

Philippe

Originally posted by: hubsi

"because the i and j are not decision variables here, they are fixed, right?" yeah just i and j are just indices of an array of decision variables.

Furthermore, thanks for the hint with the global constraints. I replaced a set of element constraints over an array with inverse and this improved the performance notably.

For now, thanks for the answers. I will try to improve my model again and if i have a more specific question regarding a specific scenario I will post again :)