Séance MB7 - Méthodes de programmation mixte / Mixed Integer Programing Methods
Jour lundi, le 04 mai 2009 Salle Tal Gestion globale d'actifs inc. Président Jacques A. Ferland
Présentations
|
15h30- 15h55 |
Enhancing Benders Decomposition |
|
Fausto Errico, Université du Québec à Montréal, CIRRELT, Montreal, QC, Canada Teodor Gabriel Crainic, Université du Québec à Montréal, C.P. 8888, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3P8 Federico Malucelli, Politecnico di Milano, DEI, Piazza Leonardo da Vinci 32, Milano, Italy, 20100 Maddalena Nonato, Università di Ferrara, Ingegneria, via Saragat 1, Ferrara, FE, Italy, 44100 The main drawbacks of the Benders decomposition approach for the solution of large-scale MIPs are, on one hand, the difficulty of finding a good initial set of bender cuts and, on the other side, the slow convergence rates. We present methods to improve Benders decomposition performances and discuss computational results. |
|
15h55- 16h20 |
An Efficient Algorithm for Set-Partitiong Problems with Additional Linear Constraints |
|
Issmail El Hallaoui, GERAD, Montreal, Quebec, Canada, H3T2A7 François Soumis, GERAD, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7 The IPS algorithm is an improved version of the primal simplex algorithm that reduces degeneracy in general linear problems. Dynamic constraint aggregation (DCA) is an efficient specialization of IPS to set-partitioning problems. In this presentation, we propose a combination of both methods to solve efficiently set-partitioning problems with additional linear constraints by column generation. |
|
16h20- 16h45 |
Generalized Resolution Search |
|
Marius M. Posta, Université de Montréal, Informatique et Recherche Opérationelle, Pavillon André Aisenstadt, 2920 Chemin de la tour, Montréal, QC, Canada, H3T 1J4 Jacques A. Ferland, Université de Montréal, DIRO, C.P. 6128, succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7 Philippe Michelon, Université d'Avignon, Laboratoire d'Informatique - LIA, 309, Chemin des Meinaijaries, 84911 Avignon, France Difficult discrete optimization problems are often solved using a Branch and Bound approach. Resolution Search is an alternate approach proposed by Chvatal for 0-1 problems, allowing more flexibility in the search process. We generalize Resolution Search to any discrete problem. |