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

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Tobias Achterberg, Stefan Heinz, Thorsten Koch
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)
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