TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - Test sets of the knapsack problem and simultaneous diophantine approximation N2 - This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem. T3 - ZIB-Report - SC-97-13 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2825 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Consecutive Case N2 - We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.~e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets. T3 - ZIB-Report - SC-95-31 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1976 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 - 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 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Polyhedral Investigations. N2 - Let $G=(V,E)$ be a graph and $T\subseteq V$ be a node set. We call an edge set $S$ a Steiner tree with respect to $T$ if $S$ connects all pairs of nodes in $T$. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph $G=(V,E)$ with edge weights $w_e$, edge capacities $c_e, e \in E,$ and node sets $T_1,\ldots,T_N$, find edge sets $S_1,\ldots,S_N$ such that each $S_k$ is a Steiner tree with respect to $T_k$, at most $c_e$ of these edge sets use edge $e$ for each $e\in E$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing Problem from a polyhedral point of view and define an appropriate polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper SC 92-09. T3 - ZIB-Report - SC-92-08 KW - cutting planes KW - Facets KW - Packing KW - polyhedron KW - Steiner tree Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-786 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results. N2 - In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems. T3 - ZIB-Report - SC-92-09 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-792 ER - TY - GEN A1 - Jünger, Michael A1 - Martin, Alexander A1 - Reinelt, Gerhard A1 - Weismantel, Robert T1 - Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits. N2 - The placement in the layout design of electronic circiuts consists of finding a non- overlapping assignment of rectangular cells to positions on the chip so what wireability is guaranteed and certain technical constraints are met.This problem can be modelled as a quadratic 0/1- program subject to linear constraints. We will present a decomposition approach to the placement problem and give results about $NP$-hardness and the existence of $\varepsilon$-approximative algorithms for the involved optimization problems. A graphtheoretic formulation of these problems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines. {\bf Keywords:} Quadratic 0/1 optimization, Computational Complexity, VLSI-Design. T3 - ZIB-Report - SC-92-10 KW - quadratic 0/1 optimization KW - computational complexity KW - VLSI-Design Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-803 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 - Weismantel, Robert T1 - On the 0/1 Knapsack Polytope. N2 - {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Given a set $N$ of items and a capacity $b \in \N$, and let $N_j$ be the set of items with weight $j$, $1 \leq j \leq b$. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{j=1}^b \sum_{i \in N_j} jx_i \leq b.$$ In this paper we first present a complete linear description of the 0/1 knapsack polytope for two special cases: (a) $N_j = \emptyset$ for all $1 < j \leq \lfloor {b \over 2} \rfloor$ and (b) $N_j = \emptyset$ for all $1 < j \leq \lfloor {b \over 3} \rfloor$ and $N_j = \emptyset$ for all $j \geq \lfloor {b \over 2} \rfloor + 1$. It turns out that the inequalities that are needed for the complete description of these special polytopes are derived by means of some ``reduction principle''. This principle is then generalized to yield valid and in many cases facet defining inequalities for the general 0/1 knapsack polytope. The separation problem for this class of inequalities can be solved in pseudo polynomial time via dynamic programming techniques.} T3 - ZIB-Report - SC-94-01 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1312 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Steiner Tree Packing Problem in VLSI-Design. N2 - In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing. T3 - ZIB-Report - SC-94-02 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1328 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Grötschel, Martin A1 - Kiefl, Stefan A1 - Krispenz, Ludwig A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Some Integer Programs Arising in the Design of Main Frame Computers. N2 - In this paper we describe and discuss a problem that arises in the (global) design of a main frame computer. The task is to assign certain functional units to a given number of so called multi chip modules or printed circuit boards taking into account many technical constraints and minimizing a complex objective function. We describe the real world problem. A thorough mathematical modelling of all aspects of this problem results in a rather complicated integer program that seems to be hopelessly difficult -- at least for the present state of integer programming technology. We introduce several relaxations of the general model, which are also $NP$-hard, but seem to be more easily accessible. The mathematical relations between the relaxations and the exact formulation of the problem are discussed as well. T3 - ZIB-Report - SC-92-25 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-957 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Routing in Grid Graphs by Cutting Planes. N2 - {\def\N{{\cal N}} \def\R{\hbox{\rm I\kern-2pt R}} \def\MN{{\rm I\kern-2pt N}} In this paper we study the following problem, which we call the weighted routing problem. Let be given a graph $G=(V,E)$ with non-negative edge weights $w_e\in\R_+$ and integer edge capacities $c_e\in\MN$ and let $\N=\{T_1,\ldots,T_N\}$, $N\ge 1$, be a list of node sets. The weighted routing problem consists in finding edge sets $S_1,\ldots,S_N$ such that, for each $k\in\{1,\ldots,N\}$, the subgraph $(V(S_k),S_k)$ contains an $[s,t]$-path for all $s,t\in T_k$, at most $c_e$ of these edge sets use edge $e$ for each $e\in E$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the weighted routing problem from a polyhedral point of view. We define an appropriate polyhedron and try to (partially) describe this polyhedron by means of inequalities. We briefly sketch our separation algorithms for some of the presented classes of inequalities. Based on these separation routines we have implemented a branch and cut algorithm. Our algorithm is applicable to an important subclass of routing problems arising in VLSI-design, namely to problems where the underlying graph is a grid graph and the list of node sets is located on the outer face of the grid. We report on our computational experience with this class of problem instances.} T3 - ZIB-Report - SC-92-26 KW - routing in VLSI-design KW - Steiner tree KW - Steiner tree packing KW - cutting plane algorithm Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-967 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Further Facets. N2 - In this paper we continue the investigations in [GMW92a] for the \def\sbppo{Steiner tree packing polyhedron} \sbppo. We present several new classes of valid inequalities and give sufficient (and necessary) conditions for these inequalities to be facet-defining. It is intended to incorporate these inequalities into an existing cutting plane algorithm that is applicable to practical problems arising in the design of electronic circuits. T3 - ZIB-Report - SC-93-01 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-975 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Separation Algorithms. N2 - In this paper we investigate separation problems for classes of inequalities valid for the polytope associated with the Steiner tree packing problem, a problem that arises, e.~g., in VLSI routing. The separation problem for Steiner partition inequalities is ${\cal N}\hskip-2pt{\cal P}$-hard in general. We show that it can be solved in polynomial time for those instances that come up in switchbox routing. Our algorithm uses dynamic programming techniques. These techniques are also applied to the much more complicated separation problem for alternating cycle inequalities. In this case we can compute in polynomial time, given some point $y$, a lower bound for the gap $\alpha-a^Ty$ over all alternating cycle inequalities $a^Tx\ge\alpha$. This gives rise to a very effective separation heuristic. A by-product of our algorithm is the solution of a combinatorial optimization problem that is interesting in its own right: Find a shortest path in a graph where the ``length'' of a path is its usual length minus the length of its longest edge. T3 - ZIB-Report - SC-93-02 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-984 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Facets for the Multiple Knapsack Problem. N2 - In this paper we consider the multiple knapsack problem which is defined as follows: given a set $N$ of items with weights $f_i$, $i \in N$, a set $M$ of knapsacks with capacities $F_k$, $k \in M$, and a profit function $c_{ik}, i \in N, k \in M$; find an assignment of a subset of the set of items to the set of knapsacks that yields maximum profit (or minimum cost). With every instance of this problem we associate a polyhedron whose vertices are in one to one correspondence to the feasible solutions of the instance. This polytope is the subject of our investigations. In particular, we present several new classes of inequalities and work out necessary and sufficient conditions under which the corresponding inequality defines a facet. Some of these conditions involve only properties of certain knapsack constraints, and hence, apply to the generalized assignment polytope as well. The results presented here serve as the theoretical basis for solving practical problems. The algorithmic side of our study, i.e., separation algorithms, implementation details and computational experience with a branch and cut algorithm are discussed in the companion paper SC 93-07. T3 - ZIB-Report - SC-93-04 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1007 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Souza, Cid C. de A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem. N2 - We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change. T3 - ZIB-Report - SC-94-16 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1450 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Souza, Cid C. de A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - The Node Capacitated Graph Partitioning Problem: A Computational Study. N2 - In this paper we consider the problem of $k$-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. T3 - ZIB-Report - SC-94-17 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1469 ER - TY - GEN A1 - Weismantel, Robert T1 - Hilbert Bases and the Facets of Special Knapsack Polytopes. N2 - {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Let a set $N$ of items, a capacity $F \in \N$ and weights $a_i \in \N$, $i \in N$ be given. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{i \in N} a_i x_i \leq F.$$ In this paper we present a linear description of the 0/1 knapsack polytope for the special case where $a_i \in \{\mu,\lambda\}$ for all items $i \in N$ and $1 \leq \mu < \lambda \leq b$ are two natural numbers. The inequalities needed for this description involve elements of the Hilbert basis of a certain cone. The principle of generating inequalities based on elements of a Hilbert basis suggests further extensions.} T3 - ZIB-Report - SC-94-19 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1475 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Noncrossing Case. N2 - We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that no two terminal pairs cross, then a path packing, i.~e.,a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets. T3 - ZIB-Report - SC-93-26 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1225 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Paths and Steiner Trees: Routing of Electronic Circuits. N2 - One of the challenging problems in the design of electronic circuits is the so-called routing problem. Roughly speaking, the task is to connect so-called terminal sets via wires on a predefined area. In addition, certain design rules are to be taken into account and an objective function such as the wiring length must be minimized. The routing problem in general is too complex to be solved in one step. Depending on the user's choice of decomposing the chip design problem into a hierarchy of stages, on the underlying technology, and on the given design rules, various subproblems arise. We discuss several variants of practically relevant routing problems and give a short overview on the underlying technologies and design rules. Many of the routing problems that come up this way can be formulated as the problem of packing so-called Steiner trees in certain graphs. We consider the Steiner tree packing problem from a polyhedral point of view and present three possibilities to define an appropriate polyhedron. Weighing their pros and cons we decide for one of these polytopes and sketch some of our investigations. T3 - ZIB-Report - SC-93-15 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1113 ER - TY - GEN A1 - Sturmfels, Bernd A1 - Weismantel, Robert A1 - Ziegler, Günter M. T1 - Gröbner bases of lattices, corner polyhedra, and integer programming N2 - We investigate the generating sets (``Gröbner bases'') of integer lattices which correspond to the Gröbner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gröbner basis in terms of the vertices and edges of the associated corner polyhedra. We emphasize the special case where the lattice has finite index. In this case the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming'' Schrijver, p.~363. We present exponential lower and upper bounds for the size of a reduced Gröbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron. T3 - ZIB-Report - SC-94-26 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1548 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 - Pochet, Yves A1 - Weismantel, Robert T1 - The Sequential Knapsack Polytope N2 - In this paper we describe the convex hull of all solutions of the integer bounded knapsack problem in the special case when the weights of the items are divisible. The corresponding inequalities are defined via an inductive scheme that can also be used in a more general setting. T3 - ZIB-Report - SC-94-30 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1588 ER - 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 - Thomas, Rekha R. A1 - Weismantel, Robert T1 - Truncated Gröbner Bases for Integer Programming N2 - {\def\N{{\mbox{{\rm I\kern-0.22emN}}}}In this paper we introduce a multivariate grading of the toric ideal associated with the integer program $min \{ cx : Ax = b, x \in \N^n \}$, and a truncated Buchberger algorithm to solve the program. In the case of $max \{ cx : Ax \leq b, x \leq u, x \in \N^n \}$ in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in UWZ94}. T3 - ZIB-Report - SC-95-09 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1750 ER - TY - GEN A1 - Thomas, Rekha R. A1 - Weismantel, Robert T1 - Test sets and inequalities for integer programs: extended abstract N2 - This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix $A$ transforms to the state polytope as we pass from linear programs that have $A$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs. T3 - ZIB-Report - SC-95-36 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2021 ER - TY - GEN A1 - Helmberg, Christoph A1 - Rendl, Franz A1 - Weismantel, Robert T1 - Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract 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-95-37 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2031 ER - TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - Hilbert bases of cones related to simultaneous Diophantine approximations and linear Diophantine equations N2 - This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem. T3 - ZIB-Report - SC-97-29 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2989 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Set Packing Relaxations of Some Integer Programs N2 - This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation. T3 - ZIB-Report - SC-97-30 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2998 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 - Henk, Martin A1 - Weismantel, Robert T1 - On Hilbert bases of polyhedral cones N2 - For a polyhedral cone $C=$ pos $\{a^1,\dots,a^m\}\subset R^d$, $a^i\in Z^d$, a subset of integral vectors $H(C)\subset C \cap Z^d$ is called a Hilbert basis of $C$ iff (i) each element of $C\cap Z^d$ can be written as a non-negative integer combination of elements of $H(C)$ and (ii) $H(C)$ has minimal cardinality with respect to all subsets of $C \cap Z^d$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates. T3 - ZIB-Report - SC-96-12 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2230 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 - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Intersection of Knapsack Polyhedra and Extensions N2 - This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported. T3 - ZIB-Report - SC-97-61 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3300 ER - TY - THES A1 - Weismantel, Robert T1 - Plazieren von Zellen: Theorie und Lösung eines quadratischen 0/1- Optimierungsproblems. N2 - Die vorliegende Arbeit beschäftigt sich mit dem Plazierungsproblem, welches beim Entwurf elektronischer Schaltungen auftritt. Das Plazierungsproblem modellieren wir als ein quadratisches 0/1 Optimierungsproblem unter linearen Nebenbedingungen und untersuchen das Modell komplexitätstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die Lösung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur Lösung dieser Beispiele wurde ein Prototyp implementiert und mit state of the art"-Plazierungsverfahren verglichen. Schlie\ss lich werden wir uns mit dem Clusteringproblem, das eine Variante des Mehrfachschnitt-Problems darstellt, beschäftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gelöst werden können und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden. T3 - ZIB-Report - TR-92-03 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4883 ER - TY - CHAP A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert ED - Rinaldi, Giovanni ED - Wolsey, Laurence T1 - Routing in grid graphs by cutting planes T2 - Integer Programming and Combinatorial Optimization. Proceedings of a Conference held at Centro Ettore Majorana, Erice, Italy, April 29 - May 1, 1993 Y1 - 1993 SP - 447 EP - 461 PB - Librarian CORE CY - Louvain-la-Neuve ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Steiner tree packing problem in VLSI design JF - Mathematical Programming Y1 - 1997 VL - 78 IS - 2 SP - 265 EP - 281 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Routing in Grid Graphs by Cutting Planes JF - ZOR - Mathematical Methods of Operations Research Y1 - 1995 VL - 41 IS - 3 SP - 255 EP - 275 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Further Facets JF - European Journal of Combinatorics Y1 - 1996 U6 - https://doi.org/10.1006/eujc.1996.0004 VL - 17 IS - 1 SP - 39 EP - 52 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Separation Algorithms JF - SIAM Journal on Discrete Mathematics Y1 - 1996 U6 - https://doi.org/10.1137/S0895480193258716 VL - 9 IS - 2 SP - 233 EP - 257 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels JF - Computers and Mathematics with Applications Y1 - 1996 VL - 31 IS - 11 SP - 23 EP - 35 PB - Elsevier ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner trees: Polyhedral Investigations JF - Mathematical Programming, Series A Y1 - 1996 U6 - https://doi.org/10.1007/BF02592085 VL - 72 IS - 2 SP - 101 EP - 123 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner trees: a cutting plane algorithm and computational results JF - Mathematical Programming, Series A Y1 - 1996 U6 - https://doi.org/10.1007/BF02592086 VL - 72 IS - 2 SP - 125 EP - 145 ER - TY - JOUR A1 - Ferreira, Carlos A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert A1 - Kiefl, Stefan A1 - Krispenz, Ludwig T1 - Some Integer Programs Arising in the Design of Main Frame Computers JF - ZOR - Methods and Models of Operations Research Y1 - 1993 VL - 38 IS - 1 SP - 77 EP - 100 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Set Packing Relaxations of Some Integer Programs JF - Math. Programming Y1 - 2000 UR - http://opus.kobv.de/zib/volltexte/1997/300/ VL - 88 SP - 425 EP - 450 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs JF - Discrete Appl. Math. Y1 - 2001 UR - http://opus.kobv.de/zib/volltexte/1997/324/ VL - 112 IS - 1–3 SP - 11 EP - 26 ER - TY - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cub JF - SIAM Journal on Optimization Y1 - 2022 ER - TY - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cube JF - SIAM Journal on Optimization Y1 - 2022 ER -