The University of Hong Kong · FACULTY OF MATHEMATICS

DASE7034 Chap.6 Integer Programming Formulation

- one subject, every graph, every model, every mark
5 Chapters3-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 6 of 12 · DASE7034

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.

In this chapter

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

Q [6 marks]. The mark allocation in this practice task is not a University-published assessment scheme. Write a constraint that permits production only when a line opens.
Binary variables act as logical switches.Binary variables act as logical switches. Linking constraints turn facilities, projects and mutually exclusive choices on or off while continuous quantities carry operating levels.open? y=10 ≤ x ≤ Mychoose AyA + yB ≤ 1
Binary variables act as logical switches. Linking constraints turn facilities, projects and mutually exclusive choices on or off while continuous quantities carry operating levels.
  • 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.
If capacity is 120, write zero less than or equal to x less than or equal to 120y, with y binary. At y=0, x is forced to zero. At y=1, production can range up to the physical capacity. A minimum operating level needs a separate lower link. The marks shown for the steps are AskSia-authored practice weighting, not the University's assessment scheme.
Sia tip — Substitute both binary values; if the forbidden case still satisfies the constraint, the implication is reversed.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your DASE7034 tutor, unlimited, worked the way the exam marks it
The full 3-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works