Help with Implementation of Branch and Benders Cut in GurobiPy
Hello,
I am trying to implement Branch and Benders Cut algorithm using GurobiPy. I do have the problem separated into master and sub problems. Since it is a mixed integer problem I need to implement Branch and Benders cut method. The master problem is pure binary.
The algorithm in short is as follows
- Solve master problem relaxation and add solution to a queue Q (Z,theta)
- Z is obj fn value and x is master problem assignment {0,1}
While Q (not empty)
select Z from Q
if Z > UB: (1)
fathom branch
else if x integer then: (2)
solve relaxed subproblem SP(x) using x assignments
solve heuristic to find integer UB
if SP(x) feasible: (3)
Add standard optimality cut
update UB
save candidate Solution
else: (4)
Add Feasibility Cut
else:(5)
Choose a variable to branch on and add partial solutions to Q
In my problem
- I know how to solve LP relaxation of master
- I know how to solve LP relaxation of subproblems and add benders optimality cuts stated by (3)
- I do not need to worry about adding feasibility cut stated by (4) since the subproblem is always feasible,
The problem however is in statement (2) and statement (5). I do not know how to branch on a particular variable as such and add that node to the queue. I do not know how Gurobi callback and Branching Tree works and do not know how to add cut at each node. Can anyone help me with this? I have a small example that can be used for this problem obtained from thesis by Arthur Maheo.
min 6x1 +10x2 +y1 +2y2
s.t. −15x1 − 22x2 + 5y1 + 8y2 ≤ 0
y1 + y2 ≥ 1.5
x ∈ B,y ∈ {0,1,2}
Where x variables are fixed in master problem and subproblem consists of y variables.
-
Official comment
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?.
Post is closed for comments.
Comments
1 comment