Uncapacitated Lot-Sizing with Stock Upper Bounds, Stock Fixed Costs, Stock Overloads and Backlogging: A Tight Formulation

摘要

For an n-period uncapacitated lot-sizing problem with stock upper bounds, stock fixed costs, stock overload and backlogging, we present a tight extended shortest path formulation of the convex hull of solutions with O(n^2) variables and constraints, also giving an O(n^2) algorithm for the problem. This corrects and extends a formulation in [11] for the problem with just stock upper bounds.