DASE7034 Chap.6 Integer Programming Formulation
Integer Programming Formulation
Integer programming represents indivisible counts, yes-or-no choices and logical relationships. Binary variables can switch activities on, impose mutual exclusion or encode implications, while linking constraints connect opening decisions to continuous operating quantities.
LP relaxations provide bounds, but rounding their fractional solution can violate feasibility and does not prove optimality.
Choose domains that match the decision
Use a general integer variable for counts such as vehicles, shifts or facilities when several whole-number values are possible. Use a binary variable when the choice is yes or no, open or closed, selected or excluded.
Continuous variables may remain alongside integers for quantities that are genuinely divisible.
Integrality should arise from operational meaning rather than from a desire to make a model seem realistic; unnecessary integer restrictions increase computational difficulty without improving the representation.
Translate logic into linear constraints
Mutual exclusion between two binary choices can be written as their sum being at most one, while an exactly-one requirement uses equality.
An implication such as selecting project A requires project B becomes yA less than or equal to yB. Fixed-charge decisions need a linking relationship: an activity quantity x is bounded above by a valid capacity M times an activation variable y.
When y is zero, x is forced off; when y is one, the physical bound remains available.
Construct defensible linking constants
A large constant should be a genuine upper bound derived from capacity, demand or another model restriction. An excessively loose value weakens the LP relaxation, increases numerical risk and can slow the search. A value that is too small silently deletes feasible solutions.
If an activity must operate above a minimum level when opened, add a lower link such as x greater than or equal to Ly as well as the upper link. Explain both bounds in operational language and retain consistent units.
Audit relaxation and rounding claims
Removing integrality creates an LP relaxation whose feasible region contains the integer solutions.
For maximisation its optimum is an upper bound on the integer optimum; for minimisation it is a lower bound. The fractional solution is not usually implementable, and rounding components independently can violate capacity, balance or logic. A valid integer candidate must be substituted into every constraint, and its objective supplies an incumbent rather than a proof of optimality.
The gap between a relaxation bound and the best feasible integer solution measures what remains to be certified.
What this chapter covers
- 01
Pure and mixed integer models
- 02
Binary decision variables
- 03
Logical implications
- 04
Big-M linking constraints
- 05
LP relaxation bounds
Worked example · free
Link facility opening to capacity
- 2Define binary opening variable y and production x.
- 2Use a grounded physical capacity as M.
- 2Test the constraint at y equal to zero and one.
Key terms
- Binary Variable
- A decision variable restricted to zero or one, commonly representing no or yes.
- Linking Constraint
- A constraint connecting a discrete activation decision to an associated operating quantity.
- Big-M Bound
- A justified upper bound used to switch a constraint or activity with a binary variable.
Integer Programming Formulation FAQ
Why is rounding a relaxed solution unsafe?
Independent rounding can violate capacities, balances or logical implications, and even a feasible rounded point need not be the best integer solution. Integer optimisation uses bounds and search to preserve feasibility and certify quality.
How should a value for M be chosen?
Derive the tightest valid upper bound from physical capacity, demand, policy or another model limit. An unnecessarily large value weakens the relaxation and can create numerical difficulty without adding valid decisions.
When is an integer restriction unnecessary?
If units are numerous and fractional values are a harmless planning approximation, a continuous variable may be adequate. Keep integrality for genuinely indivisible decisions such as facilities, machines, projects or route selections.
Exam move
Translate each logical sentence into allowed and forbidden binary combinations before writing algebra. Test the proposed inequality against the truth table. For linking constraints, justify every upper or lower bound from the situation rather than choosing a convenient large number.
Build a small truth table for mutual exclusion, implication and exactly-one rules, then test the proposed constraint against all zero-one combinations. For a continuous-to-binary link, check y equal to zero, y equal to one and the largest physically possible x. Derive the upper constant from demand, capacity or another valid restriction and explain its unit. Add a lower link when activation requires a minimum operating level.
Compare the integer model with its LP relaxation and label the bound direction for maximisation or minimisation. Take a fractional relaxation solution and try both upward and downward rounding; substitute each candidate into every capacity and logic constraint to see why rounding is not a proof. Finish by reporting three distinct objects: the relaxation bound, the best verified integer candidate and the remaining gap.
This keeps the benchmark separate from the implementable decision and the optimality certificate.
Working through Integer Programming Formulation in DASE7034? Sia is AskSia’s AI Mathematics tutor — ask any DASE7034 Integer Programming Formulation question and get a clear, step-by-step explanation grounded in how DASE7034 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.