German Title: Gewichtete Consecutive Ones Probleme

PDF, English
Download (871Kb)  Terms of use 
Abstract
A 0/1matrix 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/1matrix 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 PQtree algorithm, it is NPhard to optimize a linear objective function over all 0/1matrices 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 branchandcut 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 branchandcut 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, BranchandCutMethode 
Uncontrolled Keywords:  Consecutive One s, Polytope , BranchandCut 