@misc{JuengerMartinReineltetal., author = {J{\"u}nger, Michael and Martin, Alexander and Reinelt, Gerhard and Weismantel, Robert}, title = {Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-803}, number = {SC-92-10}, abstract = {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.}, language = {en} } @misc{KochMartin, author = {Koch, Thorsten and Martin, Alexander}, title = {Solving Steiner Tree Problems in Graphs to Optimality}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2526}, number = {SC-96-42}, abstract = {In this paper we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms and primal heuristics. We are able to solve all problem instances discussed in literature to optimality, including one to our knowledge not yet solved problem. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called {\em SteinLib} that is accessible via World Wide Web.}, language = {en} } @misc{KochMartinVoss, author = {Koch, Thorsten and Martin, Alexander and Voß, Stefan}, title = {SteinLib: An Updated Library on Steiner Tree Problems in Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6056}, number = {00-37}, abstract = {In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances.}, language = {en} } @misc{MarchandMartinWeismanteletal., 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}, 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{MartinWeismantel, 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}, 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{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{PfetschFuegenschuhGeissleretal., author = {Pfetsch, Marc and F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Vigerske, Stefan and Willert, Bernhard}, title = {Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions}, issn = {1438-0064}, doi = {10.1080/10556788.2014.888426}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16531}, abstract = {In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.}, 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} }