Skip to main content

Implementation of n-ary branching or multiway branching in gurobipy

Ongoing
Montree Jaidee
  • Gurobi-versary
  • First Comment
  • First Question

Hi,

I am new to write a code with Gurobi API on python. I would like to implement branching strategy for solving a MIP problem. Assume that I want to solve the problem Min cx subject to Ax >= B, where x is an integer variable. First, the relaxation is solved to obtain a point x_0. Then, I need to branch into n nodes, say n=4. In each node, a different cut derived from point x_0 is added (a1*x >= b1 is added in node 1, a2*x >= b2 is added in node 2) and then problem relaxation at that node is solved. Then, the problem is solved in the same way as branch-and-bound algorithm.

I am not sure how should I implement the code. Could you please give me some advice? I think it might need to call it through callback function somehow.

Thanks!

Montree

Related to

0

Comments

3 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support.
  • Maliheh Aramon
    • Gurobi Staff

    Hi Montree, 

    Gurobi does not support branching and node selection callbacks. In other words, the user cannot control the branching and node selection decisions in Gurobi. 

    If the derived cuts based on the root relaxation solution are globally valid, you can consider adding them via the Model.cbCut() method in the MIPNODE callback.

    Best regards,

    Maliheh

    0
  • Montree Jaidee
    • Gurobi-versary
    • First Comment
    • First Question

    Dear Maliheh,

    My supervision talked to his another student and he suggested to split the nodes by binary branching as follows: Assume we want to branch node R into 4 nodes, we first create a left node as N1 and a right node as Not N1. Then, on the right node we branch it into N2 and Not N2. Finally, on the most right node is branched as N3 and N4.

    The next step is to check the node data if the current node is the node we are interesting to solve or not, say check if the node is Not Ni or not. 

    Do you have any suggestion how can I attach this custom data to nodes or check them?

    Best,

    Montree

    0

Post is closed for comments.

Didn't find what you were looking for?

New post