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 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.     

A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets

Given any family of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on the complete digraphG, we show that all members of are facet defining if the primitive members of (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities forP(G) by lifting inequalities that are facet inducing forP(G), whereG is some induced subgraph ofG. Unlike traditional lifting, where the lifted coefficients are calculated one by one and their value depends on the lifting sequence, our lifting procedure replaces nodes ofG with cliques ofG and uses closed form expressions for calculating the coefficients of the new arcs, which are sequence-independent. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as special cases most known families of facet defining inequalities.Research supported by Grant DDM-8901495 of the National Science Foundation and Contract N00014-85-K-0198 of the U.S. Office of Naval Research.Research supported by M.U.R.S.T., Italy.     

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 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.     

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 theoretical justification of the set covering greedy heuristic of Caprara et al.

Large scale set covering problems have often been approached by constructive greedy heuristics, and much research has been devoted to the design and evaluation of various greedy criteria for such heuristics. A criterion proposed by Caprara et al. (1999) is based on reduced costs with respect to the yet unfulfilled constraints, and the resulting greedy heuristic is reported to be superior to those based on original costs or ordinary reduced costs.We give a theoretical justification of the greedy criterion proposed by Caprara et al. by deriving it from a global optimality condition for general non-convex optimisation problems. It is shown that this criterion is in fact greedy with respect to incremental contributions to a quantity which at termination coincides with the deviation between a Lagrangian dual bound and the objective value of the feasible solution found.     

On characterizing full dimensional weak facets in DEA with variable returns to scale technology

The frontier of the Production Possibility Set (PPS) consists of two types of full dimensional facets, efficient and weak facets. Identification of all facets of the PPS can be used in sensitivity and stability analysis, to find the closet target for inefficient Decision-Making Units (DMUs), and to determine the status of returns to scale of a DMU, among others. There has been a surge of articles on determining efficient facets in recent years. There are, however, many cases where knowledge of weak facets is required for a thorough analysis. This is the case, in particular, when the frontier of the PPS is constructed only of weak facets. The existing algorithms for finding weak facets either require knowledge of all extreme directions of the PPS or applicable only under some restrictions on the position of weak efficient DMUs. We provide a complete characterization of weak facets. Using this characterization, we then devise a different algorithm to find weak facets. We illustrate our algorithm using a numerical example.     

{0, 1/2}-Chvátal-Gomory cuts

Given the integer polyhedronP _t := conv{x ∈ℤ ⁿ :Ax⩽b}, whereA ∈ℤ ^{m × n} andb ∈ℤ ^m , aChvátal-Gomory (CG)cut is a valid inequality forP ₁ of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ ₊ ^m such that λτA∈ℤ ⁿ . In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2} ^m . We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of strong inequalities forP ₁. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.     

On the symmetric travelling salesman problem II: Lifting theorems and facets

Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.     

On {2, 3}-hyperidentities in invertible {2, 3}-algebras with a ternary group operation

The paper gives a characterization of invertible {2, 3}-algebras with a ternary group operations and balanced {2, 3}-hyperidentities of the first genus and of length 4.     

On the Recursive Sequence x_{n + 1} = {{ \mgreek{g} x_{n-1} + \mgreek{d} x_{n-2}} \over {Cx_{n-1} + Dx_{n-2}}}

We investigate the global character of solutions of the equation in the title with positive parameters and positive initial conditions. We obtain results about the global attractivity of the equilibrium, the existence and attractivity of the period-two solution and the semicycles.     

｛0,1,3｝问题摄动形式所对应的测度

给定实数λ,α以及Ｒ上（以λ,α为参数）的压缩自相似映射Ｓ１（ｘ）＝λｘ, Ｓ２（ｘ）＝ λｘ＋ａ, Ｓ３（ｘ）＝ λｘ＋３,记满足测度方程ｖ＝（１／３）∑ｉ＝１ｖｏＳｉ－１的唯一概率测度为ｕλ,α本文得到：（１）当固定 λ∈Ａ Ｅ（１／３, ２／５）时,则在 Ｌｅｂｅｓｇｕｅ测度意义下,对于 ａ．ｅ．的 ａ∈（０,１）,测度 ｕλ,α绝对连续,且存在平方可积密度．（２）若λ－１是 Ｐ．Ｖ．数,且 α是λ的有理系数多项式,则测度ｕλ,α是奇异测度．     

On the Number of Solutions of the Equation a_{1}x_{1}^{m_{1}}+\cdots +a_{n}x_{n}^{m_{n}}=bx_{1}\cdots x_{n} in a Finite Field

We obtain an explicit formula for the number of solutions of a special equation in a finite field under a certain restriction on the exponents. Mathematics Subject Classifications (2000) primary: 11G25, secondary: 11T24.     

On the Dynamics of x_{\bf{n} + \bf{1}} = {{ \mgreek{a} + \mgreek{g} x_{n-1} + \mgreek{d} x_{n-2}} \over {A + x_{n-2}}}

We investigate the global stability, the periodic character and the boundedness nature of solutions of the equation in the title for all admissible nonnegative values of the parameters and the initial conditions. We show that the solutions exhibit a trichotomy character depending on how the parameter γ compares to the sum of the parameters δ and A.