@misc{GroetschelMartinWeismantel1993, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels: The Noncrossing Case.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1225}, number = {SC-93-26}, year = {1993}, abstract = {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.}, language = {en} } @misc{FerreiraMartinSouzaetal.1994, author = {Ferreira, Carlos E. and Martin, Alexander and Souza, Cid C. de and Weismantel, Robert and Wolsey, Laurence}, title = {Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1450}, number = {SC-94-16}, year = {1994}, abstract = {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.}, language = {en} } @misc{FerreiraMartinSouzaetal.1994, author = {Ferreira, Carlos E. and Martin, Alexander and Souza, Cid C. de and Weismantel, Robert and Wolsey, Laurence}, title = {The Node Capacitated Graph Partitioning Problem: A Computational Study.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1469}, number = {SC-94-17}, year = {1994}, abstract = {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.}, language = {en} } @misc{Weismantel1994, author = {Weismantel, Robert}, title = {Hilbert Bases and the Facets of Special Knapsack Polytopes.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1475}, number = {SC-94-19}, year = {1994}, abstract = {{\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.}}, language = {en} } @misc{SchulzWeismantelZiegler1995, author = {Schulz, Andreas S. and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {0/1-Integer Programming: Optimization and Augmentation are Equivalent}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1744}, number = {SC-95-08}, year = {1995}, abstract = {{\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.}}, language = {en} } @misc{ThomasWeismantel1995, author = {Thomas, Rekha R. and Weismantel, Robert}, title = {Truncated Gr{\"o}bner Bases for Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1750}, number = {SC-95-09}, year = {1995}, abstract = {{\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}.}, language = {en} } @misc{SturmfelsWeismantelZiegler1994, author = {Sturmfels, Bernd and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {Gr{\"o}bner bases of lattices, corner polyhedra, and integer programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1548}, number = {SC-94-26}, year = {1994}, abstract = {We investigate the generating sets (``Gr{\"o}bner bases'') of integer lattices which correspond to the Gr{\"o}bner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gr{\"o}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{\"o}bner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.}, language = {en} } @misc{UrbaniakWeismantelZiegler1994, author = {Urbaniak, Regina and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {A New Variant of Buchberger's Algorithm for Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1570}, number = {SC-94-29}, year = {1994}, abstract = {In this paper we modify Buchberger's \$S\$-pair reduction algorithm for computing a Gr{\"o}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.}, language = {en} } @misc{PochetWeismantel1994, author = {Pochet, Yves and Weismantel, Robert}, title = {The Sequential Knapsack Polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1588}, number = {SC-94-30}, year = {1994}, abstract = {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.}, language = {en} } @misc{WeismantelFerreiraMartin1993, author = {Weismantel, Robert and Ferreira, Carlos E. and Martin, Alexander}, title = {A Cutting Plane Based Algorithm for the Multiple Knapsack Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1031}, number = {SC-93-07}, year = {1993}, abstract = {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.}, language = {en} } @misc{GroetschelMartinWeismantel1992, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Polyhedral Investigations.}, doi = {10.1007/BF02592085}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-786}, number = {SC-92-08}, year = {1992}, abstract = {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.}, language = {en} }