Originally posted by: SystemAdmin

I've attached my parallel machine scheduling model - details on what it does are at http://www.ibm.com/developerworks/forums/thread.jspa?threadID=317278&tstart=0. I appended the data file to the end of the .mod file since it was too large and ungainly to paste in here. The model seeks to maximize the value of all the tasks scheduled where each task has one or more time windows on each machine/leg pair, every task is optional, some tasks can be repeated (though the data file contains none of these that can be feasibly scheduled more than once), every task has a duration relevant to each scheduling opportunity (aka "opp"), and asymmetric, non-zero transition times are included for many pairs of the tasks.
I don't expect to be able to solve large problems to optimality but the symmetry within the problem is keeping me from solving what I wish to be "moderate" sized problems even with only one machine (~40 tasks). The symmetry comes from the fact that every task has an assigned value so that feasible sequence 1-2-3-4-5 has the same value as feasible sequence 3-5-2-1-4...you get the idea.

I'm new to CP and have just downloaded a few articles to read on symmetry breaking in CP (Gent and Smith - "Symmetry Breaking in CP" and Petrie, Smith, and Yorke-Smith "Dynamic Symmetry Breaking in CP and LP Hybrids" but...
***My question***
I was hoping someone might be able to give me some pointers on how to apply it to this model.
*******
Although I think I have made the model as sparse as possible, since I am new, I would happily take any constructive criticism on how to improve it.
Thank you.
William
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,
CP Optimizer indeed focuses on computing good solutions rather than computing good lower bounds or proving optimality. It explains why, even if your model seems not very large, the engine can't prove optimality. You can use a time-limit (or a branch or a fail limit if you want to stop deterministically) to stop the search and access the best solution found so far.
I think your model is good.
Symmetry breaking help if the search heavily relies on search tree exploration which is the case of pure tree search or of tree search with restarts and no-good learning for instance. But the automatic search for scheduling problems involving interval variables is closer to local-search / large-neighborhood search and, in this context, the interest of symmetry breaking is less clear.
Furthermore, I do not see any symmetries to break in your general model as you state it (unless the data is very specific). It is true that the actual ordering of intervals in the sequences has no direct impact on the cost but given that each interval has specific values (e.g. different size, different opportunity windows on the sequence) you can't do any pre-ordering in the sequences. That would be different if you have several repetitions of the same task; in this case, you probably can indeed pre-order them with precedence constraints.

Philippe
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Philippe,
Thanks for your answer. This is where my shallow knowledge of CP comes in as I am not well versed with backtracking search versus large-neighborhood search, etc. If I understand you, though, you are saying that the default search method for this problem does not rely on a tree structure so that knocking out a symmetry in one place wouldn't help elsewhere?

Is there a way to alter the search strategy to perhaps then take advantage of symmetry reduction? The reason I ask is that I'm not convinced yet that there is no symmetry in my problem, if not a priori identifiable symmetry (at least with the heuristic we have, it was extremely important to get rid of the symmetries to go from hours/days/weeks to sub-5 second computation times for some extremely large problems (50 machines, each with 10-20 legs and a total of 7000 tasks so that each machine/leg had an average of 100-200 possible tasks on it)).

Here is why: every opp is uniquely identified by the machine/leg/task triple. Though that triple may have a couple feasible time windows, the value for the task on that machine/leg is the same. For another machine/leg pair, the task may have a different value, yes, but then again, it will have a different unique identifier. Therefore, a solution that looks like <1 1 5> <1 1 3> <1 1 1> (meaning the sequence of tasks 5, 3, and 1 are done on machine/leg pair 1,1) has the same value as any other feasible permutation of these uniquely identifying triples, no matter what actual times the intervals are scheduled at.

A la adding symmetry-breaking cuts and branching rules in branch-and-cut (Ostrovsky's papers on orbital branching), aren't there ways of dynamically adding symmetry constraints during tree search in CP? In the Gent and Smith paper, they talk about the SBDS approach - Symmetry Breaking During Search - and apply it to n-queens and a few other problems. If this means I need to learn about writing my own constraints, I'd love to dive in as my goal in this project is to turn CP from something that I know is out there into something I can use intelligently and integrate with LP/IP work.

Does my rationale make sense or am I trying to fit math programming square pegs into contraint programming round holes?
Thank you for your help,
William
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

I see.
If your goal is to investigate the exploitation symmetries to better solve this problem with CP, you can indeed write your own symmetry breaking constraint / search strategies in CP Optimizer in C++ (see the Reference Manual of CP Optimizer: C++ API Reference manual > optim.cpoptimizer.extensions).
Note anyway that the engine extensions are only available for integer variables (IlcIntVar), they are not available for interval and sequence variables. In the model, you will need to define additional integer variables that are constrained to be equal to the start/end and presence statuses of the interval variables and work with these integer variables in the engine. That may make you model heavier and you may also miss some access to the sequence variables (I see from your description that the symmetries concern the possible values of the sequence variables). The CP Optimizer search type that will take the most advantage of symmetry breaking will be the "DepthFirst" search type. It explores a unique search tree so pruning redundant part of this tree can speed-up the search a lot.

But my intuition is that even with strong symmetry breaking except for small problems "DepthFirst" won't outperform the default "Restart" strategy in terms of solution quality. For small problems, "DepthFirst" may be able to come up with some solution it has proved to be optimal whereas "Restart" won't prove optimality.

Symmetry breaking should have much less impact on the default "Restart" strategy. If you want to have additional information on the "Restart" strategy, you can have a look to the following conference paper that describes the main ideas: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.4415&rep=rep1&type=pdf. If what you need is some gap to estimate the quality of the best solution found by the Restart strategy, a classical approach would be to relax the problem and use math programming or integer CP techniques to find lower bounds or optimal solutions to the relaxed problem.

Philippe
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Philippe,
Thank you again. The CP Optimizer angle as well as considering your paper about the restart strategy give me plenty to consider for the time being.
Thanks,
William
#ConstraintProgramming-General
#DecisionOptimization