TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Polyhedral Investigations on Stable Multi-Sets N2 - Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in [{\sl Koster and Zymolka 2002}] and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results. First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords. The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities. T3 - ZIB-Report - 03-10 KW - stable multi-sets KW - polyhedral combinatorics Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7324 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian A1 - Jäger, Monika A1 - Hülsermann, Ralf A1 - Gerlach, Christoph T1 - Demand-wise Shared Protection for Meshed Optical Networks N2 - In this paper, a new shared protection mechanism for meshed optical networks is presented. Significant network design cost reductions can be achieved in comparison to the well-known 1+1 protection scheme. Demand-wise Shared Protection (DSP) bases on the diversification of demand routings and exploits the network connectivity to restrict the number of backup lightpaths needed to provide the desired level of prorection. Computational experiments approve the benefits of the concept DSP for cost efficient optical network designs. T3 - ZIB-Report - 03-24 KW - optical network design KW - shared protection KW - meshed optical networks KW - diversification Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7461 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Minimum Converter Wavelength Assignment in All-Optical Networks N2 - Finding conflict-free wavelength assignments with a minimum number of required conversions for a routing of the lightpaths is one of the important tasks within the design of all-optical networks. We consider this problem in multi-fiber networks with different types of WDM systems. We give a detailed description of the problem and derive its theoretical complexity. For practical application, we propose several sequential algorithms to compute appropriate wavelength assignments. We also perform computational experiments to evaluate their performance. For the iterative algorithms, we identify characteristic patterns of progression. Two of these algorithms qualify for application in practice. T3 - ZIB-Report - 03-45 KW - minimum converter wavelength assignment KW - optical networks KW - generalized coloring KW - complexity KW - heuristics Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7673 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wagler, Annegret T1 - The extreme points of QSTAB(G) and its implications N2 - Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs $G$ where the stable set polytope STAB$(G)$ coincides with the clique constraint stable set polytope QSTAB$(G)$. For all imperfect graphs STAB$(G) \subset$ QSTAB$(G)$ holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB$(G)$ and QSTAB$(G)$. Several concepts have been developed in this direction, for instance the dilation ratio of STAB$(G)$ and QSTAB$(G)$ which is equivalent to the imperfection ratio imp$(G)$ of $G$. To determine imp$(G)$, both knowledge on the facets of STAB$(G)$ and the extreme points of QSTAB$(G)$ is required. The anti-blocking theory of polyhedra yields all {\em dominating} extreme points of QSTAB$(G)$, provided a complete description of the facets of STAB$(\overline G)$ is known. As this is typically not the case, we extend the result on anti-blocking polyhedra to a {\em complete} characterization of the extreme points of QSTAB$(G)$ by establishing a 1-1 correspondence to the facet-defining subgraphs of $\overline G$. We discuss several consequences, in particular, we give alternative proofs of several famous results. T3 - ZIB-Report - 06-30 KW - perfect graphs KW - imperfection ratio KW - stable set polytope Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9249 ER - TY - GEN A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Wessäly, Roland T1 - On the strength of cut-based inequalities for capacitated network design polyhedra N2 - In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR). T3 - ZIB-Report - 07-08 KW - cutset-polyhedra KW - flow-cutset inequalities KW - network design KW - mixed integer programming Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9512 ER - 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 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Capacitated network design using general flow-cutset inequalities N2 - This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities. T3 - ZIB-Report - 07-14 KW - general flow-cutset inequalities KW - capacitated network design KW - mixed integer rounding KW - SNDlib Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9576 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 - Hülsermann, Ralf A1 - Jäger, Monika A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - Availability and Cost Based Evaluation of Demand-wise Shared Protection N2 - In this paper, we investigate the connection availabilities for the new protection scheme Demand-wise Shared Protection (DSP) and describe an appropriate approach for their computation. The exemplary case study on two realistic network scenarios shows that in most cases the availabilities for DSP are comparable with that for 1+1 path protection and better than in case of shared path protection. T3 - ZIB-Report - 06-15 KW - demand-wise shared protection KW - network availability KW - network optimization Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9080 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wagler, Annegret T1 - Comparing Imperfection Ratio and Imperfection Index for Graph Classes N2 - Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of $STAB( G)$, the disjunctive index of $QSTAB(G)$, and the dilation ratio of the two polytopes. Including only certain types of facets for $STAB(G)$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of $STAB(G)$ and $QSTAB(G)$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of $Q STAB(G)$ as the imperfection index of $G$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements. T3 - ZIB-Report - 05-50 KW - perfect graphs KW - imperfection ratio KW - imperfection index Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8836 ER - TY - GEN A1 - Bodlaender, Hans L. A1 - Grigoriev, Alexander A1 - Koster, Arie M.C.A. T1 - Treewidth Lower Bounds with Brambles N2 - In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph $G$ is the maximum order of a bramble of $G$ minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms give often excellent lower bounds, in particular when applied to (close to) planar graphs. T3 - ZIB-Report - 05-54 KW - treewidth KW - lower bounds KW - branchwidth KW - brambles Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8878 ER - TY - GEN A1 - Gruber, Claus G. A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - A new model and a computational study for Demand-wise Shared Protection N2 - This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15\% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15\% percent worse than shared path protection. T3 - ZIB-Report - 05-55 KW - demand-wise shared protection KW - resilience KW - network design KW - integer linear programming Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8880 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Stable Multi-Sets N2 - In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks. T3 - ZIB-Report - 00-36 KW - stable multi-sets KW - polyhedral combinatorics Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6047 ER - TY - GEN A1 - Koster, Arie M.C.A. T1 - Re-Optimization of Signaling Transfer Points N2 - In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits. T3 - ZIB-Report - 00-18 KW - Telecommunications KW - Modeling KW - Integer Programming Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5863 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Bayer, Georg A1 - Engel, Thomas T1 - Single-layer Cuts for Multi-layer Network Design Problems N2 - We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context, helping to increase the dual bound and to reduce the optimality gaps. T3 - ZIB-Report - 07-21 KW - telecommunication network KW - multi-layer network design KW - mixed-integer programming KW - cutting planes Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9641 SN - 1438-0064 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Raack, Christian T1 - Robust Network Design: Formulations, Valid Inequalities, and Computations N2 - Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim [2004]. We present three different mathematical formulations for this problem, provide valid inequalities, study the computational implications, and evaluate the realized robustness. To enhance the performance of the mixed-integer programming solver we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. We show that these inequalities define facets under certain conditions and that they completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge. For realistic networks and live traffic measurements we compare the formulations and report on the speed up by the valid inequalities. We study the "price of robustness" and evaluate the approach by analyzing the real network load. The results show that the robust optimization approach has the potential to support network planners better than present methods. T3 - ZIB-Report - 11-34 KW - robust network design KW - cutset inequalities Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13890 SN - 1438-0064 ER - TY - GEN A1 - Bauschert, Thomas A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Steglich, Uwe T1 - Network Planning under Demand Uncertainty with Robust Optimization N2 - The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties. T3 - ZIB-Report - 13-59 KW - Network Design, Demand Uncertainty, Robust Optimization, Telecommunications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42557 SN - 1438-0064 ER -