ULSAlgorithms 1.1.0-g3e5595996d
High-performance exact and heuristic algorithms for uncapacitated lot sizing
Loading...
Searching...
No Matches
Algorithm Catalog

Algorithm Catalog

Generated from docs/algorithm-catalog.json. The documentation portal is the recommended browsing interface.

Current inventory: 23 exact strategies, 19 heuristics, 42 public strategies.

Exact algorithm

Strategy Family Time Memory Applicability
Adaptive exact selection Adaptive exact strategy selection O(T) in the NSM case; O(T log T) in the general case O(T) All validated classical ULS instances; dispatches from the no-speculative-motive condition
Wagner–Whitin classical Wagner–Whitin DP O(T²) O(T²) Classical ULS / Wagner–Whitin model
Wagner–Whitin / Evans Wagner–Whitin DP O(T²) O(T) Classical ULS / Wagner–Whitin model
Wagner–Whitin linear Geometric DP O(T) O(T) No speculative motive / Wagner–Whitin costs
Wagelmans general Geometric DP O(T log T) O(T) General time-varying ULS costs
Federgruen–Tzur general Geometric DP O(T log T) O(T) General time-varying ULS costs
Federgruen–Tzur linear (NSM) Geometric DP O(T) O(T) No speculative motive
Federgruen–Tzur linear (setup) Geometric DP O(T) O(T) Published restricted nondecreasing-setup case
Aggarwal–Park Monge / geometric DP O(T log T) O(T) General ULS costs represented by the library
Bahl–Taj planning horizon Planning-horizon DP O(T²) worst case O(T) No speculative motive
Heady–Zhu Planning-horizon DP O(T²) worst case O(T) Constant setup, production and relevant holding costs
Chowdhury–Baki–Azab Linear Wagner–Whitin O(T) O(T) Strictly positive demand; stationary relevant holding; constant unit production cost
Sadjadi–Aryanezhad–Sadeghi Planning-horizon DP O(T²) worst case O(T) Constant setup, production and relevant holding costs
Lyu–Lee parallel Parallel DP O(T²) work; O(T²/p) ideal parallel candidate span O(T) General ULS costs
Saydam–McKnew Wagner–Whitin DP O(T²) O(T²) General ULS costs represented by the library
Jacobs–Khumawala Branch and bound O(T²) O(T) General ULS costs represented by the library
Zangwill network Network / shortest path O(T²) O(T) Single-echelon no-backlogging ULS represented by the library

Mathematical optimization

Strategy Family Time Memory Applicability
Aggregate inventory formulation Solver-backed mathematical formulation Solver-dependent O(T) model + solver General classical ULS
Facility-location formulation Solver-backed mathematical formulation Solver-dependent O(T²) model + solver General classical ULS
Shortest-path formulation Solver-backed network formulation Solver-dependent O(T²) model + solver No speculative motive / Wagner–Whitin costs
Inventory-eliminated formulation Solver-backed mathematical formulation Solver-dependent O(T) variables + O(T²) coefficients/constraints General classical ULS

Cutting-plane method

Strategy Family Time Memory Applicability
General (l,S) cutting-plane Cutting planes / convex hull O(T²) separation per root iteration + solver O(T) separator + model/cuts General classical ULS
Wagner–Whitin (l,S) cutting-plane Cutting planes / Wagner–Whitin O(T²) separation per root iteration + solver O(T) separator + model/cuts No speculative motive / Wagner–Whitin costs

Heuristic

Strategy Family Time Memory Applicability
Lot-for-Lot Baseline O(T) O(T) General ULS costs
Silver–Meal Average-cost O(T) O(T) Stationary setup, production and relevant holding costs
Least Unit Cost Average-cost O(T) O(T) Stationary setup, production and relevant holding costs
Part-Period Balancing Part-period O(T) O(T) Stationary setup, production and relevant holding costs
Groff Marginal-cost O(T) O(T) Stationary setup, production and relevant holding costs
Periodic Order Quantity Fixed-cycle O(T) O(T) Stationary setup, production and relevant holding costs
Freeland–Colley Marginal-cost O(T) O(T) Stationary setup, production and relevant holding costs
Patterson–LaForge IPPA Part-period O(T) O(T) Stationary setup, production and relevant holding costs
Wemmerlöv corrected PPB Part-period O(T) O(T) Stationary setup, production and relevant holding costs
Wemmerlöv PPB + LALB Look-ahead / look-back O(T) O(T) Stationary costs; strictly positive demand
Wemmerlöv corrected PPB + LALB Look-ahead / look-back O(T) O(T) Stationary costs; strictly positive demand
Part-Period Simplified Part-period O(T) O(T) Stationary setup, production and relevant holding costs
Segerstedt reformulated Silver-Meal Average-cost O(T) O(T) Stationary setup, production and relevant holding costs
Chiu modified Least Unit Cost Average-cost / post-processing O(T) O(T) Stationary setup, production and relevant holding costs
Chiu-Ting modified Part-Period Balancing Part-period / post-processing O(T) O(T) Stationary setup, production and relevant holding costs
Ho-Chang-Solis net Least Period Cost Average-cost / net period O(T) O(T) Stationary setup, production and relevant holding costs
Ho-Chang-Solis improved nLPC(i) Average-cost / net period O(T) O(T) Stationary setup, production and relevant holding costs
McLaren Order Moment Part-period / EOQ hybrid O(T) O(T) Stationary setup, production and relevant holding costs
Karni Maximum Part-Period Gain Global part-period merge O(T log T) O(T) Stationary setup, production and relevant holding costs