Optimization Online


Tractable algorithms for chance-constrained combinatorial problems

Olivier Klopfenstein(olivier.klopfenstein***at***orange-ftgroup.com)

Abstract: This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0-1 problems. Furthermore, its tractability is highlighted. Then, an optimization algorithm is designed to provide possibly good solutions to chance-constrained combinatorial problems. This approach is numerically tested on knapsack and multi-dimensional knapsack problems. The results obtained outperform many methods based on earlier literature.

Keywords: stochastic programming, chance-constrained programming, integer linear programming, robus optimization, heuristics, knapsack

Category 1: Combinatorial Optimization

Category 2: Stochastic Programming

Category 3: Robust Optimization


Download: [PDF]

Entry Submitted: 06/26/2007
Entry Accepted: 06/26/2007
Entry Last Modified: 06/26/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society