Technical Note—Computational Viability of a Constraint Aggregation Scheme for Integer Linear Programming Problems

Denis C. Onyekwelu
Additional contact information
Denis C. Onyekwelu: University of Benin, Benin City, Nigeria

Operations Research, 1983, vol. 31, issue 4, 795-801

Abstract: We present the results of a computational evaluation of two constraint aggregation approaches for solving integer linear programs. In some applications, particularly set partitioning problems, the schemes can aggregate significantly different number of constraints. We first discuss the implementation of these approaches using both single and multiple precision arithmetic. From these results, we empirically show that, in practical implementation and evaluation of an aggregation scheme, the degree of difficulty encountered in solving the resulting equality constrained knapsack problem is crucial. We conclude, as contrasted with the optimism expressed in some published works, that the aggregation approach has limited value for solving general integer linear programs, but may be useful in developing a heuristic algorithm for the set partitioning problem.

Keywords: 625 integer programming constraint aggregation; 633 set partitioning problems (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.31.4.795 (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:oropre:v:31:y:1983:i:4:p:795-801

Access Statistics for this article

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