TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian A1 - Kutschka, Manuel T1 - Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts N2 - 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. T3 - ZIB-Report - 07-10 KW - {0 KW - 1/2}-Chvatal-Gomory cuts KW - separation algorithms KW - integer programming Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9531 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Koster, Arie M.C.A. A1 - Raack, Christian A1 - Wessäly, Roland T1 - Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics N2 - 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. T3 - ZIB-Report - 06-47 KW - multi-layer network design KW - integer programming KW - branch-and-cut KW - heuristics Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9412 ER - TY - GEN A1 - Kaibel, Volker A1 - Pfetsch, Marc T1 - Packing and Partitioning Orbitopes N2 - 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. T3 - ZIB-Report - 06-17 KW - integer programming KW - symmetry breaking KW - lexicographic representatives Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9104 ER - TY - GEN A1 - Koster, Arie M.C.A. T1 - Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring N2 - 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. T3 - ZIB-Report - 05-13 KW - wavelength assignment KW - optical networks KW - graph theory KW - combinatorial optimization KW - integer programming Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8478 ER - TY - GEN A1 - Helmberg, Christoph A1 - Röhl, Stefan T1 - A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses N2 - 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. T3 - ZIB-Report - 05-11 KW - convex relaxation KW - integer programming KW - stochastic demand KW - network models KW - large scale problems KW - bundle method KW - logistics KW - vehicle routing Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8454 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - An Integer Programming Model for Multi-Layer Network Design N2 - 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. T3 - ZIB-Report - 04-49 KW - multi-layer networks KW - integer programming KW - network design KW - routing KW - grooming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8248 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Provably Good Solutions for Wavelength Assignment in Optical Networks N2 - 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. T3 - ZIB-Report - 04-40 KW - wavelength assignment KW - integer programming KW - column generation Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8155 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks N2 - 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. T3 - ZIB-Report - 04-41 KW - optical networks KW - wavelength assignment KW - integer programming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8160 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Koster, Arie M.C.A. A1 - Wallbaum, Randolf A1 - Wessäly, Roland T1 - Load Balancing in Signaling Transfer Points N2 - 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. T3 - ZIB-Report - 02-50 KW - Signaling network KW - STP KW - load-balancing KW - integer programming KW - computations Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7179 ER - TY - GEN A1 - Zymolka, Adrian A1 - Koster, Arie M.C.A. A1 - Wessäly, Roland T1 - Transparent optical network design with sparse wavelength conversion N2 - 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. T3 - ZIB-Report - 02-34 KW - optical network design KW - wavelength conversion KW - integer programming Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7017 ER - TY - GEN A1 - Grötschel, Martin T1 - Frequency Assignment in Mobile Phone Systems N2 - 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. T3 - ZIB-Report - 00-58 KW - frequency assignment KW - telecommunication KW - mobile phone KW - integer programming KW - coloring Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6265 ER - TY - GEN A1 - Grötschel, Martin T1 - My Favorite Theorem: Characterizations of Perfect Graphs N2 - This paper summarizes and discusses various characterizations of perfect graphs and mentions some open problems in this area. T3 - ZIB-Report - SC-99-17 KW - graph theory KW - perfect graphs KW - integer programming Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4053 ER - TY - THES A1 - Martin, Alexander T1 - Integer Programs with Block Structure N2 - 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. T3 - ZIB-Report - SC-99-03 KW - integer programming KW - cutting planes KW - block structure Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3911 ER -