QBUS2310 Chap.8 Integer Models and Branch-and-Bound
Integer Models and Branch-and-Bound
Integer restrictions represent indivisible quantities, yes-or-no choices, and logical structure. Removing integrality creates an LP relaxation that supplies a bound, not necessarily an implementable plan. Branch-and-bound repeatedly partitions the feasible set, solves relaxations, and prunes nodes using infeasibility, integrality, or bounds. Strong formulations can make this search dramatically easier.
These terms let a reader distinguish a relaxation bound from an implementable integer plan. Integer Program is an optimisation model requiring some or all variables to take integer values. Binary Variable is a zero-or-one variable representing a discrete choice. LP Relaxation is the model obtained by removing integer restrictions while retaining linear constraints.
Integrality Gap is the difference between a relaxation bound and the best integer objective value. Branch and Bound is a search method that partitions solutions and prunes nodes using relaxation bounds. Valid Inequality is a constraint satisfied by every feasible integer solution and used to strengthen a formulation.
The relaxation and integer candidates above are compared as follows: The relaxation value is 49/3, while the integer optimum is (3,1) with value 15. Their difference is an integrality gap, and naive rounding does not preserve feasibility or optimality.
What this chapter covers
- 01
Integer and binary variables
- 02
Mixed-integer models
- 03
Fixed-charge logic
- 04
Set covering
- 05
LP relaxation
- 06
Integrality gap
- 07
Branch-and-bound tree
- 08
Valid bounds and pruning
Integer Models and Branch-and-Bound worked example
- +1Solve the two binding relaxation boundaries to obtain x=y=7/3 and value 49/3.
- +1The fractional point is a valid upper bound for the integer maximisation problem but cannot be implemented.
- +1Enumerate nearby feasible lattice points. The point (3,1) is feasible with value 15; (1,3) has value 13 and (2,2) has value 14.
- +1Rounding both coordinates up violates both constraints; rounding down gives value 14. Branching or enumeration is needed to certify the integer optimum.
Key terms
- Integer Program
- An optimisation model requiring some or all variables to take integer values.
- Binary Variable
- A zero-or-one variable representing a discrete choice.
- LP Relaxation
- The model obtained by removing integer restrictions while retaining linear constraints.
- Integrality Gap
- The difference between a relaxation bound and the best integer objective value.
- Branch and Bound
- A search method that partitions solutions and prunes nodes using relaxation bounds.
- Valid Inequality
- A constraint satisfied by every feasible integer solution and used to strengthen a formulation.
Integer Models and Branch-and-Bound FAQ
Why does integer and binary variables matter?
Integer Program: An optimisation model requiring some or all variables to take integer values. Binary Variable: A zero-or-one variable representing a discrete choice. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How can I check set covering?
Binary Variable: A zero-or-one variable representing a discrete choice. LP Relaxation: The model obtained by removing integer restrictions while retaining linear constraints. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
What separates integer program from binary variable?
LP Relaxation: The model obtained by removing integer restrictions while retaining linear constraints. Integrality Gap: The difference between a relaxation bound and the best integer objective value. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Which error is most likely around integrality gap?
Integrality Gap: The difference between a relaxation bound and the best integer objective value. Branch and Bound: A search method that partitions solutions and prunes nodes using relaxation bounds. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
How should I practise valid bounds and pruning?
Branch and Bound: A search method that partitions solutions and prunes nodes using relaxation bounds. Valid Inequality: A constraint satisfied by every feasible integer solution and used to strengthen a formulation. Keep these two roles separate when checking the model, because confusing them changes the feasible set, bound, or operational interpretation.
Exam move
Always label a fractional relaxation solution as a bound. Test rounded candidates against every constraint and use logical links that are as tight as the stated operational limits permit. Rehearse the chapter method in this order: Solve the two binding relaxation boundaries to obtain x=y=7/3 and value 49/3. The fractional point is a valid upper bound for the integer maximisation problem but cannot be implemented.
Enumerate nearby feasible lattice points. The point (3,1) is feasible with value 15; (1,3) has value 13 and (2,2) has value 14. Rounding both coordinates up violates both constraints; rounding down gives value 14. Branching or enumeration is needed to certify the integer optimum.
Working through Integer Models and Branch-and-Bound in QBUS2310? Sia is AskSia’s AI Mathematics tutor — ask any QBUS2310 Integer Models and Branch-and-Bound question and get a clear, step-by-step explanation grounded in how QBUS2310 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
