TOPIC 2 / 2

Integer Decisions, Assignment & Transport

Useful preparation: Feasible Regions, Vertices & Dual Bounds

For a long equation, swipe sideways inside its formula box to see every term.

Meaning & notation

A fractional answer may be mathematically feasible for an LP yet impossible when decisions count indivisible objects. Integer programming keeps the same linear expressions but restricts selected variables to integers. Transportation and assignment problems have special network structure: under integer supply and demand data, their standard LPs have integral vertices, so an integral optimum can be found without generic integer search.

Integer program and relaxation: An integer program restricts some or all variables to integer values. Its LP relaxation removes those restrictions, enlarging the feasible set and providing an objective bound.
Transportation model: Variable xij is the quantity sent from source i to destination j. Row sums match supplies, column sums match demands, and nonnegative shipments incur a sum of unit costs times quantities.
Assignment model: A standard assignment problem pairs each agent with one task and each task with one agent. Binary variables indicate pairs; it is a transportation model with each supply and demand equal to one.

Conditions before calculation

Relaxation gives an upper bound for maximization and a lower bound for minimization. A fractional relaxed optimizer is not automatically a valid integer solution.
The balanced transportation formulation requires total supply to equal total demand. A dummy source or destination can model a genuine shortage or surplus only with appropriate costs and meaning.
The integrality guarantee applies to the standard network formulation with integer supplies, demands, and any integral capacities. Extra coupling constraints or fixed-charge decisions can destroy that structure; arbitrary feasible or optimal convex combinations can still be fractional.

Why the method works

1. Separate bounds from decisions

Solve or analyze the relaxation to learn what is theoretically possible. Check an integer candidate against every original constraint and compute its objective directly.

2. Use structure when available

The network constraint matrix is totally unimodular: every square subdeterminant is zero, one, or minus one. With integer right sides, this makes its feasible vertices integral.

3. Certify completeness

For a small bounded integer model, enumerate all possible values systematically. For transportation, use balance equations to reduce variables, then optimize over the resulting feasible interval or use a network algorithm.

Worked examples

EXAMPLE 1

Maximize $\displaystyle 5\, x + 4\, y$ with $\displaystyle 3\, x + 2\, y$ at most 7 and nonnegative integer x,y.

Because 3x cannot exceed 7, only $\displaystyle x = 0$ ,1,2 need examination. For each x, a positive coefficient on y makes the largest feasible integer y best.
Enumerate these three best possibilities and their objective values.
$(x,y)=(0,3),(1,2),(2,0)\quad\Rightarrow\quad 12,13,10$
The relaxation prefers y because it earns 2 per resource unit rather than $\displaystyle \frac{5}{3}$ . Its point (0,3.5) has value 14, an upper bound.

Conclusion: The integer optimum is (1,2) with value 13. Rounding the relaxed y down gives only 12; rounding it up violates the resource limit.

EXAMPLE 2

Sources A,B supply 3,2 units; destinations 1,2 demand 2,3 units. Unit costs are $\displaystyle A\, 1 = 1$ , $\displaystyle A\, 2 = 4$ , $\displaystyle B\, 1 = 3$ , $\displaystyle B\, 2 = 1$ . Find a minimum-cost shipment.

Let t be the A-to-1 shipment. Balance determines all other shipments.
$x_{A1}=t,\quad x_{A2}=3-t,\quad x_{B1}=2-t,\quad x_{B2}=t$
Nonnegativity gives 0 at most t at most 2; express total cost.
$C(t)=t+4(3-t)+3(2-t)+t=18-5t$
The cost decreases as t grows, so take $\displaystyle t = 2$ . Check row totals 3,2 and column totals 2,3.
$X=\begin{pmatrix}2&1\\0&2\end{pmatrix},\qquad C=2+4+0+2=8$

Conclusion: The balanced, nonnegative shipment has minimum cost 8 and is integral.

Pitfalls & counterexamples

Tempting claim: Rounding any LP optimum solves its integer program.

Correction: Rounding may violate constraints or miss a better feasible integer point.

Test the claim: The first example rounds down to value 12 even though the feasible integer point (1,2) earns 13.

Check your understanding

Does an integral transportation optimum imply every feasible shipment is integral?

Write a reason before opening the explanation. This reflection is not graded or saved.

Compare your reasoning

No.

In the second example $\displaystyle t = \frac{1}{2}$ gives a feasible fractional shipment. Integrality describes vertices and the existence of an integral optimum.

Connect this idea

Assignment is a bipartite matching problem. Branch-and-bound combines relaxation bounds with discrete search for general integer models; network structure can make specialized problems much easier.

Practise this topic →Review concept flashcards

Reference reading

Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.