Abstract Let $$D\,=\,(V,A)$$ D = ( V , A ) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in $$\{x:x_a=i\}$$ { x : x a = i } for any $$a\in A,i\in \{0,1\}$$ a ∈ A , i ∈ { 0 , 1 } . We prove under a mild necessary condition that $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs. Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say $$\tau $$ τ , is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number $$p\,\ge \,2$$ p ≥ 2 , a p-adic packing of dijoins of value $$\tau $$ τ and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A , where F is the face of P satisfying $$x(\delta ^+(U))=1$$ x ( δ + ( U ) ) = 1 for every minimum dicut $$\delta ^+(U)$$ δ + ( U ) .

Abstract. Let [Formula: see text] be a digraph. A dicut is a cut [Formula: see text] for some nonempty proper vertex subset [Formula: see text] such that [Formula: see text], a dijoin is an arc subset that intersects every dicut at least once, and more generally a [Formula: see text]- dijoin is an arc subset that intersects every dicut at least [Formula: see text] times. Our first result is that [Formula: see text] can be partitioned into a dijoin and a [Formula: see text]-dijoin where [Formula: see text] denotes the smallest size of a dicut. Woodall conjectured the stronger statement that [Formula: see text] can be partitioned into [Formula: see text] dijoins. Let [Formula: see text], and suppose every dicut has weight at least [Formula: see text], for some integer [Formula: see text]. Let [Formula: see text], where each [Formula: see text] is the integer in [Formula: see text] equal to [Formula: see text] mod [Formula: see text]. We prove the following results: If [Formula: see text], then there is an equitable [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], then there is a [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], [Formula: see text], and [Formula: see text], then [Formula: see text] can be partitioned into three dijoins. Each result is best possible: (i) does not hold for [Formula: see text] even if [Formula: see text], (ii) does not hold for [Formula: see text], and (iii) does not hold for general [Formula: see text].

A vector is dyadic if each of its entries is a dyadic rational number, i.e., an integer multiple of $\frac{1}{2^k}$ for some nonnegative integer $k$. We prove that every clean clutter with a covering number of at least two has a dyadic fractional packing of value two. This result is best possible, for there exist clean clutters with a covering number of three and no dyadic fractional packing of value three. Examples of clean clutters include ideal clutters, binary clutters, and clutters without an intersecting minor. Our proof is constructive and leads naturally to an (albeit exponential) algorithm. We improve the running time to quasi-polynomial in the rank of the input and to polynomial in the binary case.

Let $G=(V,E)$ be a graph, and $T\subseteq V$ a nonempty subset of even cardinality. The famous theorem of Edmonds and Johnson on the $T$-join polyhedron implies that the minimum cardinality of a $T$-cut is equal to the maximum value of a fractional packing of $T$-joins. In this paper, we prove that the fractions assigned may be picked as dyadic rationals, i.e., of the form $\frac{a}{2^k}$ for some integers $a,k\geq 0$.

A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that every 4-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it in the binary case. Two key ingredients for our proof are Jaeger’s 8-flow theorem for graphs, and Seymour’s characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture, we also note that it follows from an unpublished conjecture of Seymour from 1975.

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods.

There has been a recent interest in cutting planes generated from two or more rows of the optimal simplex tableau. One can construct examples of integer programs for which a single cutting plane generated from two rows dominates the entire split closure. Motivated by these theoretical results, we study the effect of adding a family of cutting planes generated from two rows on a set of instances from the MIPLIB library. The conclusion of whether these cuts are competitive with Gomory mixed-integer cuts is very sensitive to the experimental setup. In particular, we consider the issue of reliability versus aggressiveness of the cut generators, an issue that is usually not addressed in the literature.

We show that maximal S-free convex sets are polyhedra when S is the set of integral points in some rational polyhedron of $\mathbb{R}^n$. This result extends a theorem of Lovász characterizing maximal lattice-free convex sets. Our theorem has implications in integer programming. In particular, we show that maximal S-free convex sets are in one-to-one correspondence with minimal inequalities.

Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadrilateral inequalities. On the other hand, the approximation produced by split inequalities may be arbitrarily bad.

This paper intends to show that the time needed to solve mixed-integer-programming problems by branch and bound can be roughly predicted early in the solution process. We construct a procedure that can be implemented as part of an MIP solver. It is based on analyzing the partial tree resulting from running the algorithm for a short period of time and predicting the shape of the whole tree. The procedure is tested on instances from the literature. This work was inspired by the practical applicability of such a result.

In a graph G, an odd hole is an induced odd cycle of length at least 5. A clique of G is a set of pairwise adjacent vertices. In this paper we consider the class ${\cal C}_k$ of graphs whose cliques have a size bounded by a constant k. Given a graph G in ${\cal C}_k$, we show how to recognize in polynomial time whether G contains an odd hole.

We present a polynomial algorithm for recognizing whether a graph is perfect, thus settling a long standing open question. The algorithm uses a decomposition theorem of Conforti, Cornuejols and Vuskovic. Another polynomial algorithm for recognizing perfect graphs, which does not use decomposition, was obtained simultaneously by Chudnovsky and Seymour. Both algorithms need a first phase developed jointly by Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic.

For an integer program, a k-cutis a cutting plane generated by the Gomory mixed integer procedure from a row of the LP tableau after multiplying it by a positive integer k. With this terminology, Gomory mixed integer cuts are just 1-cuts. In this paper, we compare the k-cuts (k= 2) with Gomory mixed integer cuts. In particular, we prove in the pure case that with exactly 50% probability the k-cuts perform better variable-wise than the Gomory mixed integer cuts. Some computational experiments on knapsack problems are reported to illustrate this property.

A binary clutter is the family of odd circuits of a binary matroid, that is, the family of circuits that intersect with odd cardinality a fixed given subset of elements. Let A denote the 0,1 matrix whose rows are the characteristic vectors of the odd circuits. A binary clutter is ideal if the polyhedron $\{ x \geq {\bf 0}: \; Ax \geq {\bf 1} \}$ is integral. Examples of ideal binary clutters are st-paths, st-cuts, T-joins or T-cuts in graphs, and odd circuits in weakly bipartite graphs. In 1977, Seymour [J. Combin. Theory Ser. B, 22 (1977), pp. 289--295] conjectured that a binary clutter is ideal if and only if it does not contain ${\cal{L}}_{F_7}$, ${\cal{O}}_{K_5}$, or $b({\cal{O}}_{K_5})$ as a minor. In this paper, we show that a binary clutter is ideal if it does not contain five specified minors, namely the three above minors plus two others. This generalizes Guenin's characterization of weakly bipartite graphs [J. Combin. Theory Ser., 83 (2001), pp. 112--168], as well as the theorem of Edmonds and Johnson [ Math. Programming, 5 (1973), pp. 88--124] on T-joins and T-cuts.

In this article, we consider a class of 0-1 programs that, although innocent looking, is a challenge for existing solution methods. Solving even small instances from this class is extremely difficult for conventional branch-and-bound or branch-and-cut algorithms. We also experimented with basis reduction algorithms and with dynamic programming without much success. The article then examines the performance of two other methods: a group relaxation for 0,1 programs, and a sorting-based procedure following an idea of Wolsey. Although the results with these two methods are somewhat better than with the other four when it comes to checking feasibility, we offer this class of small 0,1 programs as a challenge to the research community.

A hole in a graph is a chordless cycle of length greater than three. In this paper we present a decomposition theorem for graphs that contain no even hole. This theorem yields a polytime algorithm to recognize whether a graph contains an even hole.

In propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In this paper, we consider sets of clauses for which the corresponding integer programs can be solved as linear programs. We prove that balanced sets of clauses have this property.

Several problems of propositional logic, such as satisfiability, MAXSAT and logical inference, can be formulated as integer programs. The authors consider sets of clauses for which these integer programs can be solved as linear programs. They prove that balanced sets of clauses have this property.>

Abstract The matching problem in bipartite graphs can be solved by an elegant primal‐dual algorithm. The purpose of this paper is to introduce concepts which make it possible to generalize this algorithm to some classes of hypergraphs. We illustrate the approach by providing a polynomial primal‐dual algorithm for the matching problem in hypergraphs without odd cycles.

This paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear equalities and inequalities. The central notion is that of a 3-edge cutset, namely, a set of 3 edges that, when removed, disconnects the graph. Conversely, our approach can be used to construct classes of graphs for which there exists a polynomial algorithm for the traveling salesman problem. The approach is illustrated on two examples, Halin graphs and prismatic graphs.