90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Filtern
Erscheinungsjahr
Dokumenttyp
- ZIB-Report (46)
- Dissertation (1)
Sprache
- Englisch (47)
Volltext vorhanden
- ja (47)
Gehört zur Bibliographie
- nein (47)
Schlagworte
- polyhedral combinatorics (7)
- mixed-integer programming (6)
- integer programming (5)
- branching rule (4)
- mixed integer programming (4)
- stable set polytope (4)
- branch-and-bound (3)
- polyhedra and polytopes (3)
- polynomial inequalities (3)
- routing (3)
Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.
Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.
The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time.
Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average.
Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.
In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules.
We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.
In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.
The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.
One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way.
This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.
This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with
fixed convexity behavior over a box.
Computational results comparing our cut-generation algorithms with
state-of-the-art global
optimization software on a series of randomly generated test instances are reported and discussed.
Cloud branching
(2013)
Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud) of the current LP relaxation. These strategies naturally extend state-of-the-art methods like strong branching, pseudocost branching, and their hybrids.
We show that by exploiting dual degeneracy, and thus multiple alternative optimal solutions, it is possible to enhance traditional methods. We present preliminary computational results, applying the newly proposed strategy to full strong branching, which is known to be the MIP branching rule leading to the fewest number of search nodes. It turns out that cloud branching can reduce the mean running time by up to 30% on standard test sets.
We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances.
In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this problem one is interested in optimal configurations, where an energy function measures the benefit if certain path elements are placed on adjacent vertices of the graph. The most prominent application of this problem is the protein folding problem in biochemistry. On a set of selected instances, we demonstrate the computational merits of our approach.
In this paper, we study the neighbourlicity of the polytope $P_{k n}^2$ constituted by the $k$-cliques of the complete graph $K_n$ on $n$ vertices. We prove that this polytope is $3$-, but not $4$-neighbourly. Following a remark of Pierre Duchet, we partially generalize this result to the $k$-clique polytopes of $r$-uniform complete hypergraphs, $P_{kn}^r$. We show that the neighbourlicity of $P_{kn}^r$ is between $r$ and $2^r-1$ whenever $k\geq r+1$ and $n\geq k+r+1$. Computational results indicate that the upper bound is tight.
We consider a variant of the classical lot-sizing problem in which the capacity in each period is an integer multiple of some basic batch size. Pochet and Wolsey (Math. Oper. Res. 18, 1993) presented an O(n^2 min{n,C}) algorithm to solve this problem and a linear program with O(n^3) variables and inequalities, where n is the number of periods and C the batch size. We provide a linear program of size O(n^2 min{n,C}), that is, in case that C < n, our formulation is smaller.
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average.
This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.
Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment structure. We investigate the detection of symmetries appearing in this approach. We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear time if the assignment structure is known.
We address the property checking problem for SoC design verification at the register transfer level (RTL) by integrating techniques from integer programming, constraint programming, and SAT solving. Specialized domain propagation and preprocessing algorithms for individual RTL operations extend a general constraint integer programming framework. Conflict clauses are learned by analyzing infeasible LPs and deductions, and by employing reverse propagation. Experimental results show that our approach outperforms SAT techniques for proving the validity of properties on circuits containing arithmetics.
This article describes the main concepts and techniques that have been developed during the last year at ZIB to solve dimensioning and routing optimization problems for IP networks. We discuss the problem of deciding if a given path set corresponds to an unsplittable shortest path routing, the fundamental properties of such path sets, and the computational complexity of some basic network planning problems for this routing type. Then we describe an integer-linear programming approach to solve such problems in practice. This approach has been used successfully in the planning of the German national education and research network for several years.
This thesis is concerned with dimensioning and routing optimization problems for communication networks that employ a shortest path routing protocol such as OSPF, IS-IS, or RIP. These protocols are widely used in the Internet. With these routing protocols, all end-to-end data streams are routed along shortest paths with respect to a metric of link lengths. The network administrator can configure the routing only by modifying this metric. In this thesis we consider the unsplittable shortest path routing variant, where each communication demand must be sent unsplit through the network. This requires that all shortest paths are uniquely determined. The major difficulties in planning such networks are that the routing can be controlled only indirectly via the routing metric and that all routing paths depend on the same routing metric. This leads to rather complicated and subtle interdependencies among the paths that comprise a valid routing. In contrast to most other routing schemes, the paths for different communication demands cannot be configured independent of each other. Part I of the thesis is dedicated to the relation between path sets and routing metrics and to the combinatorial properties of those path sets that comprise a valid unsplittable shortest path routing. Besides reviewing known approaches to find a compatible metric for a given path set (or to prove that none exists) and discussing some properties of valid path sets, we show that the problem of finding a compatible metric with integer lengths as small as possible and the problem of finding a smallest possible conflict in the given path set are both NP-hard to approximate within a constant factor. In Part II of the thesis we discuss the relation between unsplittable shortest path routing and several other routing schemes and we analyze the computational complexity of three basic unsplittable shortest path routing problems. We show that the lowest congestion that can be obtained with unsplittable shortest path routing may significantly exceed that achievable with other routing paradigms and we prove several non-approximability results for unsplittable shortest path routing problems that are stronger than those for the corresponding unsplittable flow problems. In addition, we derive various polynomial time approximation algorithms for general and special cases of these problems. In Part III of the thesis we finally develop an integer linear programming approach to solve these and more realistic unsplittable shortest path routing problems to optimality. We present alternative formulations for these problems, discuss their strength and computational complexity, and show how to derive strong valid inequalities. Eventually, we describe our implementation of this solution approach and report on the numerical results obtained for real-world problems that came up in the planning the German National Research and Education Networks G-WiN and X-WiN and for several benchmark instances.
We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.
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.
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.
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.
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).
Orbitopal Fixing
(2006)
The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving this kind of symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned permutations. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch (2006)). However, it does not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks.
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.
\noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope.
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.
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.
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.
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.
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.
We investigate the impact of hop-limited routing paths on the total cost of a telecommunication network. For different survivability settings (dedicated protection, link and path restoration), the optimal network cost without restrictions on the admissible path set is compared to the results obtained with two strategies to impose hop limits on routing paths. In a thorough computational study on optimal solutions for nine real-world based problem instances, we show that hop limits should be avoided if the technology allows it and network cost is a major planning issue. In this case, column generation should be employed to deal with all routing paths. If hop-limits are required, these should be defined for each demand individually and as large as possible.
Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance.
We suggest a new model for the design of telecommunication networks which integrates decisions about the topology, configuration of the switching hardware, link dimensioning, and protected routing of communication demands. Applying the branch-and-cut-algorithm implemented in our network planning and optimization tool DISCNET, we demonstrate that real-world based network planning instances of such an enhanced model can be solved.
Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there exist no polynomial time approximation algorithms with a guaranteed quality. One kind of algorithms which turned out to be successful for many other combinatorial optimization problems uses cutting plane methods. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities.
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.
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.
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.
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.
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.
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})$.
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$.
Antiwebs are Rank-Perfect
(2002)
\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.
Stable Multi-Sets
(2000)
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.