Groupe d’études et de recherche en analyse des décisions

G-2017-73

Integral simplex using double decomposition

, et

Given an integer solution, the integral simplex using decomposition (ISUD) seeks a descent direction that leads to an improved adjacent integer solution. It uses a horizontal decomposition (of a linear transformation of the constraint matrix). We propose an integral simplex using double decomposition (ISU2D). It uses an innovative disjoint vertical decomposition to find in parallel orthogonal descent directions leading to an integer solution with a larger improvement. Each descent direction identifies a set of variables that will leave the current solution and a set of entering variables with better costs. To find these directions, we develop a dynamic decomposition approach that splits the original problem into subproblems that are then solved in parallel by ISUD. Our main innovation is the use of the current solution as a foundation for the construction of the set of subproblems; the set changes during the optimization process as the current solution changes. In addition, we use bounding and pricing strategies and implement parallel processing techniques. We show that ISU2D is faster than ISUD: 3 to 4 times faster on large instances.

, 26 pages