TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Conjunctive Cuts for Integer Programs N2 - This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view. T3 - ZIB-Report - SC-98-18 KW - Polyhedral Combinatorics KW - Integer Programming KW - Separation Algorithm Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3618 ER - TY - GEN A1 - Dittel, Agnes A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - Polyhedral Aspects of Self-Avoiding Walks N2 - 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. T3 - ZIB-Report - 11-11 KW - Polyhedral Combinatorics KW - Integer Programming KW - Self-Avoiding Path KW - Protein Folding Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12576 ER -