Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

Weighted Consecutive Ones Problems

Oswald, Marcus

German Title: Gewichtete Consecutive Ones Probleme

[img]
Preview
PDF, English
Download (871Kb) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the persistent URL or the URN below, as we can guarantee their long-time accessibility.

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.

Item Type: Dissertation
Supervisor: Reinelt, Prof. Dr. Gerhard
Date of thesis defense: 28. May 2003
Date Deposited: 10. Jul 2003 13:48
Date: 2003
Faculties / Institutes: The Faculty of Mathematics and Computer Science > Department of Computer Science
Subjects: 510 Mathematics
Controlled Keywords: Kombinatorische Optimierung, Polyedrische Kombinatorik, Branch-and-Cut-Methode
Uncontrolled Keywords: Consecutive One s, Polytope , Branch-and-Cut
About | FAQ | Contact | Imprint |
OA-LogoLogo der Open-Archives-Initiative