How to combine time and gap limits with Google OR-Tools in Python?

Question

I am using Google OR-Tools with a CBC_MIXED_INTEGER_PROGRAMMING solver.

Most of the time, the solver finds the optimal solution in less than 20 seconds, but sometimes it takes several minutes to find it. It can guess really fast a good estimate of the solution but finding the optimal the solution takes ages.

My first idea was to set a simple time limit to return the best solution found after 30 seconds:

solver = pywraplp.Solver('scheduling_solver', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
solver.SetTimeLimit(30*1000) # 30 seconds time limit

Unfortunately, the solution found at that point might be too far from the optimal solution.

Is it possible to:

1. [00 - 30 seconds] Return the optimal solution if it is found in less than 30 seconds.
2. [30 - 60 seconds] If no optimal solution was found, accept a 5% GAP for 30 additional seconds (GAP LIMIT)
3. [60+ seconds] If the solver is still running after one minute, return the best solution found (TIME LIMIT)

Many thanks in advance,

Romain

Answer 1

The main issue here is to combine the different requirements while respecting the priority of these rules.

This is how I fixed the issue:

1. Run the model with a short TIME limit based on the average time needed to retrieve an optimal solution. For example, if you discard the runs that took more than an minute, the average time to find an optimal solution was around 20 seconds. So we can set the time limit of this first run at 30 seconds.
2. If the first point returns an optimal solution, you can proceed normally. Otherwise, run again the model with the same inputs but with a GAP limit and a much longer TIME. For example, using a 5% GAP for 1 minute would satisfy the requirements of the OP.

Using this strategy, you ensure that:

1. You find the optimal solution if it can be found in less than your first TIME limit.
2. Otherwise, it returns an acceptable solution respecting your GAP limit and second TIME limit.

This is extremely useful when most of the runs can find an optimal solution very fast but get stuck for ages when this is not the case. In particular, when an acceptable solution is easily found.

Cons: you need to run the model twice.

Pros: In my case, the optimal solution is retrieved most of the time instead of always returning the first solution that simply satisfies the GAP limit.

Answer 2

This is strictly not possible with CLP/CBC. At least with the API exposed by OR-Tools, and most probably even with the solver direct API.

Answer 3

A little adjustment to Jorge's answer:

model = pywraplp.Solver('model', pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

# set time limit in milliseconds, both two methods are OK
model.set_time_limit(5000)  
# model.SetTimeLimit(5000)

# set a stopping gap limit for MIP
gap = 0.05
solverParams = pywraplp.MPSolverParameters()
solverParams.SetDoubleParam(solverParams.RELATIVE_MIP_GAP, gap)
status = model.Solve(solverParams)

Note that the gap limit parameter only works for SCIP(and maybe other commercial solvers), not for CBC or SAT.

Answer 4

You can try something like this:

model = pywraplp.Solver('my_model', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# set a time limit to get a solution in milliseconds
model.set_time_limit(60*1000)

# set a minimum gap limit for the integer solution during branch and cut
gap = 0.05
solverParams = pywraplp.MPSolverParameters()
solverParams.SetDoubleParam(solverParams.RELATIVE_MIP_GAP, gap)

In this way the solver will try to find a solution which is limited by either the gap or the time, whichever comes first. The problem here is that the solutions you get are not better than those given by the gap limit because once this limit is hit the solver will stop.