1257
eng
reportzib
0
2011-04-11
2011-04-11
--
Polyhedral Aspects of Self-Avoiding Walks
In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this problem one is interested in optimal configurations, where an energy function measures the benefit if certain path elements are placed on adjacent vertices of the graph. The most prominent application of this problem is the protein folding problem in biochemistry. On a set of selected instances, we demonstrate the computational merits of our approach.
11-11
urn:nbn:de:0297-zib-12576
Agnes Dittel
Armin Fügenschuh
Armin Fügenschuh
Alexander Martin
ZIB-Report
11-11
uncontrolled
Polyhedral Combinatorics
uncontrolled
Integer Programming
uncontrolled
Self-Avoiding Path
uncontrolled
Protein Folding
Paths and cycles [See also 90B10]
Integer programming
Polyhedral combinatorics, branch-and-bound, branch-and-cut
Protein sequences, DNA sequences
Mathematical Optimization
Fügenschuh, Armin
https://opus4.kobv.de/opus4-zib/files/1257/DittelFuegenschuhMartin2011.pdf