Extensions of the Group Theoretic Approach in Integer Programming

Laurence A. Wolsey
Additional contact information
Laurence A. Wolsey: University of Manchester, Manchester, England

Management Science, 1971, vol. 18, issue 1, 74-83

Abstract: By relaxing the nonnegativity constraints on a set of basic variables, an integer programming problem can be reduced to a shortest route problem over a finite Abelian group. Here it is shown how given a similar relaxation on any set of variables, a structurally simpler problem is obtained, which can be regarded as a shortest route problem over an Abelian (but not necessarily finite) group. In particular if the non-negativity constraints are relaxed on all but one of a set of basic variables, a knapsack (or very close to knapsack) problem is obtained, which either gives the solution of the integer problem, or when solved by dynamic programming provides bounds at least as strong as those provided by the above group problem. The difficulty that arises when the order of groups encountered is very large is also considered in the same framework, and by further relaxation it is shown how the groups can be reduced to manageable size, which can be used to provide simple bounds for the above group problem. Finally applications of these results are suggested with reference to various existing integer programming algorithms.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.18.1.74 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:18:y:1971:i:1:p:74-83

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().