10:30 AM - 10:55 AM
Stabilized Dynamic Constraint Aggregation for Solving Set Partitioning Problems
In column generation,dynamic constraint aggregation and dual variable stabilization reduce the negative impact of degeneracy. The stabilized dynamic constraint aggregation combines these methods for solving set partitioning problems. Computational results indicate a reduction of the average CPU time of the master problem by a factor of up to 7.
10:55 AM - 11:20 AM
Improved Column Generation for Degenerate Master Problems
Column generation suffers from tailing-off effect. The Improved Column Generation takes advantage of degeneracy and operates with a row-reduced master problem, the size of it being only the number of positive variables. The generation of a convex combination of variables allows for a strict decrease of the objective function.
11:20 AM - 11:45 AM
Parallel Integral Simplex Using Decomposition
This work aims at solving to optimality huge set partitioning problems by the parallel integral simplex using decomposition algorithm. We decompose the problem into sub-problems by fast, self-adjusted and non-problem-dependent procedure in order to solve them in parallel. The solutions of sub-problems are concatenated at each iteration in order to improve the current solution.
11:45 AM - 12:10 PM
Stabilization of a Complementary Problem
We present an algorithm for stabilizing a highly degenerate linear program
(LP) solved by column generation. The (LP) optimizes the objective
function over the null space of a matrix. It is particularly used in the Improved
Primal Simplex Algorithm as a complementary problem to find feasible
descent directions. We report computational results obtained for the multidepot
vehicle scheduling problem.