Get accumulated constraints of the LP at the optimal BB node after solving a MIP
Ongoing
Dear all,
I have a question regarding retrieving constraints. Is there any way to obtain the accumulated constraints of the final integer optimal solution? More specifically, how to get the LP (say Ax <= b) at the last BB node in terms of A and b which gives the optimal integer solution?
Many thanks in advance!
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi,
I don't think there is an optimal Branch-and-Bound node. When you solve a MIP the optimal solution is not necessarily found in the last node. Most of the time the solution was found on the way, sometimes in a node and sometimes using a heuristic. Such a heuristic also runs in a node but it more than just solving the LP relaxation of the node. Actually, most nodes in the Branch-and-Bound tree are just solved for proving the optimality of the solution we already have.
If you are interested in the active constraints of you solution, you can look at the constraint attributes and for example query the "slack" attribute.
Best,
Sonja
0 -
-
Hi Sonja,
Is it possible to know if the solution is obtained using heuristic or by branch and bound/cut?
Saying that, if the solution is obtained by branch and bound/cut can we know which node is that? and what constraints exist in that node?
Best,
Araz,
0 -
-
-
Hi Alex,
Is it possible to know if the solution is obtained using heuristic or by branch and bound/cut? Saying that, if the solution is obtained by branch and bound/cut can we know which node is that?
You can figure this out by looking into the section of the log that prints information on the progress of the search tree. Occasionally, an output line might start with "H" or "*" indicating that a new incumbent solution is found either by a MIP heuristic (H) or by branching (*) at the given node count and time. Please check the documentation on MIP Logging for a more detailed explanation of different sections in the log file.
and what constraints exist in that node?
I am not sure what you mean here. If you are interested to know which constraints are active at the current solution, you can query the Slack (QCSlack) attribute on each linear (quadratic) constraint, as mentioned in the above post.
Best regards,
Maliheh
0 -
-
Thank for this response.
I had a look to the documentation and they are for C, C++, python and ...
I scripted my code in Julia and it looks like there is no documentation for Julia. Does it mean if I want to query Slack from Gurobi I should re-script my code in one of the existing languages (C, C++, python and ...)
Best,
Alex,0 -
-
-
Hi Alex,
The documentation of Gurobi.jl, the wrapper for the Gurobi Optimizer, has a section on Accessing Gurobi-specific attributes via JuMP. See the script below on how to query the Slack attribute for the constraint c, for example:
model = direct_model(Gurobi.Optimizer())
@variable(model, x >= 0)
@constraint(model, c, 2x >= 1)
@objective(model, Min, x)
optimize!(model)
MOI.get(model, Gurobi.ConstraintAttribute("Slack"), c) # Should output 0.0
# Or, query the LHS value of the constraint c and then find the Slack yourself
value(model[:c]) # Should output 1If you are mainly interested in using Gurobi and no other solver, it would be definitely easier if you consider implementing your code using one of Gurobi's API directly.
Best regards,
Maliheh
0 -
-
Hi Maliheh,
Please accept my apologies as I could not express myself clearly.
The story is I am working on a two stage integer stochastic problem.
To solve a two stage linear stochastic problems we use benders decomposition approach as dividing the problem into one master problem and one sub problem. First, we solve the master problem. Second, we put the obtained values from the master problem into the sub problem and solve the sub problem. Then we get the simplex multiplier of the sub problem and generate a benders cut. This method works well in linear two stage stochastic problems.
However, my problem is an integer stochastic problem and therefore I cannot get the dual from the second stage. Reviewing literature I recognized people relax the second stage problem and solve it with branch and bound and get the dual from the relaxed problem.
For example, let say this is our problem:
min 3 x1 + 7 x2 + 9 x3 + 6 x4
s.t. 2 x1 + 4 x2 + 5 x3 + 3x4 >= 7
x1,x2,x3,x4 = binary
Which have the following solution:
x = [1, 0 ,1 , 0]
If we relax this problem and solve it using branch and bound in the node including the optimal solution the problem would be
min 3 x1 + 7 x2 + 9 x3 + 6 x4
s.t. 2 x1 + 4 x2 + 5 x3 + 3x4 >= 7
x1 >= 1
x2 <= 0
x3>= 1
x4 <= 0
0 =< x1,x2,x3,x4 =< 1
It is what I need. This problem is linear and we can get the dual from it.
Is there any way of getting this problem?
All the best and thanks a lot for the help.
Alex,
0 -
-
-
Hi Alex,
You cannot query the LP relaxation model solved at each node. However, given your explanation, I think you can do the following:
- Optimize your original MIP problem
- Get the continuous fixed model by fixing the integer variables at their optimal values (see Model.fixed())
- Optimize the fixed model and query the dual values
See the script below for an implementation of the idea above using the simple example you provided:
m = gp.Model("")
x1 = m.addVar(vtype=GRB.BINARY, name="x1")
x2 = m.addVar(vtype=GRB.BINARY, name="x1")
x3 = m.addVar(vtype=GRB.BINARY, name="x3")
x4 = m.addVar(vtype=GRB.BINARY, name="x4")
m.addConstr(2 * x1 + 4 * x2 + 5 * x3 + 3 * x4 >= 7, name="c")
m.setObjective(3 * x1 + 7 * x2 + 9 * x3 + 6 * x4)
m.optimize()
fixed = m.fixed()
fixed.optimize()
print(fixed.getAttr("Pi", fixed.getConstrs()))Following this post in the Julia forum, you can implement the above in Julia using the function \(\texttt{get_fixed_model()}\). I followed this post and I was able to implement your example in Julia.
Best regards,
Maliheh
0 -
Post is closed for comments.
Comments
8 comments