Using decomposition in integer programming

Linus Schrage

Naval Research Logistics Quarterly, 1973, vol. 20, issue 3, 469-476

Abstract: When implicit enumeration algorithms are used for solving integer programs, a form of primal decomposition can be used to reduce the number of solutions which must be implicitly examined. If the problem has the proper structure, then under the proper decomposition a different enumeration tree can be defined for which the number of solutions which must be implicitly examined increases with a power of the number of variables rather then exponentially. The proper structure for this kind of decomposition is that the southwest and northeast corners of the constraint matrix be zero or equivalently that the matrix be decomposable except for linking columns. Many real traveling salesmen, plant location, production scheduling, and covering problems have this structure.

Date: 1973
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800200309

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:wly:navlog:v:20:y:1973:i:3:p:469-476

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().