@misc{MartinWeismantel, 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}, 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{MartinWeismantel, author = {Martin, Alexander and Weismantel, Robert}, title = {Packing Paths and Steiner Trees: Routing of Electronic Circuits.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1113}, number = {SC-93-15}, abstract = {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.}, language = {en} } @misc{MartinWeismantel, 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}, 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} } @misc{WeismantelFerreiraMartin, 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}, 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} }