@misc{BorndoerferEisenblaetterGroetscheletal., author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, abstract = {Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.}, language = {en} } @misc{EisenblaetterFuegenschuhKochetal., author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Koch, Thorsten and Koster, Arie M.C.A. and Martin, Alexander and Pfender, Tobias and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Modelling Feasible Network Configurations for UMTS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6837}, number = {02-16}, abstract = {A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations.}, language = {en} } @misc{AchterbergKochMartin, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {Branching on History Information}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6990}, number = {02-32}, abstract = {Mixed integer programs (\$MIPs\$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in \$SIP\$, a state-of-the-art \$MIP\$ solver. We give computational results that show the superiority of the new strategy.}, language = {en} } @misc{AchterbergKochMartin, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {Branching rules revisited}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7886}, number = {04-13}, abstract = {Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost branching} strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed newstrategy.}, language = {en} } @misc{EisenblaetterGeerdesKochetal., author = {Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Koch, Thorsten and Martin, Alexander and Wess{\"a}ly, Roland}, title = {UMTS Radio Network Evaluation and Optimization beyond Snapshots}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7903}, number = {04-15}, abstract = {This paper is concerned with UMTS radio network design. Our task is to reconfigure antennas and the related cells as to improve network quality. In contrast to second generation GSM networks, \emph{interference} plays a paramount role when designing third generation radio networks. A known compact formulation for assessing the interference characteristics of a radio network as coupling relations between cells based on user snapshots is generalized to statistical average load. This enables us to overcome the notorious difficulties of snapshot-based network optimization approaches. We recall a mixed-integer programming model for the network design problem that is based on user snapshots and contrast it with a new network design model based on the average coupling formulation. Exemplarily focusing on the important problem of optimizing antenna tilts, we give computational results for a fast local search algorithm and the application of a MIP solver to both models. These results demonstrate that our new average-based approaches outperform state-of-the-art snapshot models for UMTS radio network optimization.}, language = {en} } @misc{EisenblaetterFuegenschuhGeerdesetal., author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Geerdes, Hans-Florian and Junglas, Daniel and Koch, Thorsten and Martin, Alexander}, title = {Optimization Methods for UMTS Radio Network Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7637}, number = {03-41}, abstract = {The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.}, language = {en} } @misc{AchterbergKochMartin, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {MIPLIB 2003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8625}, number = {05-28}, abstract = {This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances.}, language = {en} } @misc{BixbyMartin, author = {Bixby, Robert E. and Martin, Alexander}, title = {Parallelizing the Dual Simplex Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2112}, number = {SC-95-45}, abstract = {We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one general-purpose System V shared-memory constructs, and one the PowerC extension of C on a Silicon Graphics multi-processor. These versions were tested on different parallel platforms, including heterogeneous workstation clusters, Sun S20-502, Silicon Graphics multi-processors, and an IBM SP2. We report on our computational experience.}, language = {en} } @misc{BorndoerferFerreiraMartin, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Matrix Decomposition by Branch-and-Cut}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2839}, number = {SC-97-14}, abstract = {In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix \$A\$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the \%LP- and MIP-libraries \Netlib{} and MIPLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem.}, language = {en} } @misc{BorndoerferFerreiraMartin, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Decomposing Matrices into Blocks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2849}, number = {SC-97-15}, abstract = {In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix \$A\$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.}, language = {en} } @misc{GroetschelMartinWeismantel, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels: The Consecutive Case}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1976}, number = {SC-95-31}, abstract = {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.}, 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{BorndoerferEisenblaetterGroetscheletal., author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {Frequency Assignment in Cellular Phone Networks}, doi = {10.1023/A:1018908907763}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3044}, number = {SC-97-35}, abstract = {We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice.}, 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{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{BrunsGubeladzeHenketal., 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}, 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} } @misc{GroetschelMartinWeismantel, 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}, 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} } @misc{GroetschelMartinWeismantel, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-792}, number = {SC-92-09}, abstract = {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.}, language = {en} } @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{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} }