Originally posted by: Michael C

I'm using the solution polishing heuristic for a particular problem and as you know, it is not effective at proving optimality. But say you know the optimal objective value ahead of time. Is it possible to specify that the solver stops after it reaches a given objective value? Relative and absolute gap aren't a good option here since the upper/lower bound that the solver finds aren't always the same when using the solution polishing heuristic. Please give advice for python, if possible.

Thanks!

Hi

you could try cutoff

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/CutLo.html

The cutoff will probably not achieve what was intended, since it cuts off any solution worse than the cutoff. It will not make CPLEX stop as soon as a solution of certain quality is found.

Would it be an option to use a callback? In a callback you could easily query the current best known solution and compute your own gap (based on the known optimal value). Then you can abort the search from the callback if the gap is small enough.

Let's say you are minimizing f(x). Suppose you add a variable z to the model, set z = f(x) in a constraint, and set a lower bound on z equal to your desired stopping value (the known optimum, or possibly something a bit larger). The solver will stop when it hits or approaches that bound, (You will need to set the absolute and relative MIP gaps to zero, or close to zero.) For maximizing, do the same but fix the upper bound of z.

The bound set on z may affect preprocessing and decision making in the branch and cut algorithm. Depending on your luck, it might speed solution, or it might slow it down.

Originally posted by: Michael C

Paul's advice is working quite well for me. I always thought it was a bad idea to add a constraint like this so it didn't cross my mind to try, so I am happy you suggested it. Thank you all for your input.

Your "bad idea" impression is generally correct. It's a bad idea to add a constraint f(x) ~ b (where ~ is any of >=, =, <=) while optimizing f(x), because having the same linear expression in the objective function and as a constraint causes dual degeneracy. Fortunately, the "cheat" of using a variable as the objective function and setting one of its bounds doesn't seem to cause as much damage (charitably assuming that the presolver doesn't remove it and revert to the previous case). Glad it's working for you.