@misc{FerreiraMartinWeismantel1993, author = {Ferreira, Carlos E. and Martin, Alexander and Weismantel, Robert}, title = {Facets for the Multiple Knapsack Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1007}, number = {SC-93-04}, year = {1993}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1998, author = {Martin, Alexander and Weismantel, Robert}, title = {Conjunctive Cuts for Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3618}, number = {SC-98-18}, year = {1998}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1997, author = {Martin, Alexander and Weismantel, Robert}, title = {Contributions to General Mixed Integer Knapsack Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3075}, number = {SC-97-38}, year = {1997}, abstract = {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.}, language = {en} } @misc{BrunsGubeladzeHenketal.1998, author = {Bruns, Winfried and Gubeladze, Joseph and Henk, Martin and Martin, Alexander and Weismantel, Robert}, title = {A counterexample to an integer analogue of Caratheodorys theorem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3718}, number = {SC-98-28}, year = {1998}, abstract = {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.}, language = {en} } @phdthesis{Weismantel1992, author = {Weismantel, Robert}, title = {Plazieren von Zellen: Theorie und L{\"o}sung eines quadratischen 0/1- Optimierungsproblems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4883}, number = {TR-92-03}, year = {1992}, abstract = {Die vorliegende Arbeit besch{\"a}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{\"a}tstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die L{\"o}sung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur L{\"o}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{\"a}ftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gel{\"o}st werden k{\"o}nnen und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden.}, language = {de} } @misc{MarchandMartinWeismanteletal.1999, author = {Marchand, Hugues and Martin, Alexander and Weismantel, Robert and Wolsey, Laurence}, title = {Cutting Planes in Integer and Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4339}, number = {SC-99-44}, year = {1999}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1997, author = {Martin, Alexander and Weismantel, Robert}, title = {The Intersection of Knapsack Polyhedra and Extensions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3300}, number = {SC-97-61}, year = {1997}, abstract = {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.}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cub}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cube}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner trees: Polyhedral Investigations}, volume = {72}, journal = {Mathematical Programming, Series A}, number = {2}, doi = {10.1007/BF02592085}, pages = {101 -- 123}, year = {1996}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels}, volume = {31}, journal = {Computers and Mathematics with Applications}, number = {11}, publisher = {Elsevier}, pages = {23 -- 35}, year = {1996}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner trees: a cutting plane algorithm and computational results}, volume = {72}, journal = {Mathematical Programming, Series A}, number = {2}, doi = {10.1007/BF02592086}, pages = {125 -- 145}, year = {1996}, language = {en} } @article{GroetschelMartinWeismantel1997, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {The Steiner tree packing problem in VLSI design}, volume = {78}, journal = {Mathematical Programming}, number = {2}, pages = {265 -- 281}, year = {1997}, language = {en} } @inproceedings{GroetschelMartinWeismantel1993, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Routing in grid graphs by cutting planes}, booktitle = {Integer Programming and Combinatorial Optimization. Proceedings of a Conference held at Centro Ettore Majorana, Erice, Italy, April 29 - May 1, 1993}, editor = {Rinaldi, Giovanni and Wolsey, Laurence}, publisher = {Librarian CORE}, address = {Louvain-la-Neuve}, pages = {447 -- 461}, year = {1993}, language = {en} } @article{BorndoerferWeismantel2000, author = {Bornd{\"o}rfer, Ralf and Weismantel, Robert}, title = {Set Packing Relaxations of Some Integer Programs}, volume = {88}, journal = {Math. Programming}, pages = {425 -- 450}, year = {2000}, language = {en} } @article{BorndoerferWeismantel2001, author = {Bornd{\"o}rfer, Ralf and Weismantel, Robert}, title = {Discrete Relaxations of Combinatorial Programs}, volume = {112}, journal = {Discrete Appl. Math.}, number = {1-3}, pages = {11 -- 26}, year = {2001}, language = {en} } @article{FerreiraGroetschelMartinetal.1993, author = {Ferreira, Carlos and Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert and Kiefl, Stefan and Krispenz, Ludwig}, title = {Some Integer Programs Arising in the Design of Main Frame Computers}, volume = {38}, journal = {ZOR - Methods and Models of Operations Research}, number = {1}, pages = {77 -- 100}, year = {1993}, language = {en} } @article{GroetschelMartinWeismantel1995, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Routing in Grid Graphs by Cutting Planes}, volume = {41}, journal = {ZOR - Mathematical Methods of Operations Research}, number = {3}, pages = {255 -- 275}, year = {1995}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Separation Algorithms}, volume = {9}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, doi = {10.1137/S0895480193258716}, pages = {233 -- 257}, year = {1996}, language = {en} } @article{GroetschelMartinWeismantel1996, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiner Trees: Further Facets}, volume = {17}, journal = {European Journal of Combinatorics}, number = {1}, doi = {10.1006/eujc.1996.0004}, pages = {39 -- 52}, year = {1996}, language = {en} } @misc{BorndoerferWeismantel1997, author = {Bornd{\"o}rfer, Ralf and Weismantel, Robert}, title = {Set Packing Relaxations of Some Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2998}, number = {SC-97-30}, year = {1997}, abstract = {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.}, language = {en} } @misc{BorndoerferWeismantel1997, author = {Bornd{\"o}rfer, Ralf and Weismantel, Robert}, title = {Discrete Relaxations of Combinatorial Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3230}, number = {SC-97-54}, year = {1997}, abstract = {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.}, language = {en} }