Session TA9 - Progrès récents en programmation mixte / Advances in Mixed-Integer Programming
Day Tuesday, May 8, 2007 Room Rona Chair Dominique Orban
Presentations
|
10h30 AM- 10h55 AM |
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 AM- 11h20 AM |
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 AM- 11h45 AM |
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 AM- 12h10 PM |
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. |