Optimization Online


Polyhedral Aspects of Self-Avoiding Walks

Agnes Dittel(dittel***at***mathematik.tu-darmstadt.de)
Armin F├╝genschuh(fuegenschuh***at***zib.de)
Alexander Martin(alexander.martin***at***math.uni-erlangen.de )

Abstract: 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.

Keywords: Protein Folding; Integer Programming; Polyhedral Analysis; Cutting Planes

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: ZIB-Report 11-11

Download: [PDF]

Entry Submitted: 07/13/2012
Entry Accepted: 07/14/2012
Entry Last Modified: 07/13/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society