## 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.

### Additional Services

Author: Tobias Achterberg, Stefan Heinz, Thorsten Koch ZIB-Report IP; Zählen ; ganzzahlige Programme IP; counting ; integer programming 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming 2008/02/26 ZIB-Report (08-09) 1438-0064 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

$Rev: 13581$