Document
Services
BibSonomy
CiteUlike
Connotea
Del.icio.us
Digg
Facebook
|
||||||||||||||||||
RAIRO-Oper. Res. 43 (2009) 157-187
DOI: 10.1051/ro/2009010
Tractable algorithms for chance-constrained combinatorial problems
Olivier Klopfenstein1, 21 France Télécom R&D, 38-40 rue du gl Leclerc, 92130 Issy-les-Moulineaux, France; olivier.klopfenstein@orange-ftgroup.com
2 Université de Technologie de Compiègne, Laboratoire Heudiasyc UMR CNRS 6599, 60205 Compiègne Cedex, France
Received April 17, 2007. Accepted July 15, 2008. Published online 28 April 2009
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.
Mathematics Subject Classification. 90C10, 90C15.
Key words: Integer linear programming, chance constraints, robust optimization, heuristic.
© EDP Sciences, ROADEF, SMAI 2009
| What is OpenURL? |
The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
- If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
- You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
- You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.