10:30 AM - 10:55 AM
Personalized Crew Pairing and Crew Assignment Problem
We present a set-covering formulation and a solution approach based on column generation for the personalized airline cabin crew scheduling problem in which the objective is optimizing the costs and the crew’s preferences. The computational results are provided based on a major US carrier data set.
10:55 AM - 11:20 AM
Taking Advantage of Degeneracy in Mathematical Programming
I will introduce the basics concepts used by the presentations in the two following sessions. The Improved Primal Simplex and the integral simplex use a reduced master problem obtained by removing degenerated constraints and degenerated variables and a subproblem identifying non degenerated improving directions obtained by combining many degenerated variables
11:20 AM - 11:45 AM
A New Formulation of the Integral Simplex Using Decomposition with Cutting-Planes Algorithm
We present a new formulation of the integral simplex using decomposition for the set-partitioning problem. This formulation is based on a geometrical approach of the decomposition, yielding an innovative cutting-plane algorithm. Numerical results will be shown for aircrew and bus-drivers scheduling.
11:45 AM - 12:10 PM
Integral Simplex and Additional Constraints
We adapt the integral simplex algorithm of Zaghrouti and al to solve problems where besides the set partitioning constraints there are others constraints which do not have any particular structure. We use Lagrangian relaxation techniques to treat those constraints and present our results along with those of CPLEX.
12:10 PM - 12:35 PM
Integral Simplex Using Decomposition for the Set Partitioning Problem
The decomposition algorithm efficiently deals with the degenerate nature of Set Partitioning Problems. It's a constructive method that uses sub-problems to find compatible variables that improve an integer solution by only using normal simplex pivots. Optimal solutions are often obtained, for large-scale problems (up to 500000 variables), without any branching.