A Novel LP-based Local Search Technique -Fast and Quite Good-

Avdil, Alaubek (2009)
A Novel LP-based Local Search Technique -Fast and Quite Good-.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-19149

Kurzbeschreibung (Abstract)

We present and evaluate a specific way to generate good start solutions for local search. The start solution is computed from a certain LP, which is the modification of the underlying problem. Generally speaking, we will look at the non-linear formulations of the problems and apply small modifications to transform the non-linear ingredients into linear ones. It is a requirement of our technique to work that the optimal basis solutions of the LP are feasible to the primary optimization problem. We consider four optimization problems: the directed Max-Cut problem with a source and a sink, and three variations of the Max-k-SAT problem with k=2, k=3 and k=4. In each case, we define the modification such that the vertices of the LP are integral, and that the simplex method will not end up at infinity. To compare our technique, we run local search repeatedly with random start solutions. Our technique produces consistently final solutions whose objective values are nearly identical to the best solutions from repeated random starts. The surprising degree of stability and uniformity of this result throughout all of our experiments on various classes of instances strongly suggests that we have consistently achieved nearly optimal solutions. Furthermore, an implementation of our technique to the Longest Directed Path problem with a source and a sink (in which we obtain an LP by incorporating flow-consistency inequalities) strongly supports our empirical findings. On the other hand, the run time of our technique is rather small, so the technique is very efficient and seemingly quite accurate.

Typ des Eintrags:

Dissertation

Erschienen:

2009

Autor(en):

Avdil, Alaubek

Art des Eintrags:

Erstveröffentlichung

Titel:

A Novel LP-based Local Search Technique -Fast and Quite Good-

Sprache:

Englisch

Referenten:

Weihe, Prof. Dr. Karsten ; Müller-Hannemann, Prof. Dr. Matthias

Publikationsjahr:

5 Oktober 2009

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

17 Juli 2009

URL / URN:

urn:nbn:de:tuda-tuprints-19149

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

Wir präsentieren und evaluieren eine neuartige Methode, die gute Start-Lösungen für die lokale Suche generiert. Die Start-Lösung wird von einem bestimmten linearen Programm (LP) bestimmt, das eine Modifikation des zugrunden liegenden Problems ist. Wir betrachten eine nicht-lineare Formulierung des Problems und wenden kleine Änderungen an, um die nicht-linearen Bestandteile der Formulierung in lineare Bestandteile umzuwandeln. Damit die Technik angewendet werden kann, ist es notwendig, dass die optimalen Basis-Lösungen des LPs zulässig für das primäre Optimierungsproblem sind. Wir untersuchen vier Optimierungsprobleme: das gerichtete Max-Cut Problem mit einem Start- und einem Endknoten, und drei Variationen des Max-k-SAT Problems mit k=2, k=3 und k=4. In jedem Fall definieren wir die Modifikation so, dass die Eckpunkte des resultierenden LP ganzzahlig sind, und dass die Simplex-Methode nicht im Unendlichen endet. Zum Vergleich mit unserer Technik benutzen wir eine wiederholte lokale Suche mit zufälligen Start-Lösungen. Unsere Technik produziert konsequent Lösungen, deren Ziel-Werte nicht allzu weit von den besten Lösungen aus wiederholten zufälligen Starts sind. Das überraschende Maß an Stabilität und der Einheitlichkeit der Ergebnisse in allen unseren Experimenten mit verschiedenen Klassen lassen den Schluss zu, dass wir konsequent nahezu optimale Lösungen erzielen. Darüber hinaus bestätigt eine Umsetzung unserer Technik auf das längste Pfad Problem zwischen zwei angegebenen Knoten (in denen wir das LP durch den Einbau der Fluss-Konsistenz-Ungleichungen herstellen) unsere empirische Befunde. Auf der anderen Seite ist die Laufzeit unserer Technik sehr klein, so dass diese sehr effizient ist.

Deutsch

Freie Schlagworte:

Algorithms, Computations on discrete structures, Design, Experimentation, Longest-Path, Max-Cut, Max-SAT, Max-k-SAT, Polyhedral combinatorics

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik > Algorithmik
20 Fachbereich Informatik

Hinterlegungsdatum:

23 Okt 2009 11:11

Letzte Änderung:

05 Mär 2013 09:28

PPN: