Improved Combinatorial Programming Algorithms for a Class of All-Zero-One Integer Programming Problems

John F. Pierce and Jeffrey S. Lasky
Additional contact information
John F. Pierce: Management Decisions Development Corporation, Cincinnati, Ohio
Jeffrey S. Lasky: Northeastern University

Management Science, 1973, vol. 19, issue 5, 528-543

Abstract: In an earlier paper [Pierce, J. F. 1968. Application of combinatorial programming to a class of all-zero-one integer programming problems. Management Sci. 15 (3, November) 191-209.] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions.

Date: 1973
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.19.5.528 (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:5:p:528-543

Access Statistics for this article

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