Network Optimization and Integer Programming
This domain tests network algorithms and integer modeling. Expect shortest path, minimum spanning tree, maximum flow/minimum cut, min-cost flow, assignment and transportation models, plus branch-and-bound, cutting planes, relaxations, and logical constraints.
Core rules
- Shortest path with nonnegative costs suits Dijkstra; negative edges require Bellman-Ford or detect negative cycles.
- Max flow equals min cut capacity; a cut partitions nodes and bounds every flow.
- Network matrices are often totally unimodular, so LP relaxations can yield integral solutions for pure network flow models.
- Branch-and-bound solves relaxations and prunes by bound; the gap measures relaxation quality.
- Big-M constraints need a valid, tight M; too small cuts off feasible solutions, too large weakens the relaxation.
Worked example
Maximize 5x1+4x2+3x3 subject to 4x1+3x2+2x3≤6, x binary. The LP relaxation takes x3=1, x2=1, and x1=0.25, giving 8.25. Branching on x1=1 yields capacity 2 left after x1, so x3=1 and objective 8; this integer solution is feasible. Branching on x1=0 allows x2=1 and x3=1, objective 7, or x3=1 alone, objective 3. The best integer value is 8, with gap 0.25 from the relaxation.
Traps
Using Dijkstra with negative arcs, confusing cut capacity with flow value, assuming every LP relaxation is integral, and choosing big-M by guesswork.
Key points
- Match algorithms to network assumptions.
- Max flow equals min cut.
- Total unimodularity explains integral network optima.
- Branch-and-bound uses bounds and gaps.
- Big-M must be valid and tight.