Eingang zum Volltext


Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2008/1092/


Achterberg, Tobias ; Heinz, Stefan ; Koch, Thorsten

Counting solutions of integer programs using unrestricted subtree detection

pdf-Format:
Dokument 1.pdf (364 KB)
ps-Format:
Dokument 1.ps (665 KB)


Kurzfassung in Englisch

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.

Freie Schlagwörter (deutsch): Zählen , ganzzahlige Programme , IP
Freie Schlagwörter (englisch): counting , integer programming , IP
MSC - Klassifikation 90C10
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 08-09
ISBN: 1438-0064
Quelle: Appeared in: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems : 5th International Conference, CPAIOR 2008 Paris, France, May 20 - 23, 2008; proceedings / Laurent Perron ... (eds.), Lecture Notes in Computer Science 5015, pp. 278-282, 2008
Sprache: Englisch
Erstellungsjahr: 2008
Publikationsdatum: 26.02.2008
Bemerkung: printed version not available / keine gedruckte Version verfügbar


Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: