# 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.

Please sign in to leave a comment.

## Comments

0 comments