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.

Download full text files

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.