Uncapacitated lot sizing with backlogging: the convex hull
From the abstract: ``An explicit description of the convex hull of solutions to the uncapacitated lot-sizing problem with backlogging in its natural space of production, setup, inventory and backlogging variables, has been an open question for many years. Uncapacitated lot-sizing problem with backlogging can be formulated as \[ \begin{gathered} z= \min\sum^n_{t=1} f_t x_t+ c_t y_t+ g_t r_t+ h_t s_t),\\ s_{t-1}+ y_t- r_{t-1}= d_t+ s_t- r_t,\quad t= 1,\dots, n,\\ y_t\leq dx_t,\quad t= 1,\dots, n,\quad d= \sum^n_{j=t} d_j,\\ r_0= s_0= r_n= s_n= 0,\\ y\in \mathbb{R}^n_+,\quad s\in\mathbb{R}^{n+1}_+,\quad r\in\mathbb{R}^{n+1}_+,\quad x\in \{0,1\}^n.\end{gathered} \] In this paper, the authors identify valid inequalities that subsume all previously known valid inequalities for this problem. They show that these inequalities are enough to describe the convex hull of solutions. The authors give polynomial separation algorithms for some special cases. Finally, they report a summary of computational experiments with our inequalities that illustrates their effectiveness.
- A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System—A Network Approach
- A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
- A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
- A Deterministic Multi-Period Production Scheduling Model with Backlogging
- A polyhedral approach to a production planning problem
- Approximate extended formulations
- scientific article; zbMATH DE number 232493 (Why is no real title available?)
- Linear-programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity
- Lot-size models with backlogging: Strong reformulations and cutting planes
- Lotsizing with backlogging and start-ups: The case of Wagner-Whitin costs
- Network flows. Theory, algorithms, and applications.
- Polyhedra for lot-sizing with Wagner-Whitin costs
- Production Planning by Mixed Integer Programming
- Solving Multi-Item Lot-Sizing Problems Using Strong Cutting Planes
- Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation
- Valid inequalities and separation for uncapacitated fixed charge networks
- Lot-size models with backlogging: Strong reformulations and cutting planes
- Single-item dynamic lot-sizing problems: an updated survey
- A polyhedral study of the static probabilistic lot-sizing problem
- Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: zero setup case
- Convex hull results for the warehouse problem
- A computational analysis of lower bounds for big bucket production planning problems
- Robust formulations for economic lot-sizing problem with remanufacturing
- An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging
- Lot-sizing with fixed charges on stocks: the convex hull
- Mixed integer programming in production planning with backlogging and setup carryover: modeling and algorithms
- Local cuts and two-period convex hull closures for big-bucket lot-sizing problems
- Uncapacitated lot-sizing problem with production time windows, early productions, backlogs and lost sales
- Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales
- Uncapacitated lot-sizing: The convex hull of solutions
- A Lagrangian relaxation-based method and models evaluation for multi-level lot sizing problems with backorders
- A Polynomial Time Algorithm for the Stochastic Uncapacitated Lot-Sizing Problem with Backlogging
- Two-stage stochastic lot-sizing problem under cost uncertainty
- Relaxations for two-level multi-item lot-sizing problems
- Uncapacitated lot-sizing with buying, sales and backlogging
- Solving the capacitated lot-sizing problem with backorder consideration
- Multiechelon Lot Sizing: New Complexities and Inequalities
- A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems
- Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
- New valid inequalities and formulations for the static joint chance-constrained lot-sizing problem
- Valid inequalities and extended formulations for lot-sizing and scheduling problem with sequence-dependent setups
- Stochastic lot-sizing problem with deterministic demands and Wagner-Whitin costs
- Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints
- Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution
This page was built for publication: Uncapacitated lot sizing with backlogging: the convex hull
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016115)
