EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
523. Integral Simplex for the Set Partitioning Problem
Invited abstract in session WB-29: Large Scale Optimization in Air Transportation, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: 157 (building: 208)
Authors (first author is the speaker)
| 1. | Francois Soumis
|
| GERAD | |
| 2. | Alpha Saliou Barry
|
| GERAD, Polytechnique | |
| 3. | Frédéric Quesnel
|
| GERAD | |
| 4. | Issmail El Hallaoui
|
| Math. and Ind. Eng., Polytechnique Montréal and GERAD |
Abstract
For the set partitioning problem, the existence of a sequence of integer solutions with non-increasing costs produced by simplex pivots, permitting to reach optimality was proved by Balas, Padberg 1972. Finding the following term in the sequence can be very time-consuming due to degeneracy. When there is no entering variable that leads to a better integer solution, we use a linear programming sub-problem to find a group of variables to enter the basis to obtain an improved solution which is integer most of the time. When this solution is not integer, we solve a small integer programming problem to obtain a better integer solution.
We first, present results for large-scale problems (with up to 500 000 variables) for which optimal integer solutions are obtained, most of the time, without any branching. We also, present the integration of this new approach with column generation and parallelism to solve large-scale bus driver and airline pilot problems. Problems with many thousand tasks are solved 5 to 10 faster than with branch and price based on CPLEX
Keywords
- Programming, Integer
- Airline Applications
- Column Generation
Status: accepted
Back to the list of papers