7
$\begingroup$

Could someone give additional explanations about the TimeLimit of CPLEX for CPO?

I am using CPLEX to solve a problem of assignment and scheduling in which each task needs to be assigned to a worker, by respecting a correct sequence. There is a cost of changing the worker and the cost of tasks execution changes from one worker to another.

When I do not state the time limit, it takes about 15 hours to return a result. When I stated the time limit = 10 seconds, it took about 10 seconds to find a correct result, correspondent to that found by the solver after turning during 15 hours.

The only difference between both results is the sequence of tasks executed by the same worker, but it does not imply on the objective function.

My questions are:

  1. Why the solver takes 15 hours to obtain a result if it could take just few seconds to obtain an equivalent result?
  2. Could it be related to the fact that there are many possibilities of sequencing the tasks without changing the objective function value?
  3. How to know which is the most appropriate time limit to use?
$\endgroup$
  • 1
    $\begingroup$ You mention both CPLEX and CPO (CP Optimizer). Which one are you using? $\endgroup$ – prubin Dec 5 '19 at 18:56
  • $\begingroup$ I mean I use the docplex.cp module to call the IBM ILOG CPLEX Optimization Studio in Python $\endgroup$ – campioni Dec 6 '19 at 9:31
  • $\begingroup$ @campioni, would you say, what is your problem scale? (I mean, how many binary variables are there in your model?). AFAIK, CP optimizer logic is different from CPLEX logic to solve the MILP problems. I tried a couple of large scales scheduling problems using CP and they were solved in a reasonable time. Are you sure to use the correct form of the CP definition in your model? $\endgroup$ – A.Omidi Dec 6 '19 at 10:55
  • $\begingroup$ @A.Omidi I used both solvers (CPLEX and CPO) but my model is based in mathematical programming, I mean I did not use specified functions in CPLEX, such alldifferent or even interval variables to state precedence. In think it spend a long time to be solved through CPO because of the model symmetry as they said in other answers. $\endgroup$ – campioni Dec 9 '19 at 14:21
9
$\begingroup$

What Nikaza said, and also: problems of this kind often have a large number of solutions that differ only by trivial permutations/relabellings/reorderings. For example, if one worker is assigned 10 tasks that can be done in any order with no change to the objective, then there are 10! = 3628800 solutions that will have exactly the same OF. If another worker has the same situation, then you have around 1013 optimal solutions that are identical modulo task reorderings, and so on.

In my experience, this kind of symmetry sometimes leads to excessively slow solution times with the sort of behaviour you describe, and tweaking the problem to break symmetry can significantly improve performance.

A couple of options for symmetry-breaking:

  • Add constraints that impose orderings.

For example, if tasks A and B are identical in requirements, we might require that B can't start before A does.

  • Make small perturbations to the objective function weights such that the solutions are no longer identical.

For example, if your model has a binary decision variable x[j,t] indicating whether task j begins at time t, then adding the sum of x[j,t]*r[j,t]*smallnum to the objective function breaks symmetry with respect to task ordering.

Here, r[j,t] is a randomly-determined parameter chosen separately for each [j,t] and smallnum is chosen small enough that the solution will still be approximately optimal with respect to the original objective function, but large enough not to get rounded away to zero.)

IME, these options can sometimes produce a surprisingly large improvement in runtime.

$\endgroup$
  • $\begingroup$ Thank you for your explanations. For your second suggestion, in practice, how could I make perturbations on the objective functions ? $\endgroup$ – campioni Dec 6 '19 at 16:33
  • 1
    $\begingroup$ @campioni I added an example, though you may need to adapt to fit your model. $\endgroup$ – Geoffrey Brent Dec 6 '19 at 22:16
  • $\begingroup$ thanks for your help, I appreciate it. $\endgroup$ – campioni Dec 9 '19 at 13:27
6
$\begingroup$

CPLEX is probably spending 15 hours trying to reduce the optimality gap. This is very common issue in MILP problems.

The way MILPs are solved is commonly to make all integers continuous and solve the resulting LP. That is called the linear relaxation, and its solution provides a valid lower bound (if we are minimising) on the objective function. The difference between the best integer solution the solver has found and that lower bound is called the optimality gap.

In branch and bound, it's common to find the best integer solution fairly quickly, and the bulk of calculations is spent to prove that this solution is globally optimal, i.e., to close the optimality gap.

There are two ways to handle that in practice:

  1. Use the optimality gap as your convergence criterion, i.e., "stop calculating if the gap is smaller than 10%".
  2. Define a design goal in your objective function. This means that, instead of minimising cost you would minimise cost-good_enough_cost and stop when that number is zero. This could also be expressed in terms of a constraint: cost-good_enough_cost >= 0.
$\endgroup$
  • $\begingroup$ nikaza, thanks for replying. I am trying to optimize a 0-1 integer linear programming problem. In this case, optimality gap could also be an issue? $\endgroup$ – campioni Dec 5 '19 at 13:09
  • 1
    $\begingroup$ Yep. This is how CPLEX is likely to solve it under the hood, it will relax the binaries to continuous between 0-1 and solve a series of LPs in branch-and-bound to get lower bounds (among other tricks). $\endgroup$ – nikaza Dec 5 '19 at 16:27
  • $\begingroup$ Thanks for your explanations. In docplex.cp, the parameter to state this optimality gap is 'OptimalityTolerance' ? $\endgroup$ – campioni Dec 6 '19 at 9:46
  • $\begingroup$ Just for the record, I think the poster is using CP Optimizer rather than CPLEX, so gap reduction is not exactly what is going on. $\endgroup$ – prubin Dec 7 '19 at 16:19
  • $\begingroup$ @prubin, at first, thanks for your explanations, it has helped me a lot. I've solved with CPLEX and CPO (TimeLimit=10seconds) and I compared both results. Fixing the TimeLimit, CPO is much more faster than CPLEX. I tried to state the gap tolerance in CPLEX, but it did not help to increase the search speed significantly. $\endgroup$ – campioni Dec 9 '19 at 13:50
3
$\begingroup$

CP Optimizer is doing a search for progressively better solutions. Each time it finds a feasible solution, it restricts the remainder of the search to solutions with better objective values than what it just found. So you should get a sequence of progressively better solutions. Given enough time and memory, it will exhaust the search space, and the last solution found will be provably optimal. Stopped early, the last solution found will not necessarily be optimal.

So it sounds as though CPO is finding a good solution in the first 10 seconds and then struggling to find a better one. If the 15 hour run completed the search (i.e., was not stopped by time or memory limits), then that early solution is optimal.

As Geoffrey Brent said, you might have significant symmetry in your model, in which case symmetry-breaking constraints would reduce the size of the search space (and hopefully let CPO terminate sooner). There are also ways you can change the search strategy CPO uses, but if the early solution is actually optimal, I'm not sure that messing with the search strategy will get proven optimality (exhaustion of the search space) any sooner.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.