TY - GEN A1 - Wagler, Annegret T1 - Antiwebs are Rank-Perfect N2 - \We discuss a nested collection of three superclasses of perfect graphs: near-perfect, rank-perfect, and weakly rank-perfect graphs. For that, we start with the description of the stable set polytope for perfect graphs and allow stepwise more general facets for the stable set polytopes of the graphs in each superclass. Membership in those three classes indicates how far a graph is away from being perfect. We investigate for webs and antiwebs to which of the three classes they belong. We provide a complete description of the facets of the stable set polytope for antiwebs (with help of a result due to Shepherd on near-bipartite graphs). The main result is that antiwebs are rankperfect. T3 - ZIB-Report - 02-07 KW - relaxations of perfect graphs KW - antiwebs KW - stable set polytope Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6742 ER - TY - GEN A1 - Grötschel, Martin A1 - Henk, Martin T1 - On the Representation of Polyhedra by Polynomial Inequalities N2 - A beautiful result of Bröcker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every $d$-dimensional polyhedron admits a representation as the set of solutions of at most $d(d+1)/2$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number $d(d+1)/2$. T3 - ZIB-Report - 02-15 KW - polyhedra and polytopes KW - semialgebraic sets KW - polyhedral combinatorics KW - polynomial inequalities Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6826 ER - TY - GEN A1 - Grötschel, Martin T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes N2 - A subset ${\cal C}$ of the power set of a finite set $E$ is called cardinality homogeneous if, whenever ${\cal C}$ contains some set $F$, ${\cal C}$ contains all subsets of $E$ of cardinality $|F|$. Examples of such set systems ${\cal C}$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of $E$. With each cardinality homogeneous set system ${\cal C}$, we associate the polytope $P({\cal C})$, the convex hull of the incidence vectors of all sets in ${\cal C}$, and provide a complete and nonredundant linear description of $P({\cal C})$. We show that a greedy algorithm optimizes any linear function over $P({\cal C})$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type $P({\cal C})$. T3 - ZIB-Report - 02-19 KW - Cycles in Matroids KW - cardinality homogeneous set systems KW - polytopes KW - greedy algorithm KW - polyhedral combinatorics Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6868 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 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial Inequalities Representing Polyhedra N2 - Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities. T3 - ZIB-Report - 04-53 KW - polyhedra and polytopes KW - semi-algebraic sets KW - polyhedral combinatorics KW - polynomial inequalities KW - stability index Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8284 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Comparing Restoration Concepts using Optimal Network Configurations with Integrated Hardware and Routing Decisions N2 - We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results. T3 - ZIB-Report - 03-09 KW - survivable network design KW - link and path restoration KW - hardware configuration KW - branch-and-cut algorithm KW - routing Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7316 ER - 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 - Pecher, Arnaud A1 - Wagler, Annegret T1 - On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four N2 - Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only while there are examples with clique number $>4$ having non-rank facets. T3 - ZIB-Report - 03-01 KW - web KW - rank-perfect graph KW - stable set polytope KW - (non-)rank facet Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7238 ER - TY - GEN A1 - Pêcher, Arnaud A1 - Wagler, Annegret T1 - A construction for non-rank facets of stable set polytopes of webs N2 - Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs [{\sl Giles and Trotter 1981, Oriolo 2001}] and claw-free graphs [{\sl Galluccio and Sassano 1997, Giles and Trotter 1981}]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [{\sl Grötschel, Lov\'asz, and Schrijver 1988}]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only [{\sl Dahl 1999, Trotter 1975}] while there are examples with clique number $\geq 4$ having non-rank facets [{\sl e.g. Liebling et al. 2003, Oriolo 2001, P\^echer and Wagler 2003}]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. We use this construction to prove, for several fixed values of $\omega$ including all odd values at least 5, that there are only finitely many webs with clique number $\omega$ whose stable set polytopes admit rank facets only. T3 - ZIB-Report - 03-21 KW - web KW - rank-perfect graph KW - stable set polytope KW - (non-)rank facet Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7437 ER - TY - GEN A1 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial Inequalities Representing Polyhedra N2 - Our main result is that every n-dimensional polytope can be described by at most (2n-1) polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n-2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities. T3 - ZIB-Report - 03-25 KW - polyhedra and polytopes KW - semi-algebraic sets KW - polyhedral combinatorics KW - polynomial inequalities KW - stability index Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7473 ER -