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.     

Anisotropic Analysis of Some Gaussian Models

Although the classical Fractional Brownian Motion is often used to describe porosity, it is not adapted to anisotropic situations. In the present work, we study a class of Gaussian fields with stationary increments and spectral density. They present asymptotic self-similarity properties and are good candidates to model a homogeneous anisotropic material, or its radiographic images. Unfortunately, the paths of all Gaussian fields with stationary increments have the same apparent regularity in all directions (except at most one). Hence we propose here a procedure to recover anisotropy from one realization: computing averages over all the hyperplanes which are orthogonal to a fixed direction, we get a process whose Hölder regularity depends explicitly on the asymptotic behavior of the spectral density in this direction.     

An algorithmic framework for convex mixed integer nonlinear programs

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.     

Truncations of multilinear Hankel operators

We extend to multilinear Hankel operators the fact that some truncations of bounded Hankel operators are still bounded. We prove and use a continuity property of bilinear Hilbert transforms on products of Lipschitz spaces and Hardy spaces.

     

A note on the MIR closure

In 1988, Nemhauser and Wolsey introduced the concept of MIR inequality for mixed integer linear programs. In 1998, Wolsey gave another definition of MIR inequalities. This note points out that the natural concepts of MIR closures derived from these two definitions are distinct. Dash, Günlük and Lodi made the same observation independently.     

Approximations in Sobolev spaces by prolate spheroidal wave functions

Recently, there is a growing interest in the spectral approximation by the Prolate Spheroidal Wave Functions (PSWFs) ${\psi }_{n,c},c>0$. This is due to the promising new contributions of these functions in various classical as well as emerging applications from Signal Processing, Geophysics, Numerical Analysis, etc. The PSWFs form a basis with remarkable properties not only for the space of band-limited functions with bandwidth c, but also for the Sobolev space $H^s([?1,1])$. The quality of the spectral approximation and the choice of the parameter c when approximating a function in $H^s([?1,1])$ by its truncated PSWFs series expansion, are the main issues. By considering a function $f\in H^s([?1,1])$ as the restriction to $[?1,1]$ of an almost time-limited and band-limited function, we try to give satisfactory answers to these two issues. Also, we illustrate the different results of this work by some numerical examples.