Facets of the knapsack polytope

A necessary and sufficient condition is given for an inequality with coefficients 0 or 1 to define a facet of the knapsack polytope, i.e., of the convex hull of 0–1 points satisfying a given linear inequality. A sufficient condition is also established for a larger class of inequalities (with coefficients not restricted to 0 and 1) to define a facet for the same polytope, and a procedure is given for generating all facets in the above two classes. The procedure can be viewed as a way of generating cutting planes for 0–1 programs.     

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     

Lifting the knapsack cover inequalities for the knapsack polytope

Valid inequalities for the knapsack polytope have proven to be very useful in exact algorithms for mixed-integer linear programming. In this paper, we focus on the knapsack cover inequalities, introduced in 2000 by Carr and co-authors. In general, these inequalities can be rather weak. To strengthen them, we use lifting. Since exact lifting can be time-consuming, we present two fast approximate lifting procedures. The first procedure is based on mixed-integer rounding, whereas the second uses superadditivity.     

The vertices of the knapsack polytope

The number of vertices of a polytope associated to the Knapsack integer programming problem is shown to be small. An algorithm for finding these vertices is discussed.     

Facets of the independent path-matching polytope

Cunningham and Geelen introduced the independent path-matching problem as a common generalization of the weighted matching problem and the weighted matroid intersection problem. Associated with an independent path-matching is an independent path-matching vector. The independent path-matching polytope of an instance of the independent path-matching problem is the convex hull of all the independent path-matching vectors. Cunningham and Geelen described a system of linear inequalities defining the independent path-matching polytope. In this paper, we characterize which inequalities in this system induce facets of the independent path-matching polytope, generalizing previous results on the matching polytope and the common independent set 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).     

Facets of the linear ordering polytope

LetD _n be the complete digraph onn nodes, and letP _LO ⁿ denote the convex hull of all incidence vectors of arc sets of linear orderings of the nodes ofD _n (i.e. these are exactly the acyclic tournaments ofD _n ). We show that various classes of inequalities define facets ofP _LO ⁿ , e.g. the 3-dicycle inequalities, the simplek-fence inequalities and various Möbius ladder inequalities, and we discuss the use of these inequalities in cutting plane approaches to the triangulation problem of input-output matrices, i.e. the solution of permutation resp. linear ordering problems.     

On the 0/1 knapsack polytope

This paper deals with the 0/1 knapsack polytope. In particular, we introduce the class ofweight inequalities. This class of inequalities is needed to describe the knapsack polyhedron when the weights of the items lie in certain intervals. A generalization of weight inequalities yields the so-called “weight-reduction principle” and the class of extended weight inequalities. The latter class of inequalities includes minimal cover and (l,k)-configuration inequalities. The properties of lifted minimal cover inequalities are extended to this general class of inequalities.     

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.     

Facets with fixed defect of the stable set polytope

The stable set polytope of a graph is the convex hull of the 0-1 vectors corresponding to stable sets of vertices. To any nontrivial facet ∑ _v∈V a(v)x _v ≤b of this polytope we associate an integer δ, called the defect of the facet, by δ=∑ _v∈V a(v)-2b. We show that for any fixed δ there is a finite collection of graphs (called “basis”) such that any graph with a facet of defect δ contains a subgraph which can be obtained from one of the graphs in the basis by a simple subdivision operation. Received: September 28, 1998 / Accepted: February 24, 2000?Published online April 20, 2000     

Facets of the balanced (acyclic) induced subgraph polytope

A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail.     

On the complexity of sequentially lifting cover inequalities for the knapsack polytope

The well-known sequentially lifted cover inequality is widely employed in solving mixed integer programs.However,it is still an open question whether a sequentially lifted cover inequality can be computed in polynomial time for a given minimal cover(Gu et al.(1999)).We show that this problem is N P-hard,thus giving a negative answer to the question.     

On the transversal Helly numbers of disjoint and overlapping disks

A family of disks is said to have the property T(k) if any k members of the family have a common line transversal. We call a family of unit diameter disks t-disjoint if the distances between the centers are greater than t. We consider for each natural number k≧ 3 the infimum t_k of the distances t for which any finite family of t-disjoint unit diameter disks with the property T(k) has a line transversal. We determine exact values of t₃ and t₄, and give general lower and upper bounds on the sequence t_k, showing that t_k = O(1/k) as k → ∞. In honour of Helge Tverberg’s seventieth birthday Received: 9 June 2005     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

Minimal covers,minimal sets and canonical facets of the posynomial knapsack polytope

An irredundant representation of the 0–1 solutions to a posynomial inequality in terms of covering constraints induced by minimal covers is given. This representation is further strengthened using extended covering constraints induced by maximal extensions of minimal covers. Necessary, sufficient, and in a special case necessary and sufficient conditions for an extended covering constraint induced by a minimal set to be a facet of the posynomial knapsack polytope are given.     

Cover by disjoint cliques cuts for the knapsack problem with conflicting items

The knapsack problem with conflicting items arises in several real-world applications. We propose a family of strong cutting planes and prove that a subfamily of these cuts can be facet-defining. Computational experiments show that the proposed cuts are very effective in reducing integrality gaps, providing dual bounds up to 78% tighter than formulations strengthened with traditional combinatorial cuts. We also show that it is possible to adapt a recently proposed lifting procedure to further strengthen the proposed cuts.     

Mutually disjoint designs and new 5‐designs derived from groups and codes

The article gives constructions of disjoint 5‐designs obtained from permutation groups and extremal self‐dual codes. Several new simple 5‐designs are found with parameters that were left open in the table of 5‐designs given in (G. B. Khosrovshahi and R. Laue, t‐Designs with t⩾3, in “Handbook of Combinatorial Designs”, 2nd edn, C. J. Colbourn and J. H. Dinitz (Editors), Chapman & Hall/CRC, Boca Raton, FL, 2007, pp. 79–101), namely, 5−(v, k, λ) designs with (v, k, λ)=(18, 8, 2m) (m=6, 9), (19, 9, 7m) (m=6, 9), (24, 9, 6m) (m=3, 4, 5), (25, 9, 30), (25, 10, 24m) (m=4, 5), (26, 10, 126), (30, 12, 440), (32, 6, 3m) (m=2, 3, 4), (33, 7, 84), and (36, 12, 45n) for 2⩽n⩽17. These results imply that a simple 5−(v, k, λ) design with (v, k)=(24, 9), (25, 9), (26, 10), (32, 6), or (33, 7) exists for all admissible values of λ. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 305–317, 2010