A polyhedral study of the static probabilistic lot-sizing problem
From MaRDI portal
Abstract: We study the polyhedral structure of the static probabilistic lot-sizing problem and propose valid inequalities that integrate information from the chance constraint and the binary setup variables. We prove that the proposed inequalities subsume existing inequalities for this problem, and they are facet-defining under certain conditions. In addition, we show that they give the convex hull description of a related stochastic lot-sizing problem. We propose a new formulation that exploits the simple recourse structure, which significantly reduces the number of variables and constraints of the deterministic equivalent program. This reformulation can be applied to general chance-constrained programs with simple recourse. The computational results show that the proposed inequalities and the new formulation are effective for the the static probabilistic lot-sizing problems.
Recommendations
- New valid inequalities and formulations for the static joint chance-constrained lot-sizing problem
- On formulations of the stochastic uncapacitated lot-sizing problem
- A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
- An extended mixed-integer programming formulation and dynamic cut generation approach for the stochastic lot-sizing problem
- Strategies for the Probabilistic Lot-Sizing Problem with Service-Level Constraints
Cites work
- scientific article; zbMATH DE number 176392 (Why is no real title available?)
- scientific article; zbMATH DE number 3568353 (Why is no real title available?)
- A Sample Approximation Approach for Optimization with Probabilistic Constraints
- A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time
- A branch and bound method for stochastic integer problems under probabilistic constraints
- A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
- A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support
- A multi-stage stochastic integer programming approach for capacity expansion under uncertainty
- A sampling-and-discarding approach to chance-constrained optimization: feasibility and Optimality
- An Efficient Trajectory Method for Probabilistic Production-Inventory-Distribution Problems
- An \(O(N^2)\)-time algorithm for the stochastic uncapacitated lot-sizing problem with random lead times
- An algorithm for nonlinear optimization problems with binary variables
- An integer programming approach for linear programs with probabilistic constraints
- Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
- Chance Constrained Programming with Joint Constraints
- Chance-Constrained Binary Packing Problems
- Concavity and efficient points of discrete distributions in probabilistic programming.
- Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems
- Contributions to the theory of stochastic programming
- Decomposition algorithms for two-stage chance-constrained programs
- Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints
- Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution
- Dynamic version of the economic lot size model
- Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
- Formulations for dynamic lot sizing with service levels
- Inexact stabilized Benders' decomposition approaches with application to chance-constrained problems with finite support
- Introduction to Stochastic Programming
- Lot-size models with backlogging: Strong reformulations and cutting planes
- Lot-sizing on a tree
- Mixing mixed-integer inequalities
- On formulations of the stochastic uncapacitated lot-sizing problem
- On mixing sets arising in chance-constrained programming
- On stochastic lot-sizing problems with random lead times
- On the mixing set with a knapsack constraint
- Pattern-based modeling and solution of probabilistically constrained optimization problems
- Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems
- Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
- Relaxations for probabilistically constrained programs with discrete random variables
- Solving chance-constrained optimization problems with stochastic quadratic inequalities
- Solving stochastic programs with simple recourse
- Strengthened benders cuts for stochastic integer programs with continuous recourse
- The Scenario Approach to Robust Control Design
- The integer \(L\)-shaped method for stochastic integer programs with complete recourse
- Uncapacitated lot sizing with backlogging: the convex hull
- Uncapacitated lot-sizing: The convex hull of solutions
- Uncertain convex programs: randomized solutions and confidence levels
Cited in
(13)- On intersection of two mixing sets with applications to joint chance-constrained programs
- A perfect information lower bound for robust lot-sizing problems
- New valid inequalities and formulations for the static joint chance-constrained lot-sizing problem
- A Polynomial Time Algorithm for the Stochastic Uncapacitated Lot-Sizing Problem with Backlogging
- Probabilistic partial set covering with an oracle for chance constraints
- Stochastic dynamic lot-sizing with supplier-driven substitution and service level constraints
- Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems
- A study of the lot-sizing polytope
- Lot-sizing polyhedra with a cardinality constraint
- Polyhedra for lot-sizing with Wagner-Whitin costs
- A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
- Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness
- Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens
This page was built for publication: A polyhedral study of the static probabilistic lot-sizing problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708524)
