Group Programming Decomposition in Integer Programming.
Abstract
In the paper, a group programming problem is shown to be decomposable for a number of problems. The group programming problem is to minimize a real valued linear objective function subject to a single constraint and nonnegative integer variables. The constraint is defined on a finite abelian group. This problem occurs when using the asymptotic integer programming algorithm of Gomory to solve a linear program with integer constraint. An algorithm is developed which uses one of the existing group programming algorithms to solve subproblems. The total number of variables in the subproblems is the same as the number in the original problem. Each subproblem is solved only once and one linking problem is solved to obtain the optimal solution to the original problem. When decomposition is possible, significant savings in computational effort can be achieved. Examples are included to illustrate the method. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1971
- Accession Number
- AD0729910
Entities
People
- Gerald L. Hefley
- M. E. Thomas
Organizations
- University of Florida