TY - GEN A1 - Schulz, Andreas S. A1 - Weismantel, Robert A1 - Ziegler, Günter M. T1 - 0/1-Integer Programming: Optimization and Augmentation are Equivalent N2 - {\def\xnew{x^{\mbox{\tiny new}}}\def\Z{{{\rm Z}\!\! Z}}For every fixed set ${\cal F}\subseteq\{0,1\}^n$ the following problems are strongly polynomial time equivalent: given a feasible point $x\in\cal F$ and a linear objective function $c\in\Z^n$, \begin{itemize} \item find a feasible point $x^*\in\cal F$ that maximizes $cx$ (Optimization), \item find a feasible point $\xnew\in\cal F$ with $c\xnew>cx$ (Augmentation), and \item find a feasible point $\xnew\in\cal F$ with $c\xnew>cx$ such that $\xnew-x$ is ``irreducible''\\(Irreducible Augmentation). \end{itemize} This generalizes results and techniques that are well known for $0/1$--integer programming problems that arise from various classes of combinatorial optimization problems.} T3 - ZIB-Report - SC-95-08 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1744 ER - TY - GEN A1 - Bruns, Winfried A1 - Gubeladze, Joseph A1 - Henk, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - A counterexample to an integer analogue of Caratheodorys theorem N2 - For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed. T3 - ZIB-Report - SC-98-28 KW - Integral pointed cones KW - Hilbert basis KW - integral Carathéodory property Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3718 ER - TY - GEN A1 - Weismantel, Robert A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - A Cutting Plane Based Algorithm for the Multiple Knapsack Problem. N2 - In this paper we describe a cutting plane based algorithm for the multiple knapsack problem. We use our algorithm to solve some practical problem instances arising in the layout of electronic circuits and in the design of main frame computers, and we report on our computational experience. This includes a discussion and evaluation of separation algorithms, an LP-based primal heuristic and some implementation details. The paper is based on the polyhedral theory for the multiple knapsack polytope developed in our companion paper SC 93-04 and meant to turn this theory into an algorithmic tool for the solution of practical problems. T3 - ZIB-Report - SC-93-07 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1031 ER - TY - GEN A1 - Urbaniak, Regina A1 - Weismantel, Robert A1 - Ziegler, Günter M. T1 - A New Variant of Buchberger's Algorithm for Integer Programming N2 - In this paper we modify Buchberger's $S$-pair reduction algorithm for computing a Gröbner basis of a toric ideal so as to apply to an integer program in inequality form with fixed right hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented and we give elementary proofs for their correctness. A relationship between these (exact) algorithms, iterative improvement heuristics and the Kernighan-Lin procedure is established. T3 - ZIB-Report - SC-94-29 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1570 ER - TY - GEN A1 - Helmberg, Christoph A1 - Rendl, Franz A1 - Weismantel, Robert T1 - A Semidefinite Programming Approach to the Quadratic Knapsack Problem N2 - We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations. T3 - ZIB-Report - SC-96-10 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2211 ER - 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 - Martin, Alexander A1 - Weismantel, Robert T1 - Contributions to General Mixed Integer Knapsack Problems N2 - This paper deals with a general mixed integer knapsack polyhedron for which we introduce and analyze a new family of inequalities. We discuss the value of this family both from a theoretic and a computational point of view. T3 - ZIB-Report - SC-97-38 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3075 ER - TY - GEN A1 - Helmberg, Christoph A1 - Weismantel, Robert T1 - Cutting Plane Algorithms for Semidefinite Relaxations N2 - We investigate the potential and limits of interior point based cutting plane algorithms for semidefinite relaxations on basis of implementations for max-cut and quadratic 0-1 knapsack problems. Since the latter has not been described before we present the algorithm in detail and include numerical results. T3 - ZIB-Report - SC-97-02 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2719 ER - TY - GEN A1 - Marchand, Hugues A1 - Martin, Alexander A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - Cutting Planes in Integer and Mixed Integer Programming N2 - This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored. T3 - ZIB-Report - SC-99-44 KW - Mixed Integer Programming KW - Cutting Planes Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4339 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs N2 - This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code. T3 - ZIB-Report - SC-97-54 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3230 ER -