Counting solutions of integer programs using unrestricted subtree detection
Please always quote using this URN: urn:nbn:de:0297-zib-10632
- In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection.
Download full text files
Additional Services
| Author: | Tobias AchterbergORCiD, Stefan Heinz, Thorsten KochORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | IP; Zählen; ganzzahlige Programme IP; counting; integer programming |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming |
| Date of first Publication: | 2008/02/26 |
| Series (Serial Number): | ZIB-Report (08-09) |
| ISSN: | 1438-0064 |
| ZIB-Reportnumber: | 08-09 |
| Published in: | App. in: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems : 5th International Conference, CPAIOR 2008 Paris, France, 2008; proc., Laurent Perron ... (eds.), LNC 5015, Springer 2008, pp. 278-282 |
