-

 

 

 




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

Citation:

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

 

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