Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

ENH: Generalizing the branch and bound implementation #16

Open
tuncbkose opened this issue Jun 18, 2024 · 1 comment · May be fixed by #17
Open

ENH: Generalizing the branch and bound implementation #16

tuncbkose opened this issue Jun 18, 2024 · 1 comment · May be fixed by #17
Labels
enhancement New feature or request

Comments

@tuncbkose
Copy link

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
Copy link
Collaborator

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!

@henryrobbins henryrobbins added the enhancement New feature or request label Jun 18, 2024
@henryrobbins henryrobbins changed the title Generalizing the branch and bound implementation ENH: Generalizing the branch and bound implementation Jun 18, 2024
@tuncbkose tuncbkose linked a pull request Jun 20, 2024 that will close this issue
Open
5 tasks
@henryrobbins henryrobbins linked a pull request Jul 17, 2024 that will close this issue
BnB: Add ability to specify integers #17
Open
5 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

BnB: Add ability to specify integers tuncbkose/gilp
2 participants
@tuncbkose @henryrobbins