EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3517. Integral simplex for generalized set partitioning problems

Invited abstract in session WB-29: Large Scale Optimization in Air Transportation, stream Combinatorial Optimization.

Wednesday, 10:30-12:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Alpha Saliou Barry
GERAD, Polytechnique
2. Frédéric Quesnel
GERAD
3. Issmail El Hallaoui
Math. and Ind. Eng., Polytechnique Montréal and GERAD
4. Francois Soumis
GERAD

Abstract

The set partitioning problem can be generalized. One generalization is to consider that certain tasks must be covered several times. So it's no longer a partition that's sought, but a set of parts that verify the right number of coverages.

Unlike the set partitioning problem, the graph of integer solutions is no longer connected when the possible arcs are simplex pivots. Howerver, in order to restore the connectedness of the graph, it is possible to add artificial variables locally, which allow new pivots to be made while preserving the integrity of the solution.

We give priority to pivots that keep the solution integer. When this is no longer possible, we solve a linear program to obtain a non-degenerate sequence of simplex pivots to perform in order to improve the solution. When this improved solution is still not integer, in some cases the pivot sequence allows to add an artificial column associated with an integer artificial point. The linear program is solved again from this point to find the remaining pivots to be performed in order to obtain a better integer solution. If integrity is still not reached, a branching is performed.

We present results for large pairing problems (around 2,000 constraints and 300,000 variables) and show that the method is around 2 to 5 times faster than traditional methods (CPLEX) and that in many cases, the addition of the artificial variable effectively allows moves on integer points not directly accessible by pivot.

Keywords

Status: accepted

Back to the list of papers