@misc{KosterZymolkaKutschka2007, author = {Koster, Arie M.C.A. and Zymolka, Adrian and Kutschka, Manuel}, title = {Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9531}, number = {07-10}, year = {2007}, abstract = {Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or \$\frac{1}{2}\$, such cuts are known as \$\{0,\frac{1}{2}\}\$-cuts. It has been proven by Caprara and Fischetti (1996) that separation of \$\{0,\frac{1}{2}\}\$-cuts is NP-hard. In this paper, we study ways to separate \$\{0,\frac{1}{2}\}\$-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated \$\{0,\frac{1}{2}\}\$-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.}, language = {en} } @misc{OrlowskiKosterRaacketal.2006, author = {Orlowski, Sebastian and Koster, Arie M.C.A. and Raack, Christian and Wess{\"a}ly, Roland}, title = {Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9412}, number = {06-47}, year = {2006}, abstract = {This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.}, language = {en} } @misc{KaibelPfetsch2006, author = {Kaibel, Volker and Pfetsch, Marc}, title = {Packing and Partitioning Orbitopes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9104}, number = {06-17}, year = {2006}, abstract = {We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case, both the description and the proof are more involved. The associated separation problems can be solved in linear time.}, language = {en} } @misc{Koster2005, author = {Koster, Arie M.C.A.}, title = {Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8478}, number = {05-13}, year = {2005}, abstract = {In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies. We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links. A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality.}, language = {en} } @misc{HelmbergRoehl2005, author = {Helmberg, Christoph and R{\"o}hl, Stefan}, title = {A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8454}, number = {05-11}, year = {2005}, abstract = {For a real world problem --- transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand --- we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation. For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application. In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream.}, language = {en} } @misc{OrlowskiWessaely2004, author = {Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {An Integer Programming Model for Multi-Layer Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8248}, number = {04-49}, year = {2004}, abstract = {We present an integer linear programming model for the design of multi-layer telecommunication networks. The formulation integrates hardware, capacity, routing, and grooming decisions in \emph{any} n umber of network layers. Practical hardware restrictions and cost can accurately be taken into account for technologies based on connection-oriented routing protocols.}, language = {en} } @misc{KosterZymolka2004, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Provably Good Solutions for Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8155}, number = {04-40}, year = {2004}, abstract = {In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically.}, language = {en} } @misc{KosterZymolka2004, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8160}, number = {04-41}, year = {2004}, abstract = {In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.}, language = {en} } @misc{EisenblaetterKosterWallbaumetal.2002, author = {Eisenbl{\"a}tter, Andreas and Koster, Arie M.C.A. and Wallbaum, Randolf and Wess{\"a}ly, Roland}, title = {Load Balancing in Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7179}, number = {02-50}, year = {2002}, abstract = {Signaling is crucial to the operation of modern telecommunication networks. A breakdown in the signaling infrastructure typically causes customer service failures, incurs revenue losses, and hampers the company image. Therefore, the signaling network has to be highest reliability and survivability. This in particular holds for the routers in such a network, called \textit{signaling transfer points\/} (STPs). The robustness of an STP can be improved by equally distributing the load over the internal processing units. Several constraints have to be taken into account. The load of the links connected to a processing unit changes over time introducing an imbalance of the load. In this paper, we show how integer linear programming can be applied to reduce the imbalance within an STP, while keeping the number of changes small. Two alternative models are presented. Computational experiments validate the integer programming approach in practice. The GSM network operator E-Plus saves substantial amounts of time and money by employing the proposed approach.}, language = {en} } @misc{ZymolkaKosterWessaely2002, author = {Zymolka, Adrian and Koster, Arie M.C.A. and Wess{\"a}ly, Roland}, title = {Transparent optical network design with sparse wavelength conversion}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7017}, number = {02-34}, year = {2002}, abstract = {We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse wavelength conversion for efficient use of the capacities. In this paper, we investigate this extensive optical network design task. Using a flexible device-based model, we present an integer programming formulation that supports greenfield planning as well as expansion planning on top of an existing network. As solution method, we propose a suitable decomposition approach that separates the wavelength assignment from the dimensioning and routing. Our method in particular provides a lower bound on the total cost which allows to rate the solution quality. Computational experiments on realistic networks approve the solution approach to be appropriate.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Frequency Assignment in Mobile Phone Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6265}, number = {00-58}, year = {2001}, abstract = {Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.}, language = {en} } @misc{Groetschel1999, author = {Gr{\"o}tschel, Martin}, title = {My Favorite Theorem: Characterizations of Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4053}, number = {SC-99-17}, year = {1999}, abstract = {This paper summarizes and discusses various characterizations of perfect graphs and mentions some open problems in this area.}, language = {en} } @phdthesis{Martin1999, author = {Martin, Alexander}, title = {Integer Programs with Block Structure}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3911}, number = {SC-99-03}, year = {1999}, abstract = {In this thesis we study and solve integer programs with block structure, i.\,e., problems that after the removal of certain rows (or columns) of the constraint matrix decompose into independent subproblems. The matrices associated with each subproblem are called blocks and the rows (columns) to be removed linking constraints (columns). Integer programs with block structure come up in a natural way in many real-world applications. The methods that are widely used to tackle integer programs with block structure are decomposition methods. The idea is to decouple the linking constraints (variables) from the problem and treat them at a superordinate level, often called master problem. The resulting residual subordinate problem then decomposes into independent subproblems that often can be solved more efficiently. Decomposition methods now work alternately on the master and subordinate problem and iteratively exchange information to solve the original problem to optimality. In Part I we follow a different approach. We treat the integer programming problem as a whole and keep the linking constraints in the formulation. We consider the associated polyhedra and investigate the polyhedral consequences of the involved linking constraints. The variety and complexity of the new inequalities that come into play is illustrated on three different types of real-world problems. The applications arise in the design of electronic circuits, in telecommunication and production planning. We develop a branch-and-cut algorithm for each of these problems, and our computational results show the benefits and limits of the polyhedral approach to solve these real-world models with block structure. Part II of the thesis deals with general mixed integer programming problems, that is integer programs with no apparent structure in the constraint matrix. We will discuss in Chapter 5 the main ingredients of an LP based branch-and-bound algorithm for the solution of general integer programs. Chapter 6 then asks the question whether general integer programs decompose into certain block structures and investigate whether it is possible to recognize such a structure. The remaining two chapters exploit information about the block structure of an integer program. In Chapter 7 we parallelize parts of the dual simplex algorithm, the method that is commonly used for the solution of the underlying linear programs within a branch-and-cut algorithm. In Chapter 8 we try to detect small blocks in the constraint matrix and to derive new cutting planes that strengthen the integer programming formulation. These inequalities may be associated with the intersection of several knapsack problems. We will see that they significantly improve the quality of the general integer programming solver introduced in Chapter 5.}, language = {en} }