On the combinatorial structure of chromatic scheduling polytopes

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope.     

Facets of the clique partitioning polytope

A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW ¹,,W ^k such that eachW _i induces a clique, i.e., a complete (but not necessarily maximal) subgraph ofG, and such thatA = _i=1 ^k 1{uv|u, v W _i ,u v}. Given weightsw ^e for alle E, the clique partitioning problem is to find a clique partitioningA ofG such that _eA w _e is as small as possible. This problem—known to be-hard, see Wakabayashi (1986)—comes up, for instance, in data analysis, and here, the underlying graphG is typically a complete graph. In this paper we study the clique partitioning polytope of the complete graphK _n , i.e., is the convex hull of the incidence vectors of the clique partitionings ofK _n . We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs ofK _n induce facets of. The theoretical results described here have been used to design an (empirically) efficient cutting plane algorithm with which large (real-world) instances of the clique partitioning problem could be solved. These computational results can be found in Grötschel and Wakabayashi (1989).     

On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}

In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research.     

On the 0, 1 facets of the set covering polytope

In this paper, we consider inequalities of the form _jx_j , where _j equals 0 or 1, and is a positive integer. We give necessary and sufficient conditions for such inequalities to define facets of the set covering polytope associated with a 0, 1 constraint matrixA. These conditions are in terms of critical edges and critical cutsets defined in the bipartite incidence graph ofA, and are in the spirit of the work of Balas and Zemel on the set packing problem where similar notions were defined in the intersection graph ofA. Furthermore, we give a polynomial characterization of a class of 0, 1 facets defined from chorded cycles of the bipartite incidence graph. This characterization also yields all the 0, 1 liftings of odd-hole inequalities for the simple plant location polytope.Research partially supported by NSF grant ECS-8601660 and AFORS grant 87-0292.     

On the set covering polytope: I. All the facets with coefficients in {0, 1, 2}

While the set packing polytope, through its connection with vertex packing, has lent itself to fruitful investigations, little is known about the set covering polytope. We characterize the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and give necessary and sufficient conditions for such an inequality to be minimal and to be facet defining. We show that all inequalities in the above class are contained in the elementary closure of the constraint set, and that 2 is the largest value ofk such that all valid inequalities for the set covering polytope with integer coefficients no greater thank are contained in the elementary closure. We point out a connection between minimal inequalities in the class investigated and certain circulant submatrices of the coefficient matrix. Finally, we discuss conditions for an inequality to cut off a fractional solution to the linear programming relaxation of the set covering problem and to improve the lower bound given by a feasible solution to the dual of the linear programming relaxation.Research supported by the National Science Foundation through grant ECS-8503198 and the Office of Naval Research through contract N0001485-K-0198.     

On packing and covering polyhedra of consecutive ones circulant clutters

Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehman’s work or blocker/antiblocker duality, as is traditional in the field.     

Penalty computations for the set partitioning problem

The computation of penalties associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational tests which allow to fix some variables at their optimal value or to generate new constraints (cuts). We study in this paper the computation and the use of penalties as a tool to improve the efficiency of algorithms for solving set partitioning problems. This leads to a preprocessing scheme which can be embedded within any exact or approximate algorithm. The strength of these penalties is illustrated through computational results on some real-world set partitioning problems.This work was sponsored by FINEP (research contract number 4.3.86.0689-00), CNPq (research contract numbers 11.1592-84, 30.2281-85 and 40.2002-86.5), IBM Brazil and NSERC (grant # GP0036426).On leave from the Catholic University of Rio de Janeiro, Department of Electrical Engineering, Caixa Postal 38063, Gávea, Rio de Janeiro 22452, Brazil.     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

A fast approximation algorithm for solving the complete set packing problem

We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.     

Stochastic set packing problem

In this paper a stochastic version of the set packing problem (SPP), is studied via scenario analysis. We consider a one-stage recourse approach to deal with the uncertainty in the coefficients. It consists of maximizing in the stochastic SPP a composite function of the expected value minus the weighted risk of obtaining a scenario whose objective function value is worse than a given threshold. The splitting variable representation is decomposed by dualizing the nonanticipativity constraints that link the deterministic SPP with a 0-1 knapsack problem for each scenario under consideration. As a result a (structured) larger pure 0-1 model is created. We present several procedures for obtaining good feasible solutions, as well as a preprocessing approach for fixing variables. The Lagrange multipliers updating is performed by using the Volume Algorithm. Computational experience is reported for a broad variety of instances, which shows that the new approach usually outperforms a state-of-the-art optimization engine, producing a comparable optimality gap with smaller (several orders of magnitude) computing time.     

(1,k)-configurations and facets for packing problems

A new class of facets for knapsack polytopes is obtained. This class of inequalities is shown to define a polytope with zero–one vertices only. A combinatorial inequality is obtained from Fulkerson's max—max inequality.     

The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

Using dual network bounds in algorithms for solving generalized set packing partitioning problems

This article deals with a method to compute bounds in algorithms for solving the generalized set packing/partitioning problems. The problems under investigation can be solved by the branch and bound method. Linear bounds computed by the simplex method are usually used. It is well known that this method breaks down on some occasions because the corresponding linear programming problems are degenerate. However, it is possible to use the dual (Lagrange) bounds instead of the linear bounds. A partial realization of this approach is described that uses a network relaxation of the initial problem. The possibilities for using the dual network bounds in the approximation techniques to solve the problems under investigation are described.     

All-integer column generation for set partitioning: Basic principles and extensions

Column generation, combined with an appropriate integer programming technique, has shown to be a powerful tool for solving huge integer programmes arising in various applications. In these column generation approaches, the master problem is often of a set partitioning type.     

The Steiner tree problem II: Properties and classes of facets

This is the second part of two papers addressing the study of the facial structure of the Steiner tree polyhedron. In this paper we identify several classes of facet defining inequalities and relate them to special classes of graphs on which the Steiner tree problem is known to be NP-hard.Corresponding author.The author appreciates partial support from National Science Foundation Grants Nos. DSM-8606188 and ECS 8800281.     

Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

Uncapacitated Euclidean Hub Location: Strengthened Formulation,New Facets and a Relax-and-cut Algorithm

The multiple allocation uncapacitated hub location problem is considered. This problem arises in transportation systems when several locations send and receive passengers and/or express packages and the performance of these systems can be improved by using transshipment points (hubs), where the passengers/packages are collected and distributed. An Integer Programming formulation, the one giving the best computational results until now, serves as a basis for the solution method. Using the fact that the transportation costs between hubs satisfy the triangle inequality, an analysis of the set of solutions that are not candidates to be optimal is carried out and, as a consequence, the formulation of the problem can be strengthened by means of powerful valid inequalities obtained through the study of the intersection graph of an associated set packing problem. The algorithm developed uses the most promising of these inequalities in a Lagrangian relaxation context to reduce the size of the branching tree and improve the computational times. This improvement is shown by means of a computational study, where a set of instances are optimally solved with low computational effort.     

Gear composition and the stable set polytope

We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of when G is claw-free.