ETF5248 Chap.5 Integer Programming Decisions
Integer Programming Decisions
Integer programming represents choices that cannot be divided continuously. Binary variables encode open or closed, selected or rejected, and logical states, while general integers represent countable quantities.
Linking constraints connect those discrete states to flows, production or assignments so the model cannot use an activity whose enabling choice is off.
This chapter tests logic in both binary states, distinguishes fixed-charge, covering, knapsack and facility patterns, and explains branch and bound as a proof process.
LP relaxations provide bounds, integer solutions become incumbents, and nodes are pruned by infeasibility, integrality or dominance. A reported solution is complete only when feasibility, bound direction, gap and tolerance are interpreted together.
Logical accuracy can be tested before optimisation.
Substitute zero and one into every binary implication and check that each state permits exactly the intended continuous activity. A fixed-charge model normally puts the fixed cost on the binary and variable cost on the activity, then links activity to a defensible physical upper bound. An unnecessarily huge constant leaves the integer solutions unchanged but weakens the LP relaxation, so the search learns less from each node.
In maximisation, relaxation values are upper bounds; in minimisation, they are lower bounds. The incumbent moves in the opposite practical role because it is an achievable integer solution. A node closes when it is infeasible, already integer, or unable to beat that incumbent. The remaining difference between incumbent and global bound is the optimality gap.
Reporting the gap, its absolute or relative convention and the numerical tolerance makes clear whether the decision is merely feasible or actually certified optimal.
What this chapter covers
- 01
Binary and general integer domains
- 02
Fixed charges and activation logic
- 03
Tight linking bounds
- 04
Covering, knapsack and facility patterns
- 05
LP relaxation and branch and bound
- 06
Incumbents, bounds, pruning and gaps
Worked example · free
Link a facility opening decision to capacity
- 1Use x no more than 80y, with y binary and x non-negative.
- 1When y = 0, the row and non-negativity force x = 0, so a closed depot cannot ship.
- 1When y = 1, the row becomes x no more than 80, which is the physical capacity.
- 1A bound of 1,000 permits unrealistic relaxation flow and produces a weaker branch-and-bound bound without adding valid integer solutions.
Key terms
- Binary variable
- A zero-or-one variable used to represent a discrete state or decision.
- Linking constraint
- A row connecting a discrete enabling decision to the level of another activity.
- LP relaxation
- The continuous model obtained when integer restrictions are temporarily removed.
- Incumbent
- The best integer-feasible solution currently known during search.
- Branch-and-bound node
- A restricted subproblem created by partitioning the remaining discrete feasible set.
Integer Programming Decisions FAQ
Why not solve continuously and round?
Independent rounding can violate capacity, coverage, assignment or logical constraints, and it can miss a better nearby integer combination. Integrality changes the feasible set itself. The integer model must be solved or a rounded proposal must be checked and compared through a valid discrete method.
What makes a linking bound tight?
It is the smallest valid upper bound on the linked activity when the binary equals one, derived from physical capacity, demand or another proven limit. A tighter bound narrows the LP relaxation and usually helps branch and bound produce stronger bounds with fewer nodes.
When can a branch-and-bound node be pruned?
A node can close when its relaxation is infeasible, when the relaxation solution is integer, or when its bound cannot improve the incumbent. Each reason is a proof about that entire subregion, so record which condition applies instead of describing pruning as arbitrary deletion.
What should I report if the solver stops early?
Report the best integer-feasible incumbent, the best remaining bound, whether the problem is maximisation or minimisation, the absolute or relative gap and the stopping tolerance. Do not label the incumbent proven optimal unless the gap and solver status justify that claim.
Exam move
For every logical rule, make a two-row truth table for the binary states and substitute zero and one into the proposed constraints. Derive every large bound from business data and note its unit. When reading a branch-and-bound tree, annotate each node with its relaxation bound, integer feasibility and pruning reason, then track the incumbent separately. Practise the direction of bounds for both maximisation and minimisation.
This builds the proof logic that solver output compresses into a status line and prevents an attractive feasible solution from being mistaken for a certified optimum.
Working through Integer Programming Decisions in ETF5248? Sia is AskSia’s AI Mathematics tutor — ask any ETF5248 Integer Programming Decisions question and get a clear, step-by-step explanation grounded in how ETF5248 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
