ENH: Generalizing the branch and bound implementation

[tuncbkose]

Hi, I wanted to visualize LPs and the simplex algorithm and discovered this package. It has been great so far so thanks for that.

I'd like to use it for MILPs as well, but I noticed that the provided branch and bound implementation assumes all decision variables are integers. It seems to me that the branch_and_bound_iteration and branch_and_bound functions could naively be extended, by having a mask to indicate which indices are integers. I hacked an implementation quickly and with very limited testing it seems to work fine, but I have two questions:

1. What is happening in this if statement? I only have a high-level understanding of the algorithm so this may be silly/simple, but it is not clear to me why a new variable is added.
2. The visualization code seems somewhat separate than the code in simplex.py and I wasn't immediately sure if a similar hack is feasible there. Do you have any thoughts?

[henryrobbins]

Hey -- I'm glad you've been enjoying the package! Extending to MILPs is a great idea. Hack or not, I encourage you to create a PR so others can benefit from your work. I'm happy to work with you to get your implementation merged in. In the mean time, here are quick answers to your questions:

1. The idea here is to keep the LPs for each sub-problem of the branch in the same form as the parent LP. For a standard inequality form LP, it suffices to add a constraint of the form $x_i <= b$. But, for a standard equality form LP, we need to add $x_i + s = b$. The if statement you mention is adding a slack variable to the new constraint if the LP is in standard equality form.
2. I don't like how coupled the current bnb_visual implementation is with the logic of the algorithm. This should be refactored. I'd need to think about this a little more; you're welcome to take a first crack if you're interested!