How to generate lower bounding constraints ?
Awaiting user input
Hello,
I would like to implement a branch-and-cut decomposition by minimizing a lower bounding variable z. The idea is to solve a relaxed version of my model (*) and then iteratively modify it by integrating lower bounding constraints on z (**).
(*)
(**)
I have therefore looked into the Model.cbCut() but my problem is that when I solve the relaxation of my problem, I never enter the condition where == GRB.Callback.MIPNODE. How can I model this feature ?
Thank you.
Sophie
-
Hi Sophie,
Could you share a code snippet of how you are currently trying to implement the callback?
Best regards,
Jaromił0 -
Hi Sophie,
Maybe the Gurobi example callback.py is helpful to see how a callback is included.
Best regards,
Marika0 -
Hi Jaromil, Marika,
I don't have difficulties to include a callback. It actually enters the callback, what it does not is to enter the condition where ==
GRB.Callback.MIPNODE. Anyways, here is my code snippet, but I don't think the error comes from there:def mycallback(model, where):
if where == GRB.Callback.MIPNODE:
status = model.cbGet(GRB.Callback.MIPNODE_STATUS)
if status == GRB.OPTIMAL:
rel = model.cbGetNodeRel(self.x_vars)
fx = f(rel)
model.cbCut(self.z >= fx)
model = createModel()
model.optimize(mycallback)0 -
Hi Sophie,
Could you also show the Gurobi log when you run your code? Are there any nodes in the B&B?
Best regards,
Jaromił0 -
Hi Jaromil,
Yes that's the thing. No nodes are displayed at all. The model finds an optimal solution and stops. Thank you for your follow up.
Gurobi 9.5.0 (linux64) logging started Thu Jun 9 17:52:36 2022
Set parameter LogFile to value "bb_cuts.log"
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 40 physical cores, 80 logical processors, using up to 8 threads
Optimize a model with 7211 rows, 6998 columns and 2425072 nonzeros
Model fingerprint: 0xd77be502
Variable types: 6637 continuous, 361 integer (361 binary)
Coefficient statistics:
Matrix range [6e-04, 2e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 2e+01]
RHS range [6e+01, 6e+01]
Warning: Completing partial solution with 361 unfixed non-continuous variables out of 361
User MIP start did not produce a new incumbent solution
User MIP start violates constraint GTV2_minConstr[0] by 56.000000000
Presolve removed 6635 rows and 693 columns (presolve time = 5s) ...
Presolve removed 6635 rows and 693 columns (presolve time = 10s) ...
Presolve removed 6635 rows and 693 columns
Presolve time: 11.93s
Presolved: 576 rows, 6305 columns, 2411802 nonzeros
Variable types: 6305 continuous, 0 integer (0 binary)
Root barrier log...
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 4.133e+04
Factor NZ : 4.162e+04 (roughly 3 MB of memory)
Factor Ops : 8.004e+06 (less than 1 second per iteration)
Threads : 8
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 0.00000000e+00 -4.69047754e+02 7.60e+03 0.00e+00 5.47e-01 17s
1 0.00000000e+00 -3.58632418e+02 7.86e+02 9.71e-17 7.41e-02 17s
2 0.00000000e+00 -8.63793196e+01 6.15e+01 2.57e-16 9.07e-03 17s
3 0.00000000e+00 -1.54655594e+01 5.22e+00 3.40e-16 1.31e-03 17s
4 0.00000000e+00 -8.33221405e-01 1.49e-13 2.03e-16 6.32e-05 17s
5 0.00000000e+00 -8.33221405e-04 4.26e-14 2.86e-17 6.32e-08 17s
6 0.00000000e+00 -8.33221405e-07 5.51e-14 2.69e-20 6.32e-11 17s
7 0.00000000e+00 -8.33221405e-10 6.39e-14 3.63e-23 6.32e-14 17s
Barrier solved model in 7 iterations and 16.84 seconds (3.49 work units)
Optimal objective 0.00000000e+00
Root crossover log...
3 DPushes remaining with DInf 0.0000000e+00 17s
6308 PPushes remaining with PInf 0.0000000e+00 17s
0 PPushes remaining with PInf 0.0000000e+00 17s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 17s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
6311 0.0000000e+00 0.000000e+00 0.000000e+00 17s
6311 0.0000000e+00 0.000000e+00 0.000000e+00 17s
Root relaxation: objective 0.000000e+00, 6311 iterations, 2.70 seconds (1.36 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
* 0 0 0 0.0000000 0.00000 0.00% - 17s
Explored 1 nodes (6311 simplex iterations) in 17.26 seconds (3.66 work units)
Thread count was 8 (of 80 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
User-callback calls 499, time in user-callback 0.03 sec
Gurobi 9.5.0 (linux64) logging started Thu Jun 9 17:53:30 2022
Set parameter LogFile to value "bb_cuts.log"
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 40 physical cores, 80 logical processors, using up to 8 threads
Optimize a model with 7211 rows, 6998 columns and 2425072 nonzeros
Model fingerprint: 0xd77be502
Variable types: 6637 continuous, 361 integer (361 binary)
Coefficient statistics:
Matrix range [6e-04, 2e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 2e+01]
RHS range [6e+01, 6e+01]
Warning: Completing partial solution with 361 unfixed non-continuous variables out of 361
User MIP start did not produce a new incumbent solution
User MIP start violates constraint GTV2_minConstr[0] by 56.000000000
Presolve removed 6635 rows and 693 columns (presolve time = 5s) ...
Presolve removed 6635 rows and 693 columns
Presolve time: 8.27s
Presolved: 576 rows, 6305 columns, 2411802 nonzeros
Variable types: 6305 continuous, 0 integer (0 binary)
Root barrier log...
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 4.133e+04
Factor NZ : 4.162e+04 (roughly 3 MB of memory)
Factor Ops : 8.004e+06 (less than 1 second per iteration)
Threads : 8
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 0.00000000e+00 -4.69047754e+02 7.60e+03 0.00e+00 5.47e-01 12s
1 0.00000000e+00 -3.58632418e+02 7.86e+02 9.71e-17 7.41e-02 12s
2 0.00000000e+00 -8.63793196e+01 6.15e+01 2.57e-16 9.07e-03 12s
3 0.00000000e+00 -1.54655594e+01 5.22e+00 3.40e-16 1.31e-03 12s
4 0.00000000e+00 -8.33221405e-01 1.49e-13 2.03e-16 6.32e-05 12s
5 0.00000000e+00 -8.33221405e-04 4.26e-14 2.86e-17 6.32e-08 12s
6 0.00000000e+00 -8.33221405e-07 5.51e-14 2.69e-20 6.32e-11 12s
7 0.00000000e+00 -8.33221405e-10 6.39e-14 3.63e-23 6.32e-14 12s
Barrier solved model in 7 iterations and 12.30 seconds (3.49 work units)
Optimal objective 0.00000000e+00
Root crossover log...
3 DPushes remaining with DInf 0.0000000e+00 12s
6308 PPushes remaining with PInf 0.0000000e+00 12s
0 PPushes remaining with PInf 0.0000000e+00 12s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 12s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
6311 0.0000000e+00 0.000000e+00 0.000000e+00 12s
6311 0.0000000e+00 0.000000e+00 0.000000e+00 13s
Root relaxation: objective 0.000000e+00, 6311 iterations, 2.56 seconds (1.36 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
* 0 0 0 0.0000000 0.00000 0.00% - 12s
Explored 1 nodes (6311 simplex iterations) in 12.74 seconds (3.66 work units)
Thread count was 8 (of 80 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
User-callback calls 444, time in user-callback 0.01 sec0 -
Hi Sophie,
Gurobi is able to get rid of all discrete variables in the presolve step.
Presolved: 576 rows, 6305 columns, 2411802 nonzeros
Variable types: 6305 continuous, 0 integer (0 binary)Thus, your model is essentially an LP. Gurobi recognizes that and solves it is an LP. The logging is still MIP logging because the original problem is a MIP. You could try checking for the MIPSOL callback instead of the MIPNODE callback. Alternatively, you could turn off Presolve.
Best regards,
Jaromił0 -
Hi Jaromil,
I tried both solutions you proposed and it does not change anything, it still solves the LP and stops there.
Using mipsol call back, it complains I don't use MIPNODE while using cbGetNodeRel and cbCut
Error code 10011: where != GRB.Callback.MIPNODE.
Setting presolve=0, did not impact , see log below
Gurobi 9.5.0 (linux64) logging started Fri Jun 10 14:49:01 2022
Set parameter LogFile to value "bb_cuts.log"
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 40 physical cores, 80 logical processors, using up to 8 threads
Optimize a model with 7211 rows, 6998 columns and 2425072 nonzeros
Model fingerprint: 0xd77be502
Variable types: 6637 continuous, 361 integer (361 binary)
Coefficient statistics:
Matrix range [6e-04, 2e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 2e+01]
RHS range [6e+01, 6e+01]
Warning: Completing partial solution with 361 unfixed non-continuous variables out of 361
User MIP start did not produce a new incumbent solution
User MIP start violates constraint GTV2_minConstr[0] by 56.000000000
Variable types: 6637 continuous, 361 integer (361 binary)
Root relaxation: objective 0.000000e+00, 913 iterations, 0.56 seconds (0.59 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
H 0 0 0.0000000 0.00000 0.00% - 1s
0 0 0.00000 0 14 0.00000 0.00000 0.00% - 1s
Explored 1 nodes (913 simplex iterations) in 1.70 seconds (0.84 work units)
Thread count was 8 (of 80 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
User-callback calls 63, time in user-callback 0.00 sec0 -
Could you please share the model? We discuss an option of sharing files in the Community in Posting to the Community Forum.
0 -
Sure. Here is a link. Thank you for your help.
0 -
The issue is indeed that your model is too easy to solve for the solver such that it terminates before getting to the first MIPNODE callback.
You could try taking the solution of the first solve, i.e., the solution point with objective value 0 you get right now, and add the first constraint \(z \geq f(x)\) to the model a priori.
Are you sure that the model should be such that all discrete variables can be presolved? Is it possible that the currently obtained solution is already the optimal one, which you would get from your algorithm?
0 -
I see. Well here is the thing, I have tried a model where I was trying to minimize a function \(f'\) directly representing a linear combination of binary variables associated with additional flow constraints. However, this old model was really hard to solve for bigger instances and the MIP run indefinitely to find even one single feasible solution. This is why we thought we could instead solve the relaxed problem (which is an easy problem for Gurobi) and then iteratively add constraints (optimality cuts) on this new variable \(z\) gradually tightened upward in the course of the algorithm, approaching the objective function from below.
The currently obtained solution is optimal if we take into account only the continuous part of the problem but is definitely not the optimal one in terms of \(f\) result, that I am sure. I guess I am missing something here but I don't know what.
Could you extrapolate when you write "add the first constraint to the model a priori" ? I am not able to translate my new function \(f\) in the model itself because it not linear anymore.. In addition if I use the solution found with objective 0 and add the constraint, it will be violated directly and the mip start won't be processed.
0 -
Could you extrapolate when you write "add the first constraint to the model a priori" ?
My suggestion would be that you solve your current model to optimality first. Then extract the optimal solution point values via accessing the X attribute. Once you have the X values of the optimal solution point, you can apply your nonlinear function \(f\) to compute whatever you are computing. Next, you add the next constraint \(z \geq f(x)\) to your model and re-solve the model.
A possible Python code might look something like
model.optimize()
if m.Status == GRB.OPTIMAL:
rel = model.getAttr("X",model.getVars())
fx = f(rel)
model.addConstr(self.z >= fx)
model.optimize()The above can be done in a loop to iterate until some termination criterion is met.
I am not able to translate my new function in the model itself because it not linear anymore..
Could you briefly explain what your \(f\) function does? From your code, I would guess that the result of \(\texttt{f(rel)}\) is just some real number. If this is true, then you can apply my suggestion as described above.
In addition if I use the solution found with objective 0 and add the constraint, it will be violated directly and the mip start won't be processed.
This is correct, but the same would happen if you would cut off the solution via lazy constraints. I think it might be worth a try, given the fact that your starting model seems to be easy to solve.
0
Please sign in to leave a comment.
Comments
12 comments