On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

Simultaneous rational approximation to the successive powers of a real number

Let n be an integer ≥ 1 and let θ be a real number which is not an algebraic number of degree ≤ [n/2]. We show that there exist ? > 0 and arbitrary large real numbers X such that the system of linear inequalities |x₀| ≤ X and |x₀θ^j − x_j| ≤ ?X^−1/[n/2] for 1 < j < n, has only the zero solution in rational integers x₀,…, x_n. This result refines a similar statement due to H. Davenport and W. M. Schmidt, where the upper integer part [n/2] is replaced everywhere by the integer part [n/2]. As a corollary, we improve slightly the exponent of approximation to 0 by algebraic integers of degree n + 1 over Q obtained by these authors.     

On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube

Split cuts are prominent general-purpose cutting planes in integer programming. The split closure of a rational polyhedron is what is obtained after intersecting the half-spaces defined by all the split cuts for the polyhedron. In this paper, we prove that deciding whether the split closure of a rational polytope is empty is NP-hard, even when the polytope is contained in the unit hypercube. As a direct corollary, we prove that optimization and separation over the split closure of a rational polytope in the unit hypercube are NP-hard, extending an earlier result of Caprara and Letchford.     

Monoidal cut strengthening revisited

There are two distinct strengthening methods for disjunctive cuts with some integer variables; they differ in the way they modularize the coefficients. In this paper, we introduce a new variant of one of these methods, the monoidal cut strengthening procedure, based on the paradox that sometimes weakening a disjunction helps the strengthening procedure and results in sharper cuts. We first derive a general result that applies to cuts from disjunctions with any number of terms. It defines the coefficients of the cut in a way that takes advantage of the option of adding new terms to the disjunction. We then specialize this result to the case of split cuts for mixed integer programs with some binary variables, in particular Gomory mixed integer cuts, and to intersection cuts from multiple rows of a simplex tableau. In both instances we specify the conditions under which the new cuts have smaller coefficients than the cuts obtained by either of the two currently known strengthening procedures.     

Optimizing over the split closure

The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation P of a mixed integer program (MIP) is termed the (elementary, or rank 1) split closure of P. This paper deals with the problem of optimizing over the elementary split closure. This is accomplished by repeatedly solving the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. Following Caprara and Letchford [17], we formulate this separation problem as a nonlinear mixed integer program that can be treated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We develop an algorithmic framework to deal with the resulting PMILP by creating and maintaining a dynamically updated grid of parameter values, and use the corresponding mixed integer programs to generate rank 1 split cuts. Our approach was implemented in the COIN-OR framework using CPLEX 9.0 as a general purpose MIP solver. We report our computational results on well-known benchmark instances from MIPLIB 3.0 and several classes of structured integer and mixed integer problems. Our computational results show that rank-1 split cuts close more than 98% of the duality gap on 15 out of 41 mixed integer instances from MIPLIB 3.0. More than 75% of the duality gap can be closed on an additional 10 instances. The average gap closed over all 41 instances is 72.78%. In the pure integer case, rank-1 split cuts close more than 75% of the duality gap on 13 out of 24 instances from MIPLIB 3.0. On average, rank 1 split cuts close about 72% of the duality gap on these 24 instances. We also report results on several classes of structured problems: capacitated versions of warehouse location, single-source facility location, p-median, fixed charge network flow, multi-commodity network design with splittable and unsplittable flows, and lot sizing. The fraction of the integrality gap closed varies for these problem classes between 100 and 67%. We also gathered statistics on the average coefficient size (absolute value) of the disjunctions generated. They turn out to be surprisingly small. Research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133.     

A constructive characterization of the split closure of a mixed integer linear program

Two independent proofs of the polyhedrality of the split closure of mixed integer linear program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Köppe and Weismantel.     

Valid inequalities for mixed integer linear programs

This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength. Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894.     

Laguerre polynomial expansions in indefinite inner product spaces

When ?j ? 1 < α < ?j, where j is a positive integer, the Laguerre polynomials {L_n^(α)}_{n = 0}^∞ form a complete orthogonal set in a nondegenerate inner product space H which is defined by employing an appropriate regularized linear functional on H^(j)[[0, ∞); x^{α + j}e^?x]. Expansions in terms of these Laguerre polynomials are exhibited. The Laguerre differential operator is shown to be self-adjoint with real, discrete, integer eigenvalues. Its spectral resolution and resolvent are exhibited and discussed.     

Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in ${\mathbb{R}^2}$ , and various types of disjunctions. Recently Li and Richard (2008), studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (Presentation at the Spring Meeting of the American Mathematical Society (Western Section), San Francisco, 2009) initiated the study of cuts for the two-row continuous group relaxation obtained from 2-branch split disjunctions. We study these cuts (and call them cross cuts) for the two-row continuous group relaxation, and for general MIPs. We also consider cuts obtained from asymmetric 2-branch disjunctions which we call crooked cross cuts. For the two-row continuous group relaxation, we show that unimodular cross cuts (the coefficients of the two split inequalities form a unimodular matrix) are equivalent to the cuts obtained from maximal lattice-free sets other than type 3 triangles. We also prove that all 2D lattice-free cuts and their S-free extensions are crooked cross cuts. For general mixed integer sets, we show that crooked cross cuts can be generated from a structured three-row relaxation. Finally, we show that for the corner relaxation of an MIP, every crooked cross cut is a 2D lattice-free cut.     

Nonsingularity of least common multiple matrices on gcd-closed sets

Let n be a positive integer. Let S={x₁,…,x_n} be a set of n distinct positive integers. The least common multiple (LCM) matrix on S, denoted by [S], is defined to be the n×n matrix whose (i,j)-entry is the least common multiple [x_i,x_j] of x_i and x_j. The set S is said to be gcd-closed if for any x_i,x_j∈S,(x_i,x_j)∈S. For an integer m>1, let ω(m) denote the number of distinct prime factors of m. Define ω(1)=0. In 1997, Qi Sun conjectured that if S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. In this paper, we settle completely Sun's conjecture. We show the following result: (i). If S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. Namely, Sun's conjecture is true; (ii). For each integer r?3, there exists a gcd-closed set S satisfying max_x∈S{ω(x)}=r, such that the LCM matrix [S] is singular.     

A note on the split rank of intersection cuts

In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that élog₂ (l)ù{\lceil \log_2 (l)\rceil} is a lower bound on the split rank of the intersection cut, where l is the number of integer points lying on the boundary of the restricted lattice-free set satisfying the condition that no two points lie on the same facet of the restricted lattice-free set. The use of this result is illustrated by obtaining a lower bound of élog₂( n+1) ù{\lceil \log_2( n+1) \rceil} on the split rank of n-row mixing inequalities.     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

Enhanced intersection cutting-plane approach for linear complementarity problems

In this paper, we develop an enhanced intersection cutting-plane algorithm for solving a mixed integer 0–1 bilinear programming formulation of the linear complementarity problem (LCP). The matrixM associated with the LCP is not assumed to possess any special structure, except that the corresponding feasible region is assumed to be bounded. A procedure is described to generate cuts that are deeper versions of the Tuy intersection cuts, based on a relaxation of the usual polar set. The proposed algorithm then attempts to find an LCP solution in the process of generating either a single or a pair of such strengthened intersection cuts. The process of generating these cuts involves a vertexranking scheme that either finds an LCP solution, or else these cuts eliminate the entire feasible region leading to the conclusion that no LCP solution exists. Computational experience on various test problems is provided.This material is based upon work supported by the National Science Foundation under Grant No. DMII-9121419 to the first author and Grant No. DMII-9114489 to the third author. The authors gratefully acknowledge the constructive suggestions of a referee that helped focus the approach and its presentation.     

An effective iterative method for computing real and complex roots of systems of nonlinear equations

A simple and flexible iterative method is proposed to determine the real or complex roots of any system of nonlinear equations F(x)=0. The idea is based on passing defined functions G_j(x_j),j=1,…,n tangent to F_i(x_j),i,j=1,…,n at an arbitrary starting point. Choosing G_j(x_j) in the form of or or any other reversible function compatible to F_i(x_j), where k is obtained for the best correlation with the function F_i(x_j), gives an added freedom, which in contrast with all existing methods, accelerates the convergence.The method that was first proposed for computing the roots of any single function is now adopted for a system of nonlinear equations. This method is compared to some classical and famous methods such as Newton’s method and Newton-Simpson’s method. The results show the effectiveness and robustness of this new method.     

Generating Cuts from Surrogate Constraint Analysis for Zero-One and Multiple Choice Programming

This paper presents a new surrogate constraint analysis that givesrise to a family of strong valid inequalities calledsurrogate-knapsack (S-K) cuts. The analytical procedure presentedprovides a strong S-K cut subject to constraining the values ofselected cut coefficients, including the right-hand side. Ourapproach is applicable to both zero-one integer problems and problemshaving multiple choice (generalized upper bound) constraints. We alsodevelop a strengthening process that further tightens the S-K cutobtained via the surrogate analysis. Building on this, we develop apolynomial-time separation procedure that successfully generates anS-K cut that renders a given non-integer extreme point infeasible. Weshow how sequential lifting processes can be viewed in our framework,and demonstrate that our approach can obtain facets that are notavailable to standard lifting methods. We also provide a relatedanalysis for generating fast cuts. Finally, we presentcomputational results of the new S-K cuts for solving 0-1 integerprogramming problems. Our outcomes disclose that the new cuts arecapable of reducing the duality gap between optimal continuous andinteger feasible solutions more effectively than standard liftedcover inequalities, as used in modern codes such as the CPLEX mixed0-1 integer programming solver.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

Stability for the functional equation of cubic type

In this article, we establish the stability of the orthogonally cubic type functional equation (1.2) for all x₁,x₂,x₃ with xi⊥xj(i,j=1,2,3), where ⊥ is the orthogonality in the sense of Rätz, and investigate the stability of the n-dimensional cubic type functional equation (1.3), where n?3 is an integer.     

A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates

In this paper we consider the scheduling problem of minimizing the weighted number of late jobs on a single machine (1|_rj|∑_wjUj)$\left(1|r_j|\sum w_j{U}_j\right)$. A branch-and-check algorithm is proposed, where a relaxed integer programming formulation is solved by branch-and-bound and infeasible solutions are cut off using infeasibility cuts. We suggest two ways to generate cuts. First, tightened “no-good” cuts are derived using a modification of the algorithm by Carlier (1982, EJOR, v.11, 42–47) which was developed for the problem of minimizing maximum lateness on a single machine. Secondly we show how to create cuts by using constraint propagation. The proposed algorithm is implemented in the Mosel modelling and optimization language. Computational experiments on instances with up to 140 jobs are reported. A comparison is presented with the exact approach of Péridy at al. (2003, EJOR, v.148, 591–603).     

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.     

The split closure of a strictly convex body

The Chvátal-Gomory closure and the split closure of a rational polyhedron are rational polyhedra. It has been recently shown that the Chvátal-Gomory closure of a strictly convex body is also a rational polytope. In this note, we show that the split closure of a strictly convex body is defined by a finite number of split disjunctions, but is not necessarily polyhedral. We also give a closed form expression in the original variable space of a split cut for full-dimensional ellipsoids.