Branch and Bound Input Form
This version solves two-variable integer linear models. Enter the objective, set variable bounds, then define up to six linear constraints.
Example Data Table
The page loads with the following sample model. It is a compact integer program that demonstrates branching, pruning, and node comparison clearly.
| Element | Value | Meaning |
|---|---|---|
| Objective | Maximize z = 8x + 5y | Improve the objective score using two integer decision variables. |
| Constraint 1 | 2x + y ≤ 14 | Resource cap for the first requirement. |
| Constraint 2 | x + 3y ≤ 18 | Resource cap for the second requirement. |
| Constraint 3 | x ≤ 8 | Upper bound for x. |
| Constraint 4 | y ≤ 7 | Upper bound for y. |
| Bounds | x ≥ 0, y ≥ 0 | Nonnegative integer decision region. |
| Expected best integer point | x = 5, y = 4, z = 60 | Useful checkpoint for testing the calculator. |
Formula Used
z = c1x + c2y
Ignore integrality temporarily and solve the continuous linear program. For maximization, the relaxation gives an upper bound. For minimization, the relaxation gives a lower bound.
If x* or y* is fractional, choose one variable and split it:
x ≤ floor(x*) and x ≥ ceil(x*)
or
y ≤ floor(y*) and y ≥ ceil(y*)
A node is removed when it is infeasible, cannot beat the incumbent, or already gives a valid integer solution.
Bound gap = |Root relaxation objective − best integer objective|
How to Use This Calculator
- Choose whether the model should maximize or minimize the objective.
- Enter coefficients for x and y in the objective function.
- Set lower and upper bounds for both variables.
- Fill in up to six linear constraints using coefficients, relation signs, and right-hand values.
- Adjust tolerance, node limit, and depth if you want tighter or broader search behavior.
- Click the solve button to view the best integer solution, LP bound, node log, graph, and export options.
Frequently Asked Questions
1. What does branch and bound solve?
It solves integer optimization problems by combining linear relaxation, node branching, and pruning. This page focuses on two-variable integer linear models with bounded search regions.
2. Why does the calculator use an LP relaxation first?
The relaxation gives a fast bound for each node. That bound helps reject weak branches early, which reduces the number of nodes explored before finding the best integer answer.
3. What does “pruned by bound” mean?
It means the node’s relaxed result cannot beat the current best integer solution. Since it offers no improvement, the search safely stops exploring that branch.
4. Why are variable bounds important?
Bounds keep the search region finite and make graphing practical. They also help the solver create a closed feasible region for the LP relaxation and integer scan.
5. What happens when the node limit is reached?
The calculator stops branching and reports the best solution found so far. If open nodes remain, the reported result may be partial instead of fully proven optimal.
6. Can I use equality constraints?
Yes. Choose the equals sign for any row that must hold exactly. Equality rows are treated as hard boundaries during relaxation and feasibility checking.
7. Why is the graph sometimes missing?
The graph is skipped when the chosen integer grid becomes too large. That keeps the page responsive and avoids very slow rendering in the browser.
8. What do the CSV and PDF downloads include?
They export the solution summary and node log. This makes it easier to document runs, compare settings, or attach results to reports and class notes.