Integer programming sandbox
Solve a small integer linear program with exact branch and bound and see every node of the search. The best point is reported as proven optimal only when the whole tree has been explored.
Programs are limited to 4,000 characters and 40 lines, 8 variables and 8 constraints with two or more variables; the node limit is 1 to 5,000 and the search also stops after 3,000,000 exact arithmetic steps. Everything is computed on your device in a background worker with a 15 second limit. Downloads are a JSON report and a CSV of nodes. First line: maximize or minimize and the objective. Then one constraint per line. Up to 4,000 characters. Review the settings before running.
Your result
How to use Integer programming sandbox
- Write the objective on the first line, such as maximize 5x + 4y.
- Add one constraint per line, bounds such as x, y >= 0, and optional lines such as integer x or binary z.
- Set the node limit and run the search.
- Read the status, the incumbent, the best bound and the gap, then download the JSON report or the CSV of nodes.
Useful next steps
Programs are limited to 4,000 characters and 40 lines, 8 variables and 8 constraints with two or more variables; the node limit is 1 to 5,000 and the search also stops after 3,000,000 exact arithmetic steps. Everything is computed on your device in a background worker with a 15 second limit. Downloads are a JSON report and a CSV of nodes.
Branch and bound
Each node solves the linear relaxation exactly with the simplex method. A fractional integer variable is split into two branches, x <= floor and x >= ceiling. Nodes are pruned when their relaxation is infeasible or cannot beat the best integer point found. Method: Wolsey, Integer Programming, 2nd edition, chapter 7 (2020).
What proven means
When every node has been solved or pruned with an exact bound, the incumbent is proven optimal, or the problem is proven infeasible. If the node limit or the step budget stops the search first, the incumbent is only the best point found so far, and the report gives the best bound and the gap between them.
Input rules
Variables are integer unless you list some with integer x, y, in which case the others are continuous. Single-variable constraints become bounds. A relaxation that is unbounded stops the search, because the integer program may then be unbounded or infeasible.