Shortest-path formulation

Shortest-path formulation

Class: ULSAlgorithms.Exact.Formulations.ShortestPathFormulationSolver

Family: Solver-backed network formulation
Time: Solver-dependent
Memory: O(T²) model + solver
Applicability: No speculative motive / Wagner–Whitin costs

Description

Shortest-path formulation is an exact solver-backed ULS strategy. It builds a mathematical formulation and delegates the optimization step to the selected external engine while keeping the common IUlsSolver result contract.

Mathematical model

A replenishment arc \((t,j+1)\) has cost

\[c_{tj}=f_t+\sum_{k=t}^{j}d_k\left(p_t+\sum_{r=t}^{k-1}h_r\right). \]

The unit-flow model is

\[\min \sum_{(t,j+1)\in A}c_{tj}z_{t,j+1} \]

with node-flow conservation

\[\sum_{a\in\delta^+(v)}z_a-\sum_{a\in\delta^-(v)}z_a=b_v, \qquad b_v=\begin{cases} 1 & v=0,\\ -1 & v=T,\\ 0 & \text{otherwise,} \end{cases} \]

and \(0\le z_a\le1\). The formulation requires

\[p_t+h_t\ge p_{t+1}, \qquad t=1,\ldots,T-1. \]

For the formulation taxonomy and historical context, see Mathematical Programming Formulations.

Minimal API

IUlsSolver solver = new ShortestPathFormulationSolver();
UlsSolveResult result = solver.Solve(problem);

Scientific source

Zangwill (1969), A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System, Management Science 15(9), 506-527; Brahimi, Dauzere-Peres, Najid & Nordli (2006), Single Item Lot Sizing Problems, European Journal of Operational Research 168(1), 1-16

Full class reference

Use the Doxygen Classes index for constructors, members and source-level documentation.