Direkt zum Inhalt
  1. Publizieren |
  2. Suche |
  3. Browsen |
  4. Neuzugänge rss |
  5. Open Access |
  6. Rechtsfragen |
  7. EnglishCookie löschen - von nun an wird die Spracheinstellung Ihres Browsers verwendet.

Weighted Consecutive Ones Problems

Oswald, Marcus

Deutsche Übersetzung des Titels: Gewichtete Consecutive Ones Probleme

[thumbnail of diss.pdf]
Vorschau
PDF, Englisch
Download (891kB) | Nutzungsbedingungen

Zitieren von Dokumenten: Bitte verwenden Sie für Zitate nicht die URL in der Adresszeile Ihres Webbrowsers, sondern entweder die angegebene DOI, URN oder die persistente URL, deren langfristige Verfügbarkeit wir garantieren. [mehr ...]

Abstract

A 0/1-matrix has the consecutive ones property (for rows) if its columns can be permuted in such a way that in every row all ones appear consecutively. The consecutive ones property for columns is defined analogously. Furthermore a 0/1-matrix has the simultaneous consecutive ones property if it has both the consecutive ones property for rows and for columns. Whereas deciding whether a given matrix has the (simultaneous) consecutive ones property can be done in linear time by the PQ-tree algorithm, it is NP-hard to optimize a linear objective function over all 0/1-matrices with (simultaneous) consecutive ones property. The latter problem is called Weighted (Simultaneous) Consecutive Ones Problem WC1P (WSC1P). In this thesis we study both the WC1P and the WSC1P from a polyhedral point of view and derive integer programming formulations consisting only of facets of the corresponding polytopes. Additionally polynomial separation procedures are given for all these classes of inequalities. Therefore this IP formulation serves as a good basis for a branch-and-cut algorithm which is used to solve the WC1P and the WSC1P to optimality. New ideas for separating and for primal heuristics are given which improve the algorithm substantially. The thesis continues with an overview of several applications of the WC1P and the WSC1P, for example the Physical Mapping Problem occurring in computational biology or the problem of finding clusters of inorganic crystal structure types. Finally computational results are presented which show that the branch-and-cut code provides a useful tool for tackling WC1P and WSC1P problems occurring in practice.

Dokumententyp: Dissertation
Erstgutachter: Reinelt, Prof. Dr. Gerhard
Tag der Prüfung: 28 Mai 2003
Erstellungsdatum: 10 Jul. 2003 13:48
Erscheinungsjahr: 2003
Institute/Einrichtungen: Fakultät für Mathematik und Informatik > Institut für Informatik
DDC-Sachgruppe: 510 Mathematik
Normierte Schlagwörter: Kombinatorische Optimierung, Polyedrische Kombinatorik, Branch-and-Cut-Methode
Freie Schlagwörter: Consecutive One s, Polytope , Branch-and-Cut
Leitlinien | Häufige Fragen | Kontakt | Impressum |
OA-LogoDINI-Zertifikat 2013Logo der Open-Archives-Initiative