Séance TA9 - Progrès récents en programmation mixte / Advances in Mixed-Integer Programming
Jour mardi, le 8 mai 2007 Salle Rona Président Dominique Orban
Présentations
|
10h30- 10h55 |
Reaching Feasibility Quickly in Mixed-Integer Programming Part I: Tutorial on the State of the Art |
|
John W. Chinneck, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, Ontario, Canada, K1S 5B6 This talk provides a tutorial overview of existing algorithms for reaching feasibility quickly in mixed-integer and binary programs. The main techniques reviewed are pivot-and-shift/complement, the OCTANE heuristic, and the feasibility pump. |
|
10h55- 11h20 |
Reaching Feasibility Quickly in Mixed-Integer Programming Part II: New Branching Heuristics |
|
John W. Chinneck, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, Ontario, Canada, K1S 5B6 New rules for the selection of the branching variable during branch and bound can significantly reduce the time to reach feasibility in mixed-integer and binary programs. We describe these new algorithms and present empirical results sharing very favourable results in comparison to a state-of-the-art commercial MIP solver. |
|
11h20- 11h45 |
Faster MIP Solutions via New Node Selection Rules |
|
Daniel T. Wojtaszek, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, Ontario, Canada, K1S 5B6 John W. Chinneck, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, Ontario, Canada, K1S 5B6 MIP solution effort can be reduced by changing the node selection rules. One approach is to generate a reasonably accurate estimate of the optimum objective function value and to use this to guide the node selection process. We present empirical results for this approach, and describe other node selection heuristics that are under study. |
|
11h45- 12h10 |
An Integer Cutting-Plane Procedure for the Dantzig-Wolfe Decomposition |
|
Troels Martin Range, University of Southern Denmark, Department of Business & Economics, Campusvej 55, Odense, M, Denmark, 5230 We introduce a new procedure for generating violated valid integer inequalities to the master problem of the integer Dantzig-Wolfe decomposition. It uses an auxiliary LP in which ordinary integer cuts can be applied and it does not change the structure of pricing problem yielding a robust Branch-Price-and-Cut algorithm. |