Accession Number:

AD0729910

Title:

Group Programming Decomposition in Integer Programming.

Descriptive Note:

Technical rept.,

Corporate Author:

FLORIDA UNIV GAINESVILLE DEPT OF INDUSTRIAL AND SYSTEMS ENGINEERING

Personal Author(s):

Report Date:

1971-07-01

Pagination or Media Count:

80.0

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE