JuMP: Setting an absolute bound stopping criterion for MIP

[Frans de Ruiter]

Hi all,

As the core developers of JuMP already know, I have become a fan of JuMP at the beginning of this year. I am very grateful for their work and introducing me to JuMP. I have an issue now with writing a callback function and I believe that JuMP is very well capable of handling it. I just do not know how to do it in a neat way.

There are many stopping criteria for solvers, such as the relative or absolute gap between the upper and lower bound, that can be set with standard parameters. In Gurobi examples of these parameters are MIPGap and MIPGapAbs. I want a different criterion. Namely, I want to stop solving my minimization problem when the current solution drops below a certain absolute value or when the lower bound exceeds a certain absolute value.

Surprisingly, and to the best of my knowledge, there is no parameter in the most popular solvers (Gurobi, Cplex) to set my absolute bound stopping criteria. These stopping criteria are for instance useful when you are satisfied with any solution that has an objective value smaller than zero. Also, once the lower bound is larger than zero I know that there do not exist such solutions and I can just as well stop the solver process. This feature is also asked for in many other languages (a small sample: google groups: [1], [2], [3], [4], [5],  Cplex FAQ: [6]). For AMPL they suggest (for the upper bound) to set the CutOff parameter to 0 and the SolutionLimit to 1, or to turn the problem into a feasibility problem. Both of these approaches have serious disadvantages.

Fortunately JuMP has some support for callbacks! In pseudo code, the callback should do the following:

Callback for Absolute Stopping criterion (treshold 0):

1. Query objective value (objval), lower bound (LB) and current solution.
   
2. If objval < 0 or LB > 0, then return the values above and gently stop the solver process.

When I tried to implement this callback in JuMP I ran into a few difficulties, namely:

• In the JuMP callback documentation it is advised to use throw(CallbackAbort()) to exit the optimization process earlier than a solver would. I want the solver process to be stopped in a "gentle" way. With "gentle" I mean that the solver stops the same way as it would stop with a parameter setting, so not by throwing an error. 
  
• cbgetobj(cb) is not callable in the state :MIPSol and cbgetmipsolution(cb) is not callable in state :MIPInfo.

I came up with the following haphazard implementation. It does work, but any comments or suggestions to implement this in a better/more neat way are highly appreciated.

# Above here a model 'm' with (mixed) integer variables x have been defined and objective function 'dot(c,x)'.

type solutionInfoType
    obj
    bestbound
    solution
end

solutiondata = solutionInfoType(Inf,-Inf,NaN)

function AbsoluteStoppingCriterion(cb)
        currentsol       = getValue(x)
        currentobj       = dot(c,currentsol)    #MathProgBase.cbgetobj(cb) does not work in state MIPSol.
        currentbestbound = MathProgBase.cbgetbestbound(cb)

        # If current best integer solution drops below 0 or lower bound
        # exceeds 0, then stop.
        if currentobj <= 0 || currentbestbound >= 0
            solutiondata = solutionInfoType(currentobj,currentbestbound,currentsol)
            # Make the problem obviously infeasible so that the optimization process is "gently" exited
            # Non gentle alternative: throw(CallbackAbort())
            @addLazyConstraint(cb, x[1] >= 1)
            @addLazyConstraint(cb, x[1] <= 0)
       end
end

addLazyCallback(m, AbsoluteStoppingCriterion)

- Frans

(PS (minor) remark: The link to the MathProgBase callback documentation in the JuMP callback documentation does not work.)

[Miles Lubin]

Hi Frans,

Try out this code here: https://github.com/JuliaOpt/Gurobi.jl/pull/48 (by running Pkg.checkout("Gurobi","cbterminate")). I think you're right that requesting the solver to terminate from inside a callback shouldn't result in ugly error messages. Maybe we need multiple ways to stop the solver from a callback, one which is for true error cases and one which is for user termination criteria?

Miles

[Frans de Ruiter]

Hi Miles,

Thanks for the quick response and the nice solution, this works like a charm! Perhaps I am biased now, but I would be in favor of stopping the solver with this new terminate(), because I am instructing the solver to terminate early. I could even print an error message after terminating the solver process if I want to.

The only (arguably) strange syntax still in my code is the addLazyCallback function, which ensures that the callback is in a :MIPSol state. Clearly, I am not adding any lazy constraints in this callback anymore.

- Frans

[Miles Lubin]

You should be able to use addInfoCallback for this. You can decide to check for termination or not based on the solver state.

[Frans de Ruiter]

Ah I see. My problem was that cbgetmipsolution can only be called in state :MIPSol. But there is no need to extract the solution here, I can just get the solution with getValue(x) after I have terminated the solver process of course.

Thanks again Miles! And I heard you are also going to the Optimization Days conference in Montreal, so I will see you there again.


For other people interested in this (or similar) user termination criteria the callback is now simply the following:

# Above here a model 'm' with (mixed) integer variables x have been defined. Use Pkg.checkout("Gurobi","cbterminate") to ensure that not an error is thrown, but the solver process is gently terminated.

function AbsoluteStoppingCriterion(cb)
   currentobj       = MathProgBase.cbgetobj(cb)

   currentbestbound = MathProgBase.cbgetbestbound(cb)

   # If current best integer solution drops below 0 or lower bound
   # exceeds 0, then stop.
   if currentobj <= 0 || currentbestbound >= 0

     throw(CallbackAbort())
   end
end

addInfoCallback(m,AbsoluteStoppingCriterion)

- Frans