Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation

Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation–linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising.     

A recursive procedure to generate all cuts for 0–1 mixed integer programs

We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.The research of this author was supported by NSF Contract No. ECS-8540898.     

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.     

Bounded rank-1 transformations

We define the notion of canonical boundedness among rank-1 transformations and use it to characterize the class of bounded rank-1 transformations with trivial centralizer. We also explicitly characterize totally ergodic rank-1 transformations with bounded cutting parameter. Together with a recent result of Ryzhikov, our results provide a simple procedure for determining, purely in terms of the cutting and spacer parameters for the transformation, whether a bounded rank-1 transformation has minimal self-joinings of all orders.     

Separability of distinct Boolean rank-1 matrices

For two distinct rank-1 matricesA andB, a rank-1 matrixC is called aseparating matrix ofA andB if the rank ofA+C is 2 but the rank ofB+C is 1 or vice versa. In this case, rank-1 matricesA andB are said to beseparable. We show that every pair of distinct Boolean rank-1 matrices are separable.     

Automatic convexity of rank-1 convex functions

We announce new structural properties of 1-homogeneous rank-1 convex integrands, and discuss some of their consequences.     

Efficient similarity factorization of rank-1 modifications

For the solution of stiff ODEs by implicit methods one has to solve sequences of algebraic systems, whose Jacobian is the identity minus a multiple of the 'system' Jacobian of the right hand side. The latter can be successively approximated by a new 'two-sided rank-1' formula yielding only a moderate increase in the number of iterations compared to Newton's method. However, so far we have only been able to achieve the reduction in the linear algebra effort per integration step from O (n 3) to O (n 2) as long as the size is kept constant. To obtain an effort of O (n 2) seems to require an update of a similarity reduction of the system Jacobian to Hessenberg form or even a band matrix. As we have found no O (n 2) algorithms for updating such factorizations in literature, we discuss an idea to approximate the update with enough accuracy to ensure rapid convergence of the underlying implicit equation solver. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Cubic regularization in symmetric rank-1 quasi-Newton methods

Quasi-Newton methods based on the symmetric rank-one (SR1) update have been known to be fast and provide better approximations of the true Hessian than popular rank-two approaches, but these properties are guaranteed under certain conditions which frequently do not hold. Additionally, SR1 is plagued by the lack of guarantee of positive definiteness for the Hessian estimate. In this paper, we propose cubic regularization as a remedy to relax the conditions on the proofs of convergence for both speed and accuracy and to provide a positive definite approximation at each step. We show that the n-step convergence property for strictly convex quadratic programs is retained by the proposed approach. Extensive numerical results on unconstrained problems from the CUTEr test set are provided to demonstrate the computational efficiency and robustness of the approach.     

A deterministic algorithm for constructing multiple rank-1 lattices of near-optimal size

Advances in Computational Mathematics - We present a novel family of C1 quadrilateral finite elements, which define global C1 spaces over a general quadrilateral mesh with vertices of arbitrary...     

Additive rank-1 preservers between spaces of Hermitian matrices

Suppose ? is the real number field, ? is the complex number field, and m,n are integers with min?{m,n}≥2. Denote by S _n (?) (respectively, H _n (?)) the ?-linear space of all n×n real symmetric (respectively, complex Hermitian) matrices. We describe the structure of all additive rank-1 preservers from S _m (?) (respectively, H _m (?)) to H _n (?), and thereby, the general form of all additive rank preservers from S _m (?) (respectively, H _m (?)) to H _n (?) is determined.     

A unifying approach to heuristic search

We present the General Search Procedure (GSP) that provides a unifying way of describing search algorithms. The GSP captures both constructive and iterative search algorithms. We demonstrate as an exercise that various well-known heuristic search procedures can be obtained as instances of the GSP. The introduced formalism provides a solid ground to prove theoretical properties of search methods. Furthermore, by the formal approach we obtain a framework that can serve as the basis of implementing a search based problem solver.     

Subtracting a best rank-1 approximation may increase tensor rank

It has been shown that a best rank-R approximation of an order-k tensor may not exist when R?2 and k?3. This poses a serious problem to data analysts using tensor decompositions. It has been observed numerically that, generally, this issue cannot be solved by consecutively computing and subtracting best rank-1 approximations. The reason for this is that subtracting a best rank-1 approximation generally does not decrease tensor rank. In this paper, we provide a mathematical treatment of this property for real-valued 2×2×2 tensors, with symmetric tensors as a special case. Regardless of the symmetry, we show that for generic 2×2×2 tensors (which have rank 2 or 3), subtracting a best rank-1 approximation results in a tensor that has rank 3 and lies on the boundary between the rank-2 and rank-3 sets. Hence, for a typical tensor of rank 2, subtracting a best rank-1 approximation increases the tensor rank.     

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

 We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also maps bases of the higher-dimensional cut generating linear program (CGLP) into bases of the linear programming relaxation. It provides new bounds on the number of facets of the elementary closure, and on the rank, of the standard linear programming relaxation of the mixed 0-1 polyhedron with respect to the above families of cutting planes. Based on the above correspondence, we develop an algorithm that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional (LP) simplex tableau. In particular, we show how to calculate the reduced costs of the big tableau from the entries of the small tableau and based on this, how to identify a pivot in the small tableau that corresponds to one or several improving pivots in the big tableau. The overall effect is a much improved lift-and-project cut generating procedure, which can also be interpreted as an algorithm for a systematic improvement of mixed integer Gomory cuts from the small tableau. Received: October 5, 2000 / Accepted: March 19, 2002 Published online: September 5, 2002 Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

A simple heuristic approach to simplex efficiency

Consider the standard linear program:

$\text{Minimize}\text{cx}\text{subject to}\text{Ax=b, x?0}$

where A is an m × n matrix. The simplex algorithm solves this linear program by moving from an extreme point of the feasibility region to a better (in terms of the objective function cx) extreme point (via the pivot operation) until the optimal is reached. In order to obtain a feel for the number of necessary iterations, we consider a simple probabilistic (Markov chain) model as to how the algorithm moves along the extreme points. At first we suppose that if at any time the algorithm is at the jth best extreme point then after the next pivot the resulting extreme point is equally likely to be any of the j?1 best. Under this assumption, we show that the time to get from the Nth best to the best extreme point has approximately, for large N, a Poisson distribution with mean equal to the algorithm (base e) of N. We also consider a more general probabilistic model in which we drop the uniformity assumption and suppose that when at the jth best the next one is chosen probabilistically according to weights w_i, i = 1, …, j?1.     

A note on 1-cycles on the moduli space of rank-2 bundles over a curve

Over a smooth complex projective curve of genus ≥3, we study 1-cycles on the moduli space of rank-2 stable vector bundles with fixed determinant of degree 1. We show the first Chow group of the moduli space is isomorphic to the zeroth Chow group of the curve.     

A nonlinear model to generate the winner-take-all competition

This paper is concerned with the phenomenon of winner-take-all competition. In this paper, we propose a continuous-time dynamic model, which is described by an ordinary differential equation and is able to produce the winner-take-all competition by taking advantage of selective positive–negative feedback. The global convergence is proven analytically and the convergence rate is also discussed. Simulations are conducted in the static competition and the dynamic competition scenarios. Both theoretical and numerical results validate the effectiveness of the dynamic equation in describing the nonlinear phenomena of winner-take-all competition.     

A Gaussian smoothing algorithm to generate trend curves

A Gaussian smoothing algorithm obtained from a cascade of convolutions with a seven-point kernel is described. We prove that the change of local sums after applying our algorithm to sinusoidal signals is reduced to about two thirds of the change by the binomial coefficients. Hence, our seven point kernel is better than the binomial coefficients when trend curves are needed to be generated. We also prove that if our Gaussian convolution is applied to sinusoidal functions, the amplitude of higher frequencies reduces faster than the lower frequencies and hence that it is a low pass filter.