Constraint programming using solver: how to state the time limit of search?

Question

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?

Answer 1

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 10¹³ 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.

Answer 2

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.

Answer 3

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.