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.     

Facets and lifting procedures for the set covering polytope

Given a family of subsets of an arbitrary groundsetE, acover of is any setC E having non-empty intersection with every subset in. In this paper we deal with thecovering polytope, i.e., the convex hull of the incidence vectors of all the covers of. In Section 2 we review all the known properties of the covering polytope. In Sections 3 and 4 we introduce two new classes of non-Boolean facets of such a polytope. In Sections 5 and 6 we describe some non-sequential lifting procedures. In Section 7 a generalization of the notion ofweb introduced by L.E. Trotter is presented together with the facets of the covering polytope produced by such a structure.Moreover, the strong connections between several combinatorial problems and the covering problem are pointed out and, exploiting those connections, some examples are presented of new facets for the Knapsack and Acyclic Subdigraph polytopes.     

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.     

Facets of the independent set polytope

Theoretical results pertaining to the independent set polytope P^ISP=conv{x{0,1}ⁿ:Axb} are presented. A conflict hypergraph is constructed based on the set of dependent sets which facilitates the examination of the facial structure of P^ISP. Necessary and sufficient conditions are provided for every nontrivial 0-1 facet-defining inequalities of P^ISP in terms of hypercliques. The relationship of hypercliques and some classes of knapsack facet-defining inequalities are briefly discussed. The notion of lifting is extended to the conflict hypergraph setting to obtain strong valid inequalities, and back-lifting is introduced to strengthen cut coefficients. Preliminary computational results are presented to illustrate the usefulness of the theoretical findings.Mathematics Subject Classification (2000): 90C11, 90C57, 90C35     

On the stable set polytope of a series-parallel graph

We give a short proof of Chvátal's conjecture that the nontrivial facets of the stable set polytope of a series-parallel graph all come from edges and odd holes.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and by CP Rail.     

On the complete set packing and set partitioning polytopes: Properties and rank 1 facets

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary $n$-row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.     

How to recycle your facets

We show how to transform any inequality defining a facet of some 0/1-polytope into an inequality defining a facet of the acyclic subgraph polytope. While this facet-recycling procedure can potentially be used to construct ‘nasty’ facets, it can also be used to better understand and extend the polyhedral theory of the acyclic subgraph and linear ordering problems.     

Clustering heuristics for set covering

We introduce a new class of set covering heuristics, based on clustering techniques. In its simplest form, a heuristic in this class may be described as follows: firstly, partition the column set into clusters formed by columns that are close to each other (e.g. in the Hamming distance sense). Then select a best (e.g. a cheapest) column in each cluster; if the selected columns form a coverC, then extract fromC a prime cover and stop; else, modify the partition (e.g. by increasing the number of clusters) and repeat. We describe two implementations of this general algorithmic strategy, relying on the Single Linkage and the Leader clustering algorithm, respectively. Numerical experiments performed on 72 randomly generated test problems with 200 or 400 rows and 1000 columns indicate that the above two heuristics often yield cheaper covers than other well-known (greedy-type) heuristics when the cost-range is not too narrow.The present work is based on R.K. Kwatera's dissertation, written under the supervision of B. Simeone. A preliminary version was presented at EURO VIII, Paris, July 1988.     

On the facets of the secondary polytope

The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope.The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.     

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.     

The equipartition polytope. I: Formulations,dimension and basic facets

The following basic clustering problem arises in different domains, ranging from physics, statistics and Boolean function minimization.Given a graphG = (V, E) and edge weightsc _e , partition the setV into two sets of 1/2|V| and 1/2|V| nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized.Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we give some integer programming formulations of the equicut problem, study the dimension of the equicut polytope and describe some basic classes of facet-inducing inequalities forQ(G). Partial support of NSF grants DMS 8606188 and ECS 8800281.This work was done while these two authors visited IASI, Rome, in Spring 1987.     

Computing the minimal covering set

We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set–the minimal upward covering set and the minimal downward covering set–unless P equals NP. Finally, we observe a strong relationship between von Neumann–Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

On a new class of nonlinear set covering problems arising in wireless network design

This is a summary of the author’s PhD thesis, supervised by Edoardo Amaldi and defended on 28 April 2006 at Politecnico di Milano, Dipartimento di Matematica. The thesis is written in English and is available from the author upon request. The thesis investigates a class of nonlinear set covering variants arising from the problem of designing single-frequency Wireless Local Area Networks (WLANs) with maximum efficiency. In the first part of the thesis a basic hyperbolic formulation of the problem is considered. After a complexity and approximability study, the problem is tackled by linearization techniques, and by Lagrangean and Dantzig–Wolfe decompositions. The second part of the thesis focuses on variants accounting for various relevant features of the WLAN application. A Branch-and-Price algorithm is presented, and extensions to the multiple-frequency WLAN design problem are considered.      

A probabilistic analysis of the set covering problem

A probabilistic analysis of the minimum cardinality set covering problem (SCP) is developed, considering a stochastic model of the (SCP), withn variables andm constraints, in which the entries of the corresponding (m, n) incidence matrix are independent Bernoulli distributed random variables, each with constant probabilityp of success. The behaviour of the optimal solution of the (SCP) is then investigated as bothm andn grow asymptotically large, assuming either an incremental model for the evolution of the matrix (for each size, the matrixA is obtained bordering a matrix of smaller size by new columns and rows) or an independent one (for each size, an entirely new set of entries forA are considered). Two functions ofm are identified, which represent a lower and an upper bound onn in order the (SCP) to be a.e. feasible and not trivial. Then, forn lying within these bounds, an asymptotic formula for the optimum value of the (SCP) is derived and shown to hold a.e.The performance of two simple randomized algorithms is then analyzed. It is shown that one of them produces a solution value whose ratio to the optimum value asymptotically approaches 1 a.e. in the incremental model, but not in the independent one, in which case the ratio is proved to be tightly bounded by 2 a.e. Thus, in order to improve the above result, a second randomized algorithm is proposed, for which it is proved that the ratio between the approximate solution value and the optimum approaches 1 a.e. also in the independent model.