Decomposition of the Group Problem in Integer Programming.
FLORIDA UNIV GAINESVILLE DEPT OF INDUSTRIAL AND SYSTEMS ENGINEERING
Pagination or Media Count:
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
- Operations Research