Pierre Bonami, LIF, Marseille

Projected Formulations for Non-Convex Quadratically Constrained Programs

Abstract: A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher dimensional space by introducing one variable to represent each of the products of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can be efficiently strengthened by using SDP constraint and disjunctive programming. On the other hand, their main drawback is their huge size, even for problems of moderate size. In this paper, we study projection methods to build low-dimensional relaxations of MIQCP that capture the strength of the extended formulations.

For a copy of the slides for this presentation, click here.

Joint work with Anureet Saxena and Jon Lee.

Sonia Cafieri, LIX, Ecole Polytechnique

Convex Relaxations for Quadrilinear Terms

Branch and Bound based global optimization methods, applied to formulations involving multivariate polynomials, rely on convex envelopes for the lower bound computation. Convex/concave envelopes in explicit form currently exist for concave/convex univariate functions, bilinear terms, trilinear terms, univariate monomials of odd degree and fractional terms. The multivariate monomial of smallest degree for which the convex envelope is not known is the quartic one.

We present four different ways to compute a convex linear relaxation of a quadrilinear monomial on a box and analyze their relative tightness. We also apply the results to derive good convex relaxations for some instances of the Molecular Distance Geometry Problem and the Hartree-Fock Problem.

For a copy of the slides for this presentation, click here.

Joint work with Jon Lee and Leo Liberti.

Claudia D'Ambrosio, University of Bologna

A Feasibility Pump Heuristic for Non-Convex MINLPs

We propose an heuristic algorithm aimed at finding feasible solutions for non-convex Mixed Integer Non-Linear Programming problems. The proposed algorithm generalizes Feasibility Pump heuristics, previously proposed for MILPs and convex MINLPs. Existing heuristic algorithms for non-convex MINLPs are, for example, Variable Neighborhood Search and Local Branching, but this field is still highly unexplored. We explain how the presence of non-convex constraints complicates the problem and makes algorithms for convex MINLP in general not suitable for non-convex MINLPs. In particular we focus on how to deal with the issues of non-valid Outer Approximation cuts and of locally optimal solutions of the continuous relaxation. Then we propose different approaches to overcome these difficulties and present computational results on MINLPLib instances, showing good performances of such a general algorithm.

For a copy of the slides for this presentation, click here.

Joint work with Antonio Frangioni, Leo Liberti, and Andrea Lodi.

Sarah Drewes, TU Darmstadt

Mixed Integer Second Order Cone Programming

We present two algorithms to solve mixed integer second-order cone programming problems: a nonlinear branch-and-cut method and a branch-and-bound based outer approximation approach. The latter is an extension of the branch-and-bound based outer approximation approach for continuously differentiable problems to subdifferentiable constraint functions. Convergence can be guaranteed, since subgradients that satisfy the KKT conditions, can be identified using the dual solutions of the occurring second order cone problems. The impact of different techniques for the generation of linear and convex quadratic cuts in the context of both algorithms is investigated. Computational results for test problems and real world applications are given.

For a copy of the slides for this presentation, click here.

Joint work with Stefan Ulbrich.

Pierre Hansen, HEC Montréal and LIX, Ecole Polytechnique

An Improved Column Generation Algorithm for Minimum Sum-of-Squares Clustering

For a copy of the slides for this presentation, click here.

Joint work with Daniel Aloise and Leo Liberti.

Leo Liberti, LIX, Ecole Polytechnique

Mathematical Programming is Turing-complete

We define mathematical programming (MP) as a formal language. We then show a MP formulation (of the MINLP class) whose parameters encode the input of a Minsky's Register Machine (MRM) and whose set of solutions is the output of the MRM. Since the MRM is Turing-equivalent to a Universal Turing Machine (UTM), MP is Turing-complete. We show a few interesting applications deriving from treating MP as a formal language.

For a copy of the slides for this presentation, click here.

Jeff Linderoth, University of Wisconsin-Madison

Inequalities from Strong Branching Information for Mixed Integer Nonlinear Programs

Strong Branching is an effective branching technique that can significantly reduce the size of branch-and-bound tree for Mixed Integer Nonlinear Programs (MINLP)s. We will demonstrate how to effectively use "discarded" information from strong branching to create disjunctive cutting planes in a linearization-based solver for convex MINLPs. Computational results reveal that the tree size can be effectively reduced using these inequalities.

For a copy of the slides for this presentation, click here.

Joint work with Mustafa Kilinc, James Luedtke, and Andrew Miller.

Andrea Lodi, University of Bologna

Quadratic {-1,0,1} Optimization

We present a fast branch-and-bound algorithm for the minimization of a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of some variables, a simple lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by considering certain lattice-free ellipsoids that are centered in the continuous minimum and determined by a reduced lattice basis. Inside these ellipsoids, we compute the maximal scaling factor of the ellipsoid that is given by the quadratic objective function. This yields an improved lower bound for each considered ellipsoid. The main reason for the high performance of our algorithm in practice is that all expensive calculations can be done in a preprocessing phase, while the running time for a single node in the enumeration tree is at most quadratic in the problem dimension. Experiments show that our approach is fast on both unconstrained problems and problems with box constraints. However, it can handle arbitrary convex constraints by defining the pruning in an appropriate way.

For a copy of the slides for this presentation, click here.

Joint work with Christoph Buchheim and Alberto Caprara.

James Luedtke, University of Wisconsin-Madison

Generating Improved Relaxations for Global Optimization with Multilinear Terms

Multilinear functions appear in many global optimization problem. A common technique for creating relaxations of such terms is to decompose them into bilinear terms and then use a relaxation (the McCormick envelope) for each term separately. We study an approach which generates a relaxation directly from the multilinear term and show via numerical examples that in some cases this can lead to a tighter relaxation than the decomposition approach. We will discuss potential advantages and challenges of using this approach within a global optimization solver.

For a copy of the slides of this presentation click here.

Joint work with Mahdi Namazifar and Jeff Linderoth.

Philippe Meurdesoif, RealOpt, Université Bordeaux 1

'Rounding procedures in Semidefinite Programming'

This presentation provides a survey of results on the use of rounding to obtain integer solutions for semidefinite programs. Features of the best known methods will be highlighted, along with problem characteristics that create difficulties for all known procedures. Thus, this presentation also points out problem classes in which research in how to generate integer feasible solutions is crucially needed.

For a copy of the slides of this presentation click here.

Giacomo Nannicini, LIX, Ecole Polytechnique

'A Local Branching Heuristic for MINLPs'

Local branching is an improvement heuristic, developed within the context of branch-and-bound algorithms for MILPs, which has proved to be very effective in practice. For the binary case, it is based on defining a neighbourhood of the current incumbent solution by allowing only a few binary variables to flip their value, through the addition of a local branching constraint. The neighbourhood is then explored with a branch-and-bound solver. We propose a local branching scheme for (nonconvex) MINLPs which is based on iteratively solving MILPs and NLPs. Preliminary computational experiments within the open source solver Couenne show that this approach is able to improve the incumbent solution on the majority of the test instances, requiring only a very short CPU time.

For a copy of the slides of this presentation click here.

Joint work with Pietro Belotti and Leo Liberti.

Stefan Vigerske, Humboldt-Universität zu Berlin

Extending SCIP for Solving Mixed-Integer Nonlinear Programs

We discuss recent efforts in extending the constraint integer programming framework SCIP for the handling of nonlinear constraints in an LP-based branch-and-cut algorithm. For quadratic constraints, a polyhedral outer-approximation is built by using McCormick underestimators. For nonquadratic nonconvex constraints, we construct a quadratic approximation. Preliminary numerical experiments are presented.

For a copy of the slides of this presentation click here.

Page last modified by May 05, 2005, at 04:34 PM