Incumbent solution is not updated after optimality cut
ユーザーの入力を待っています。Dear Gurobi staff,
I try to understand the behaviour of the Gurobi Solver for a standard Benders Decomposition with lazy callback optimality cuts.
I have a multi-period (t) and multi-scenario (s) problem.
I have a mixed integer master problem (MP) and a standard LP subproblem, which depends on two integer variables of the MP.
Gurobi found a feasible incumbent solution in the callback and adds an optimality cut for my theta(t,s) variables, if the estimate is off. I then add the lazy cut: model.cbLazy(expr≤theta)
However, in early iterations, the solution seems to be forgotten and the incumbent solution is not updated. Then at some points it retries an updated solution and may accept it finally like you can see in my log. I observed that in some instances it never seem to find an initial imcumbent solution, even when adding multiple optimality cuts.
Is this a bug or can I do something to prevent this behaviour?
-
Btw, when I fix the solution to the first cut for the instances where Gurobi does not find any incumbent solution, then it “finds” the solution, but just after two cut loops. This seems a bit weird to me.
Set parameter Username Set parameter LicenseID to value 2623598 Academic license - for non-commercial use only - expires 2026-02-18 Set parameter TimeLimit to value 3600 Set parameter Threads to value 8 Set parameter PreCrush to value 1 Set parameter LazyConstraints to value 1 Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (win64 - Windows 11.0 (22621.2)) CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz, instruction set [SSE2|AVX|AVX2] Thread count: 4 physical cores, 8 logical processors, using up to 8 threads Non-default parameters: TimeLimit 3600 PreCrush 1 Threads 8 LazyConstraints 1 Optimize a model with 21016 rows, 10661 columns and 70708 nonzeros Model fingerprint: 0xcb00ef7d Variable types: 569 continuous, 10092 integer (10092 binary) Coefficient statistics: Matrix range [1e+00, 1e+03] Objective range [1e+00, 3e+03] Bounds range [1e+00, 1e+00] RHS range [1e+00, 6e+02] Adding optimality cut theta(1, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(2, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(3, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(4, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(5, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(6, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(1, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(2, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(3, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(4, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(5, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(6, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(1, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(2, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(3, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(4, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(5, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(6, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(1, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(2, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(3, 4) with violation 1855.2, incumbent obj 228269.0, check sum of cut 1855.2 Adding optimality cut theta(4, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(5, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(6, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(1, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(2, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(3, 5) with violation 884.2999999999998, incumbent obj 228269.0, check sum of cut 884.2999999999998 Adding optimality cut theta(4, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(5, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(6, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Presolve removed 21016 rows and 10631 columns Presolve time: 0.02s Presolved: 0 rows, 30 columns, 0 nonzeros Variable types: 30 continuous, 0 integer (0 binary) Root relaxation: objective 2.282690e+05, 0 iterations, 0.00 seconds (0.00 work units) Adding optimality cut theta(1, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(2, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(3, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(4, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(5, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(6, 1) with violation 1069.4, incumbent obj 228269.0, check sum of cut 1069.4 Adding optimality cut theta(1, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(2, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(3, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(4, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(5, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(6, 2) with violation 2034.1999999999998, incumbent obj 228269.0, check sum of cut 2034.1999999999998 Adding optimality cut theta(1, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(2, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(3, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(4, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(5, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(6, 3) with violation 3885.9999999999995, incumbent obj 228269.0, check sum of cut 3885.9999999999995 Adding optimality cut theta(1, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(2, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(3, 4) with violation 1855.2, incumbent obj 228269.0, check sum of cut 1855.2 Adding optimality cut theta(4, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(5, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(6, 4) with violation 1855.1999999999998, incumbent obj 228269.0, check sum of cut 1855.1999999999998 Adding optimality cut theta(1, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(2, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(3, 5) with violation 884.2999999999998, incumbent obj 228269.0, check sum of cut 884.2999999999998 Adding optimality cut theta(4, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(5, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Adding optimality cut theta(6, 5) with violation 884.3, incumbent obj 228269.0, check sum of cut 884.3 Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 228269.000 0 - - 228269.000 - - 8s * 0 0 0 286643.60000 286643.600 0.00% - 11s Cutting planes: Lazy constraints: 30 Explored 1 nodes (0 simplex iterations) in 11.63 seconds (0.01 work units) Thread count was 8 (of 8 available processors) Solution count 1: 286644 Optimal solution found (tolerance 1.00e-04) Best objective 2.866436000000e+05, best bound 2.866436000000e+05, gap 0.0000% User-callback calls 155, time in user-callback 11.59 sec0 -
-
Can I get any feedback on that request? I notice this problem especially on 2 instances. It seems that gurobi adds the cut and immediately forgets that this solution exists.
0 -
-
-
Gurobi Staff
Hi,
After reading this a few times I'm still not clear on what the problem is. I would guess others feel the same and perhaps that is why there has been no activity.
the solution seems to be forgotten and the incumbent solution is not updated
In particular I'm not sure what “seems to be forgotten” is referring to, can you explain as simply as possible?
- Riley
0 -
-
Dear Riley,
thanks for asking!
- Gurobi finds an incumbent solution in the Master Problem
- The Benders Subproblem is solved in the MIPSOL callback
- An optimality cut is generated because the theta estimates in the master problem are wrong, and the solution is rejected
- I expect Gurobi to retry the solution again and then accept it at some point, because the added optimality cuts should fix the wrong theta estimates
- But in some big instances, with many time periods, Gurobi never retries the checked solutions and seems to forget that they exist. Leading to the case, where no feasible solution is ever reported after the solving time ends
In the meantime, I found a slightly hacky solution: I store the incumbent solution in a pool and reinject it into a delayed MIPNODE callback in case Gurobi has not found it before. It is expensive because I must also set all the correct theta estimates to make Gurobi accept the solution.
Hope the issue is now clearer.
0 -
-
-
Hi,
I think this phrasing is problematic:
Gurobi never retries the checked solutions and seems to forget that they exist
If you added a lazy constraint then the solution (which includes thetas) is going to be cut off (i.e. it is infeasible), and a solver is not going to keep track of infeasible solutions.
If I understand correctly it sounds like you're suggesting the partial solution, corresponding to integer variables in the master, should be kept and then later completed (multiple times?) to a new feasible solution to derive new theta values (and this would only work for the optimality cuts). In general I don't think this is broadly useful, but I can see how it might be useful for Bender's decomposition. I think your “hacky solution” is the way to do it - I'm not sure you need to use a MIPNode callback though, I would try immediately using Model.cbSetSolution with your partial solution, after using cbLazy to add an optimality cut.
- Riley
0 -
サインインしてコメントを残してください。
コメント
5件のコメント