Shortest Path Binary Formulation¶

Definition¶

A shortest path binary formulation assigns $x_{ij}=1$ if a directed edge is selected. For the undirected course network, create both directed orientations of each edge. With origin $s$ , destination $t$ , and edge lengths $\ell_{ij}$ , use

\begin{gathered} \min\sum_{(i,j)}\ell_{ij}x_{ij},\\ \sum_jx_{ij}-\sum_jx_{ji}=\begin{cases}1,&i=s,\\-1,&i=t,\\0,&\text{otherwise},\end{cases}\\ x_{ij}\in\{0,1\}. \end{gathered}

Sums include only existing directed orientations.

Interpretation¶

The formulation writes the shortest path problem as a binary integer program. Each variable $x_{ij}$ says whether the route uses edge $i\to j$ $j$ , and the balance equations force the selected edges to carry one unit from origin to destination; the objective then picks the cheapest such route.

A network from A to F with the edges of the shortest path labelled x = 1 and the flow balance written at the source, the sink and an intermediate vertex.

The selected edges $A\to C\to B\to D\to E\to F$ have $x=1$ and the grey edges have $x=0$ $0$ . At the origin $A$ one selected edge leaves and none enters (out $-$ in $=1$ $1$ ), at the destination $F$ one enters and none leaves ( $-1$ ), and at an intermediate vertex such as $D$ one enters and one leaves ( $0$ ).

Each undirected edge becomes two directed edges because the route may use it in either direction. The balance equations do not by themselves rule out a closed loop of selected edges, since such a loop also has out $-$ in $=0$ at each of its vertices. With strictly positive lengths a loop only adds cost, so an optimal solution contains none; with zero-length edges an optimal solution may contain one, and removing it leaves a shortest path of the same cost.

The shortest path algorithm solves the same problem directly; the formulation is useful because, as an ordinary integer program, it accepts further constraints. The same balance equations reappear in the project longest path model, with the objective maximized, and at the intermediate vertices they are the flow-conservation constraints of the maximum flow LP.

Key Results¶

With strictly positive lengths as in the exercise, an optimum contains no unnecessary cycle.
If zero-cost edges are allowed, an optimal binary solution may contain removable zero-cost cycles.
The balances alone must not be claimed to prohibit every possible cycle.

Examples¶

For a feasible network with nonnegative edge lengths, the unit-flow LP relaxation admits an integral optimal solution. Removing any zero-cost cycles leaves a shortest path; arbitrary optimal flow representations need not themselves be cycle-free.

In the course exercise network (not the figure), the route $S-B-A-D-E-T$ selects its five directed edges and has cost 12.
At $A$ on that route, $x_{BA}=x_{AD}=1$ balances one incoming and one outgoing edge.

Prerequisites¶

Sources¶

OR Modelling · Week 5

Symbols: element of, sum

Last updated: 20 October 2026 03:02