eprintid: 3588
rev_number: 8
eprint_status: archive
userid: 1
dir: disk0/00/00/35/88
datestamp: 2003-07-10 13:48:01
lastmod: 2014-04-03 13:01:15
status_changed: 2012-08-14 15:08:30
type: doctoralThesis
metadata_visibility: show
creators_name: Oswald, Marcus
title: Weighted Consecutive Ones Problems
title_de: Gewichtete Consecutive Ones Probleme
ispublished: pub
subjects: 510
divisions: 110300
adv_faculty: af-11
keywords: Consecutive One s, Polytope , Branch-and-Cut
cterms_swd: Kombinatorische Optimierung
cterms_swd: Polyedrische Kombinatorik
cterms_swd: Branch-and-Cut-Methode
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.
abstract_translated_lang: eng
class_scheme: msc
class_labels: branch-and, branch-and, 90Cxx Math
date: 2003
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00003588
ppn_swb: 164346597X
own_urn: urn:nbn:de:bsz:16-opus-35885
date_accepted: 2003-05-28
advisor: HASH(0x556120df8060)
language: eng
bibsort: OSWALDMARCWEIGHTEDCO2003
full_text_status: public
citation:   Oswald, Marcus  (2003) Weighted Consecutive Ones Problems.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/3588/1/diss.pdf