Search code examples
or-toolsmixed-integer-programming

How to stop MPSolver of Google OR-Tools at the first feasible solution found?

I have a MIP (BP, maximization) that takes too long to compute and I'd like to have MPSolver return the first feasible solution it finds, also, I'd like to know if I use RELATIVE_MIP_GAP solver parameter correctly.
I have tried two things:

Callback

I have searched the docs and have not found a callback possibility for MPSolver's solution iteration process (only for CpSolver) with which one could implement stopping on the first feasible solution found.

Relative gap as termination criterion

I tried using RELATIVE_MIP_GAP like so (this is Kotlin language):

val mpSolverParameters = MPSolverParameters().apply {
    setDoubleParam(MPSolverParameters.DoubleParam.RELATIVE_MIP_GAP, 1.0)
}
solver.solve(mpSolverParameters)

I've seen as a documentation comment somewhere that a 0.05 value for RELATIVE_MIP_GAP means a 5% gap, so 1.0 should denote a 100% gap.
But it did not work. I know it because when I have set a time limit, it returned a solution at the end of the time limit, but when I ran the same problem without a time limit, it just went on and did not return anything even after much more time than when it stopped at the time limit previously.
If I understand relative gaps correctly, if I set a value of 1.0 for this relative gap parameter, the solver should stop at any feasible solution found immediately, because the objective value of any integer solution is inside a 100% relative difference of the objective value for any continuous state of the variables. I should add that my objective function is always positive, so there's no problem of these two having different signs.

Solution remarks

  • Both of Laurent Perron's suggestions work for my case.
  • If using SCIP as the solver, we may call solver.setSolverSpecificParametersAsString("limits/solutions = 1") to get the first feasible solution, but that will be a poor quality one. We may increase this value passed as we see fit.
    Check out time limit too: call setTimeLimit(timeInMs) on your solver object. It will return the best feasible solution found so far, or the unsolved state if no solution has been found at all.
  • Still not sure why RELATIVE_MIP_GAP didn't work, it is part of the API, not a solver specific parameter.
Solution

  • can you try CP-SAT ? Does it fit there ? meaning no continuous variables.

    Can you remove the objective function ?