Rejecting MIP Solutions without lazy cuts
Answered
Hi,
I am working in a framework similar to benders decomposition. I use lazy cuts and callbacks for cutting new integer solutions that are not feasible considering a subproblem. Such lazy cuts just cut the integer solution presented by the callback (on MIPSOL status) and will not cut any other solutions or strengthen the model. Currently, my bottleneck is that, after some time, the solver begins to take more and more time between one call to callback and the next. I have solved part of the problem by fixing the objective function to the upper bound (it is a maximization problem), solving for that unit of the objective function, discovering that all ten thousand solutions with that same objective function value are invalid for the subproblem, and then reseting the model and do the same for the solutions in which the objective function value is one less. However, some units of the objective function have more than ten thousand solutions, and the lazy cuts seem to accumulate and clog the model, and as the objective function has not lowered a single unit, I cannot reset the model yet (immediately after reset the model is considerably faster, the long times between callbacks always happen after many lazy cuts were added, never at the beggining).
What I would like is the ability to, instead of adding a lazy cut, just tell the solver to reject the presented incumbent and forget that branch/subtree. This is something I could do if I re-implemented the master problem as a manual branch-and-bound in C++, but I can't seem how to do this on Gurobi.
I am, however, open to other suggestions on how to solve this problem.
Thanks for the attention,
Henrique Becker
-
Official comment
Sadly it is currently not possible to "just" reject solutions. I guess by adding so many lazy constraints the LP becomes hard?!
Do you know if a valid solution exists, i.e., one you would not cut off? Does such a valid solution has some property that you could exploit?
Best, Michael
-
Thanks for the fast answer.
I do not know if there exists a valid solution on the specific value unit of the objective function and, as this method is a dual method (starts at an upper bound of a maximization problem, with not-sure-if-feasible solutions but optimal-if-feasible), then the first time I find a feasible solution it will be optimal and the algorithm will stop. The 99.99% of the cases will be of infeasible solutions as just one feasible is necessary and it would be a easy problem if I needed a small number of iterations.
I am interested in an optimal solution because I am PhD student and this is the topic of my thesis.
There will always be at least one optimal solution (if not many of them) and many suboptimal solutions (all valid). Such valid solutions clearly have some special property that is returning true for the sub-problem (XD), however putting the subproblem in the model itself (abandoning the benders decomposition) creates a model with big-Ms and horrid performance (we already tried many "pure" models). The subproblem, however, can be fastly solved for a specific not-sure-if-valid solution of the master problem by using CP and thus this bender's decomposition is much faster than any model we tried for medium-sized instances. Given the problem I explained in the initial post, solving the big instances with bender's decomposition is slow and I would not even date to dream of solving them with a pure model. I should probably find a way to strengthen the master problem model (reduce the number of invalid solutions it discovers) slowing it so much that I lose what I gain with the reduced number of iterations.
I discovered that CPLEX allows to "just reject", I sincerely prefer the Gurobi API and do not like IBM very much, but seems for this case I will need to migrate the technology I use.
0 -
Hello,
There are other instances where rejecting a MIP solution by "just" reject is very useful! Suppose you require a variable "matrix" to be invertible for a size bigger than 10. Writing determinant different from 0 is neither easy nor tractable (even though multilinear in the varying entries of the matrix); however, knowing a MIP solution for the varying matrix, then computing its determinant is easy and rejecting this solution whenever the determinant is 0 easy too. As a special case, constraining the variable matrix to be unimodular (det=\pm 1) could be handled the same way but i do not know how to introduce lazy cuts to do so.
As H. Becker wrote, it was available under CPLEX to just "reject" a MIP solution thru MIPnodeCallback.
Is there a chance to consider again this capability?
Best regards,
D. Fortin
0 -
Hi Dominique,
We track requests like this internally and add them for consideration into our roadmap. We have included your thoughts on this particular request. Thank you for taking the time to provide the motivation. If this feature is added in the future I expect we will notify you.
Kind Regards,
Riley0 -
Hi Riley,
i tried a workaround with lazyconstraint callback to remember MIP solutions such that the determinant is different from 0; however, i could not prevent that a bad MIP solution (corresponding to a determinant 0) being active as a solution wrt the pruning process so that the B&B finishes before exploring the true MIP solution (determinant not 0). I understand that this request should be incorporated to your roadmap, so this message id just to argue in favor of rejecting a MIP solution on behalf in the end user (afterall, the workaround mentioned above is not satisfactorily too).
best,
Dominqiue
0
Please sign in to leave a comment.
Comments
5 comments