The Equivalence of Integer Programs to Constrained Recursive Systems

Patanjali S. Nanda
Additional contact information
Patanjali S. Nanda: Syracuse University

Management Science, 1973, vol. 19, issue 7, 809-824

Abstract: It has been established that integer programs with integral, recursive constraint matrices have integral extreme points for integral, nonnegative requirement vectors. In this paper, it is first shown that the assignment problem can be transformed to such a program, but with upper bounds on some variables. This equivalent program leads to additional results for solving the assignment problem. Algorithms are then delineated to transform matching, covering and travelling salesman problems to equivalent recursive programs of the aforementioned type, but with bounds on some variables. These results are extended to programs with special structure in their constraint matrices.

Date: 1973
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.19.7.809 (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:19:y:1973:i:7:p:809-824

Access Statistics for this article

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