ETF2480 Chap.7 Integer Programming Formulations
Integer Programming Formulations
Integer programming represents decisions that cannot be divided freely. Binary variables model opening, selecting, assigning and activating. General integer variables count indivisible units, while continuous variables can coexist in a mixed-integer model.
Logical consequences need explicit linking constraints: activity is allowed only when a site opens, coverage is provided by selected facilities, and mutually exclusive projects cannot be chosen together. The LP relaxation drops integrality and supplies a bound, not an implementable answer. Rounding may violate constraints or lose value.
Strong formulations use the smallest valid big-M and preserve the intended logic in both binary states.
What this chapter covers
- 01
Binary and general integer domains
- 02
Fixed-charge decisions
- 03
Logical implication rows
- 04
Facility location and coverage
- 05
LP relaxation bounds
- 06
Big-M strength and units
Worked example · free
Link site openings to activity
- +1Define binary yA,yB and nonnegative activity xA,xB.
- +2Use xA <= 40yA, xB <= 70yB and xA + xB = 80.
- +2Both sites must open because neither capacity covers 80 alone; allocate 70 to B and 10 to A.
- +1Total cost is 300 + 450 + 10(5) + 70(3) = $1,010.
Key terms
- Binary variable
- A zero-or-one variable representing a yes-or-no decision.
- Mixed-integer program
- An optimisation model containing both integer and continuous decision variables.
- Fixed charge
- A cost incurred once when an option is activated, usually multiplied by a binary variable.
- Linking constraint
- A row connecting an operational quantity to the binary decision that permits it.
- LP relaxation
- The continuous model obtained by removing integer restrictions, used to create bounds.
Integer Programming Formulations FAQ
Why is rounding a relaxed solution unsafe?
Rounding variables independently can break capacity, balance, coverage or logical rows. Even a feasible rounded plan may be far from the best integer solution. Treat the relaxation objective as a bound and solve the discrete model when indivisibility matters.
How do I choose big-M?
Derive the smallest valid upper bound from capacity, demand, time or another physical limit. An unnecessarily large value weakens the relaxation and can cause numerical difficulty. Document the derivation so the link is auditable.
How do I translate only-if logic?
If choosing A requires choosing B, use yA <= yB. Check the four binary combinations and confirm the forbidden case A=1, B=0 is excluded. Reverse wording can require the opposite inequality, so test meaning rather than memorising phrases.
Why record the relaxation bound?
It provides a benchmark for the best integer solution and exposes formulation weakness. Compare the relaxation and integer objectives, but never present a fractional or mechanically rounded plan as a feasible discrete decision.
Exam move
Build a truth table before writing binary logic. List which combinations are allowed, then choose an inequality that excludes only the forbidden cases. For activity links, substitute zero and one into the binary variable and read the resulting operational bound. Derive big-M from real data rather than convenience.
Solve a small LP relaxation and compare its fractional point with a true integer optimum so the role of bounds becomes concrete. Group formulations by purpose: fixed charge, mutual exclusion, prerequisite, exactly-one choice, coverage and assignment. After solving, report both selected options and continuous activity levels. Check that every selected action obeys capacity and every required customer or zone is covered.
If an objective combines competing measures, explain scaling and explore several weights rather than treating one arbitrary weighted sum as a universal answer. For each implication, write the plain-language trigger and consequence before choosing a constraint. Test all binary combinations against both the intended rule and the proposed inequality.
In fixed-charge models, separate the opening cost from the activity cost and verify that zero opening forces zero activity. Derive each linking bound from demand, capacity or another proven limit; then compare its relaxation with one using an unnecessarily large constant. For location and coverage problems, create a customer-by-site incidence table and check that every required row is covered by a selected option.
Solve a tiny instance by enumeration to verify the optimiser's result and expose symmetry. When multiple objectives are combined, rescale them or present several weights and report the trade-off frontier. Never round a fractional relaxation as a substitute for solving the integer model; substitute any proposed rounded plan into every row first.
Working through Integer Programming Formulations in ETF2480? Sia is AskSia’s AI Management tutor — ask any ETF2480 Integer Programming Formulations question and get a clear, step-by-step explanation grounded in how ETF2480 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
