Decomposition of the Group Problem in Integer Programming.
Abstract
Group theoretic algorithms for solving linear integer programming problems have been proposed by Gomory and extended by Shapiro. An essential and time-consuming task in these algorithms is solving a programming problem which is a defined on a finite abelian group. The computational effort required to solve this group problem can be significantly reduced if the problem can be decomposed. A method is presented in this paper for decomposing the group problem into subproblems which are defined on subgroups of the original problem. These subproblems can be solvee by any of the existing group programming algorithms. The total number of variables in the subproblems is the same as the number in the original problem, and each subproblem is folved only once. The solutions to a group linking problem are used to obtain the solutions to the original problem. This paper includes an algorithm for solving the group linking problem. Tests have been made to compare the solution times for the group problem with and without decomposition. The results of these tests indicate significant savings in computational effort can be achieved by decomposing the group problem. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1971
- Accession Number
- AD0731785
Entities
People
- Gerald L. Hefley
- M. E. Thomas
Organizations
- University of Florida