A branch and bound method for stochastic integer problems under probabilistic constraints
Optimization methods & softwarePublished 1 January 2002
Patrizia Beraldi, Andrzej Ruszczyński
Citations102
SJR quartileQ2
SJR score0.72
SNIP1.42
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The numerical experience with the probabilistic lot-sizing problem shows the potential of the solution approach and the efficiency of the algorithms implemented.
Abstract
Stochastic integer programming problems under probabilistic constraints are considered. Deterministic equivalent formulations of the original problem are obtained by using p-efficient points of the distribution function of the right hand side vector. A branch and bound solution method is proposed based on a partial enumeration of the set of these points. The numerical experience with the probabilistic lot-sizing problem shows the potential of the solution approach and the efficiency of the algorithms implemented.
Keywords
Decision SciencesBusiness, Management and AccountingEngineering
Journal of the Operational Research SocietyInteger and Combinatorial Optimization
5,548 Citations1990H. P. Williams, George L. Nemhauser +1 more
Management ScienceChance-Constrained Programming
2,729 Citations1959A. Charnes, W. W. Cooper
The paper presents a method of attack which splits the problem into two non-linear or linear programming parts, i determining optimal probability distributions, ii approximating the optimal distributions as closely as possible by decision rules of prescribed form.
Management ScienceDynamic Version of the Economic Lot Size Model
2,077 Citations2004Harvey M. Wagner, T. M. Whitin
Disjoint planning horizons are shown to be possible which eliminate the necessity of having data for the full N periods and desire a minimum total cost inventory management scheme which satisfies known demand in every period.
Management ScienceDynamic Version of the Economic Lot Size Model
2,042 Citations1958Harvey M. Wagner, T. M. Whitin
Stochastic Programming
1,535 Citations1995András Prékopa
Operations ResearchSolving Large-Scale Zero-One Linear Programming Problems
676 Citations1983Harlan Crowder, Ellis L. Johnson +1 more
The results indicate that cutting-planes related to the facets of the underlying polytope are an indispensable tool for the exact solution of this class of problem.
Management ScienceCost Horizons and Certainty Equivalents: An Approach to Stochastic Programming of Heating Oil
619 Citations1958A. Charnes, W. W. Cooper +1 more
Operations ResearchEconomic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
459 Citations1992Albert Wagelmans, Stan van Hoesel +1 more
An algorithm to solve the economic lot sizing problem in O(n log n) time is presented and it is shown how the Wagner-Whitin case can even be solved in linear time.
Operations ResearchChance Constrained Programming with Joint Constraints
458 Citations1965Bruce Miller, Harvey M. Wagner
Management ScienceStrategies for the Probabilistic Lot-Sizing Problem with Service-Level Constraints
276 Citations1988James H. Bookbinder, Jin‐Yan Tan
A stochastic-demand version of the single-stage lot-sizing problem with time-varying demand is formulated, incorporating a service-level constraint on the probability of a stockout and the static uncertainty strategy is shown to be the most straightforward to modify and "roll along" as new demands become known.
Princeton University Press eBooksON PROBABILISTIC CONSTRAINED PROGRAMMING
221 Citations2015András Prékopa
The term probabilistic constrained programming means the same as chance constrained programming, i.e., optimization of a function subject to certain conditions where at least one is formulated so that a condition, involving random variables, should hold with a prescribed probability.
Mathematical ProgrammingConcavity and efficient points of discrete distributions in probabilistic programming
207 Citations2000Darinka Dentcheva, András Prékopa +1 more
The concept of a p-efficient point of a probability distribution is used to derive various equivalent problem formulations and the concept of r-concave discrete probability distributions is introduced.
Mathematical ProgrammingContributions to the theory of stochastic programming
188 Citations1973András Prékopa
The theory presented in this paper is based to a large extent on recent results of the author concerning logarithmic concave measures on two stochastic programming decision models, where the solvability of the second stage problem only with a prescribed (high) probability is required.
Mathematical programming studiesUncapacitated lot-sizing: The convex hull of solutions
184 Citations1984Imre Bárány, Tony J. Van Roy +1 more
The convex hull of the solutions of the economic lot-sizing model is given, and an alternative formulation as a simple plant location problem is examined, and here too the convex Hull of solutions is obtained.
Mathematical ProgrammingLot-size models with backlogging: Strong reformulations and cutting planes
138 Citations1988Yves Pochet, Laurence A. Wolsey
An implicit description of the convex hull of solutions is given, and it is shown how the problem of finding a violated cutting plane can be solved as a linear program.
Mathematical Methods of Operations ResearchDual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution
126 Citations1990András Prékopa
This paper presents a method for the solution of a one stage stochastic programming problem, where the underlying problem is an LP and some of the right hand side values are random variables, by a dual type algorithm.
Management ScienceThe Theory of Search: Optimum Distribution of Search Effort
120 Citations1958A. Charnes, W. W. Cooper
Operations ResearchThe Probabilistic Set-Covering Problem
112 Citations2002Patrizia Beraldi, Andrzej Ruszczyński
The structure of the set of probabilistically efficient points of binary random vectors is analyzed, methods for their enumeration are developed, and specialized branch-and-bound algorithms for probabilistic set-covering problems are proposed.
Operations ResearchGenerating Alternative Mixed-Integer Programming Models Using Variable Redefinition
98 Citations1987Richard K. Martin
A theory of variable redefinition is developed based on relating the two sets of decision variables by a linear transformation, and methods for reformulating the special structure problem are described.
Operations Research LettersRelaxations for probabilistically constrained programs with discrete random variables
71 Citations1992Suvrajeet Sen
Methods of disjunctive programming are used to approximate the convex hull of the feasible region of the possible region of mathematical programs with probabilistic constraints in which the random variables are discrete.
Applied optimizationProgramming Under Probabilistic Constraint with Discrete Random Variable
71 Citations1998András Prékopa, Béla Vízvári +1 more
The solution method uses the concept of a p-Ievel efficient point (pLEP) intoduced by the first author (1990) and works in such a way that first all pLEP's are enumerated, then a cutting plane method does the rest of the job.
Statistica NeerlandicaStochastic programming in production planning: a case with none‐simple recourse
28 Citations1977ROBERTJ. PETERS, Klaas Jelmer Boskma +1 more