Eine Heuristik für quadratische 0-1-Probleme
- Eine neue Modellformulierung für kombinatorische Optimierungsprobleme wird vorgestellt. Auf der Grundlage des quadratischen 0-1-Problems ohne Nebenbedingungen wird ein vorteilhafter Typ kombinatorischer Optimierungsprobleme eingeführt. Eine einfache Heuristik, die sog. RII-Methode (randomized iterative improvement), erlaubt es, diesen Modelltyp effizient zu lösen. Die Flexibilität des Ansatzes wird an der Modellierung des K-Färbungsproblems gezeigt. Es werden Rechenergebnisse für Färbungsprobleme aus der Literatur präsentiert. Wendet man Randomized Iterative Improvement auf den neuen Modelltyp an, können diese Testprobleme effizient gelöst werden.
- A new model formulation for combinatorial optimization problems is presented. Based on the unconstrained quadratic program (binary quadratic program), a favourable type of combinatorial optimization problems is introduced. A simple heuristic method, i.e. randomized iterative improvement (RII), permits to solve this type of model efficiently. Modelling of the K-colouring problem shows the flexibility of the approach. Computational results on data sets from the literature about vertex colouring are reported. These benchmark problems are shown to be solved efficiently using randomized iterative improvement and the new type of model.
Author: | Matthias Forster |
---|---|
URN: | urn:nbn:de:kobv:526-opus-765 |
DOI: | https://doi.org/10.15771/0949-8214_2008_1_10 |
ISSN: | 0949-8214 |
Parent Title (German): | Wissenschaftliche Beiträge 2008 |
Document Type: | Article in a Periodical of the TH Wildau |
Language: | German |
Year of Publication: | 2008 |
Year of first Publication: | 2008 |
Publishing Institution: | Technische Hochschule Wildau |
Release Date: | 2009/03/18 |
Volume: | 13 |
First Page: | 67 |
Last Page: | 71 |
Faculties an central facilities: | Fachbereich Betriebswirtschaft / Wirtschaftsinformatik (bis 8/2014) |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
TH Wildau publications: | Wissenschaftliche Beiträge |
Licence (German): | Creative Commons - CC BY-NC-ND 3.0 DE - Namensnennung - Nicht-kommerziell - Keine Bearbeitung 3.0 Deutschland |