optional · interactive figures

Explore: arc flow and symmetry

The arc-flow model's flow taken apart into bins, integer and LP, and every symmetric copy of the running example's packings.

optional: nothing in the lab depends on itback to the slides

27 · explore

An arc-flow solution, one bin at a time

Try: step through the running example's integer flow, then its LP relaxation (2.5), then the capacity-7 instance's LP. Static version: the arc-flow graph.

What it shows. The arc-flow graph of the reference arcflow_model: nodes $0..C$, an item arc $d \to d + s$ for every size $s$ (curves, taller for bigger sizes) and a loss arc $d \to d + 1$ (along the line). Arc labels are SCIP's flow values for the integer model and for its LP relaxation (vtype="C"). Stepping takes the flow apart into paths from node 0 to node $C$, one per bin, each with the amount of flow it carries; that decomposition is done in slides/viz/traces/u27.py and checked to add back up to SCIP's arc values.

Running example, integer: 2 bins "3 + 2" and 1 bin "2 + 2" with one unit empty, as on the slide.
Running example, LP: the same two paths, but the second carries only 0.5: value 2.5, which rounds up to the optimum 3.
Capacity 7, LP: four fractional bins adding to 2.43; again $\lceil 2.43 \rceil = 3$ is the integer optimum. Paths can use more item arcs than there are items: an item arc with no item in it is just empty space.
A path decomposition is not unique; this is one of them. The arc values are what SCIP returned.

27 · explore

Symmetry, every copy on one screen

Try: hover a few cells in one row (same packing, different labels), then tick the rule and see which one survives. Static version: symmetry, counted.