Integral simplex using double decomposition for set partitioning problems

Omar Foutlane

doi:10.1016/j.cor.2019.06.016

Integral simplex using double decomposition for set partitioning problems

2019-11-01

1

PRE

AI

DOI：10.1016/j.cor.2019.06.016

原文链接

原文求助

摘要

En 中文

The integral simplex using decomposition (ISUD) is a primal algorithm dedicated to solve set partitioning problems (SPP). 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 the integral simplex using double decomposition (ISU2D) which is a parallel version of ISUD. 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 3 to 4 times faster than ISUD on large instances. (C) 2019 Elsevier Ltd. All rights reserved.

Keyword:

Set partitioning problems

Integral simplex

Parallel computing

Integral simplex using double decomposition for set partitioning problems

摘要

AI总结

期刊

机构

引用论文