Back to Search
Start Over
Improved Combinatorial Programming Algorithms for a Class of All-Zero-One Integer Programming Problems
- Source :
- Management Science. 19:528-543
- Publication Year :
- 1973
- Publisher :
- Institute for Operations Research and the Management Sciences (INFORMS), 1973.
-
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.
Details
- ISSN :
- 15265501 and 00251909
- Volume :
- 19
- Database :
- OpenAIRE
- Journal :
- Management Science
- Accession number :
- edsair.doi.dedup.....cf93a4ef9094c627e7f72eb0951e4441