Easy distributions for combinatorial optimization problems with probabilistic constraints

Fortz, Bernard; Poss, M.

doi:10.1016/j.orl.2010.09.005

Download

Article (Scientific journals)

Easy distributions for combinatorial optimization problems with probabilistic constraints

Fortz, Bernard; Poss, M.

2010 • In Operations Research Letters, 38 (6), p. 545-549

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/323935

DOI
10.1016/j.orl.2010.09.005

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Easy-distributions-combinatorial-optimization-problems.pdf

Author postprint (441.33 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Combinatorial optimization; Probabilistic constraint; Stochastic programming

Abstract :

[en] We show how we can linearize individual probabilistic linear constraints with binary variables when all coefficients are independently distributed according to either N(μi,λμi), for some λ>0 and μi>0, or Γ(ki,θ) for some θ>0 and ki>0. The constraint can also be linearized when the coefficients are independent and identically distributed and either positive or strictly stable random variables.

Disciplines :

Quantitative methods in economics & management

Author, co-author :

Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt

Poss, M.

Language :

English

Title :

Easy distributions for combinatorial optimization problems with probabilistic constraints

Publication date :

2010

Journal title :

Operations Research Letters

ISSN :

0167-6377

eISSN :

1872-7468

Volume :

Issue :

Pages :

545-549

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-77958084059&doi=10.1016%2fj.orl.2010.09.005&partnerID=40&md5=92efc4a181be1c63c2a6c36c2c3b80a8

Available on ORBi :

since 28 October 2024

Statistics

Number of views

7 (2 by ULiège)

Number of downloads

2 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

F. Alagz Approximations on the aggregate mpeg video traffic and their impact on admission control Turk. J. Electr. Eng. 10 1 2002 73 84
A. Altin, E. Amaldi, P. Belotti, and M.. Pinar Provisioning virtual private networks under traffic uncertainty Networks 49 1 2007 100 115
R. Andrade, A. Lisser, N. Maculan, and G. Plateau Telecommunication network capacity design for uncertain demand Comput. Optim. Appl. 29 2 2004 127 146
C. Barnhart, C.A. Hane, and P.H. Vance Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems Oper. Res. 48 2 2000 318 326
P. Beraldi, and M.E. Bruni A probabilistic model applied to emergency service vehicle location European J. Oper. Res. 196 1 2009 323 331
P. Beraldi, and M.E. Bruni An exact approach for solving integer problem under probabilistic constraints with random technology matrix Ann. Oper. Res. 177 2010 127 137
P. Beraldi, and A. Ruszczynski A branch and bound method for stochastic integer problems under probabilistic constraints Optim. Methods Softw. 17 2002 359 382
P. Beraldi, and A. Ruszczynski The probabilistic set-covering problem Oper. Res. 50 6 2002 956 967
P. Beraldi, and A. Ruszczynski Beam search heuristic to solve stochastic integer problems under probabilistic constraints European J. Oper. Res. 167 1 2005 35 47
O. Berman, and D. Krass Facility location problems with stochastic demands and congestion Z. Drezner, H.W. Hamacher, Facility Location: Applications and Theory 2004 Springer 329 371 (Chapter 11)
P. Bonami, M. Kilinc, J. Linderoth, Algorithms and software for convex mixed integer nonlinear programs, Tech. Report 1664, Computer Sciences Department, University of Wisconsin-Madison, 2009.
G. Calafiore, and L. El Ghaoui Distributionally robust chance-constrained linear programs with applications J. Optim. Theory Appl. 130 1 2006 1 22
D. Dentcheva, A. Prkopa, and A. Ruszczynski Bounds for probabilistic integer programming problems Discrete Appl. Math. 124 13 2002 55 65
C. Grinstead, and J. Snell Introduction to Probability 2nd edition 1997 American Math. Society Providence
I.E. Grossmann Review of nonlinear mixed-integer and disjunctive programming techniques Optim. Eng. 3 26 2002 227 252
P. Hansen, and C. Meyer Improved compact linearizations for the unconstrained quadratic 01 minimization problem Discrete Appl. Math. 157 2009 1267 1290
R. Henrion, Introduction to chance-constrained programming, Tutorial Paper for the Stochastic Programming Community Home Page, 2004.
R. Henrion, and C. Strugarek Convexity of chance constraints with independent random variables Comput. Optim. Appl. 41 2008 263 276
S. Kataoka A stochastic programming model Econometrica 31 1/2 1963 181 196
J. Kilpi, and I. Norros Testing the gaussian approximation of aggregate traffic IMW'02: Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurment 2002 ACM New York, NY, USA 49 61
O. Klopfenstein Solving chance-constrained combinatorial problems to optimality Comput. Optim. Appl. 45 3 2010 607 638
O. Klopfenstein, D. Nace, Valid inequalities for a robust knapsack polyhedron-application to the robust bandwidth packing problem, Networks (2010) (in press).
M.A. Lejeune, and A. Ruszczynski An efficient trajectory method for probabilistic productioninventory-distribution problems Oper. Res. 55 2 2007 378 394
A. Lisser, A. Ouorou, J.-P. Vial, J. Gondzio, Capacity planning under uncertain demand in telecommunication networks, Tech. report, 1999.
J. Luedtke, and S. Ahmed A sample approximation approach for optimization with probabilistic constraints SIAM J. Optim. 19 2 2008 674 699
R. Morris, D. Lin, Variance of aggregated web traffic, in: Proceedings of INFOCOM, 2000, pp. 360366.
J.P. Nolan, Stable Distributions-Models for Heavy Tailed Data, Birkhuser, Boston, 2010 (in progress), Chapter 1 online at: academic2.american.edu/ ~jpnolan.
B. Pagnoncelli, S. Ahmed, and A. Shapiro Sample average approximation method for chance constrained programming: theory and applications J. Optim. Theory Appl. 142 2009 399 416
S. Parikh, Lecture Notes on Stochastic Programming, University of California, Berkeley, CA, 1968.
K. Park, S. Kang, and S. Park An integer programming approach to the bandwidth packing problem Manage. Sci. 42 9 1996 1277 1291
F. Pascali, Chance constrained network design, Ph.D. thesis, Universit di Pisa, 2009.
A. Prkopa Dual method for a one-stage stochastic programming with random rhs obeying a discrete probability distribution Z. Oper. Res. 34 1990 441 461
A. Prkopa Stochastic Programming 1995 Kluwer
A. Prkopa Probabilistic programming models A. Ruszczynski, A. Shapiro, Stochastic Programming: Handbook in Operations Research and Management Science vol. 10 2003 Elsevier Science Ltd. Amsterdam 267 351 (Chapter 5)
A. Saxena, V. Goyal, and M.A. Lejeune MIP reformulations of the probabilistic set covering problem Math. Program. 121 1 2009 1 31
S. Sen, R.D. Doverspike, and S. Cosares Network planning with random demand Telecommun. Syst. 3 1 1994 11 30
A. Shapiro, D. Dentcheva, and A. Ruszczynski Lectures on Stochastic Programming: Modeling and Theory 2009 SIAM Philadelphia
D. Spoerl, R.K. Wood, A stochastic generalized assignment problem, INFORMS Annual Meeting, Atlanta, GA, 1922 October, 2003.
C. van de Panne, and W. Popp Minimum-cost cattle feed under probabilistic protein constraints Manag. Sci. 9 3 1963 405 430