2
$\begingroup$

I once read a paper stating that under certain conditions, some simple variants of dynamic capacitated lot-sizing problems can be decomposed into subproblems along the temporal dimension and solved separately while retaining optimality of the full problem. Along the lines of, starting from $t = 0$, implement a certain policy and increment $t$ until some conditions are met, then the decisions up to the current $t'$ are optimal regardless of what follows for $t > t'$.

I cannot remember anything else about that paper. I fear that the description is too broad for lot-sizing literature, but I want to try my luck: does someone know what paper I might have in mind? I'm also interested in results regarding approximation ratios of simple dynamic lot-sizing problems. Note that I'm specifically asking about capacitated problems and decomposition along the temporal dimension.

$\endgroup$

1 Answer 1

1
$\begingroup$

First type: The decomposition of the lot-sizing variant problems more than being studied as an academic literature does have a practical background. The heuristic-based decomposition approach focuses on decomposing the problem into the single item lot-sizing as a sub-problems along the temporal dimension or planning horizon is well known as a closed-loop MRP or MRP-II which is the core of many of the modern ERP/APS software. (Whose steps can be easily found by googling).

second type: As the mathematical decomposition approach, there are various decomposition algorithms:

  • Algorithms based on valid inequalities or extended formulations for the subproblems
  • Algorithms based on Lagrangian relaxation or column generation that are the algorithms of choice for many classes of problems in which it is relatively easy in practice to optimize over the “subproblems,” but little is known about improved formulations
  • Hybrid algorithms that combine both approaches

For the second type of reformulation, I refer you to Production Planning by Mixed Integer Programming by Yves Pochet & Laurence A. Wolsey, specifically, chapter $6$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.