In order to solve MINLP problems to optimality, Branch&Bound algorithms typically apply disjunctions at the branching step, however the use of disjunctive cuts, i.e., valid inequalities based on disjunctions of the feasible set, proved to be effective in the Mixed-Integer Linear case and, recently, also in Mixed-Integer Quadratic Programming.

We discuss a straightforward extension of disjunctive cuts to a general MINLP solver and present some computational results to assess the use disjunctions in both the branching and the cutting plane steps.

Abstract: We describe continuing work on solving problems where the objective is convex while the feasible region is not, even though the actual variables used to model the problem are continuing. A classical example which is of importance is that of minimizing a convex quadratic, subject to linear inequalities and an upper bound on the number of nonzero variables -- a cardinality constraint on the support.

We describe approaches that rely on methodologies from constrained eigenvalue optimization problems. These approaches yield bounds frequently far stronger than those obtained through polyhedral mixed-integer programming methods, and scale very well problem size. If time allows, we will also describe branching approaches based on these techniques.

Gérard Conuéjols (Carnegie Mellon University, USA)

Abstract: In this talk we consider a semi-infinite relaxation of mixed integer linear programs. We show that minimal valid inequalities for this relaxation correspond to maximal lattice-free convex sets, and that they arise from nonnegative piecewise-linear positively homogeneous convex functions. The proof relies on an extension to linear subspaces of a theorem of Lovasz stating that a maximal lattice-free convex set in Rn is either an irrational hyperplane or a cylinder over a polytope. This work is joint with Valentin Borozan for the first result and with Amitabh Basu, Michele Conforti and Giacomo Zambelli for the generalization of Lovasz's theorem. 

Abstract:A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2008) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from maximal lattice-free triangles and quadrilaterals. These new families of inequalities can be used to generate valid cutting planes from any two rows of a simplex tableau.

Through a result by Cook et al. (1990) (and more recently in a generalization by Li and Richard (2008)) it is known that one particular class of facet-defining triangle inequality does not have a finite split rank, i.e., it cannot be obtained by repeated application of split cuts. In this talk, we show that all other facet-defining triangle and quadrilateral inequalities have a finite split-rank. The proof is constructive, i.e., for a given facet-defining triangle or quadrilateral inequality we present an explicit sequence of split inequalities that can be used to generate it.

(Joint work with Quentin Louveaux)

Ricardo Fukasawa (University of Waterloo and IBM Research, Canada/USA)

 
Thorsten Koch (ZIB, Germany)
LP/MIP/MINLP Challenges
Abstract: It is reported (e.g., by CPLEX developers) that linear programs can today be solved about 5 million times faster than 20 year ago. Are there still any difficult LPs left? What about integer programs? Here the reported speedup is even larger. But how do we measure progress? What are our benchmarks? Considering real world applications, can we really solve most of what is needed in industry? This talk will provide some answers and report, in particular, about new challenges arising in practice. 

(Joint work with Martin Grötschel)

(Joint work with Erick Moreno-Centeno)

N-step Mingling Inequalities and Their Facet-Defining Properties for Mixed Integer Knapsack Sets

Abstract: The n-step MIR inequalities (Kianfar and Fathi, 2008) are valid inequalities for the general mixed integer knapsack set, which are derived based on mixed integer rounding. An n-step MIR inequality can be generated by applying the corresponding n-step MIR function on the coefficients and right-hand side of the original inequality. The mingling inequalities (Atamturk and Gunluk, 2007) are also derived based on mixed integer rounding and incorporate bounds on integer variables. The mingling and 2-step mingling inequalities have been shown to be facet-defining in many cases. In this talk, we show that the ideas behind n-step MIR and mingling can be used together to generate what we call n-step mingling inequalities for general mixed integer knapsack sets. Furthermore, we show that the n-step mingling inequalities are facet-defining for these sets if certain conditions on coefficients are satisfied (the facet-defining conditions for mingling and 2-step mingling inequalities are special cases of these conditions). This makes n-step mingling a novel method for generating facets for the general mixed integer knapsack set, and presents new facets for this set. 

(Joint work with Alper Atamturk)

Jeff Linderoth (University of Wisconsin, Madison, USA)

Flexible Isomorphism Pruning
Abstract: Isomorphism Pruning is an effective technique for solving integer programs with many isomorphic solutions. Previous implementations of isomorphism pruning have had the limitation that the algorithm must use a restricted choice of branching variables during the branch-and-bound search. In this talk, we show how remove this limitation---modifying isomorphism pruning to allow for complete flexibility in the choice of branching variable. Computational results showing the benefit of this flexibility will be given.

(Joint work with Jim Ostrowski and Francois Margot)

Andrea Lodi (University of Bologna, Italy)
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.

(Joint work with Christoph Buchheim and Alberto Caprara)

Sanjay Mehrotra (Northwestern University, USA)
A Method for Rounding a Continuous Solution
Abstract: We will present a method for generating integer solutions from a continuous solution in integer programming. The method uses a simple ellipsoid to measure the distance of rounded solution to the continuous one, and progressively generates solutions whose feasibility is checked. It ensures that a feasible integer solution does not escape, should it be available within a specified distance. We will present computational performance of this method depending on the progress.

Vishnu Narayanan (IIT Bombay, India)
The Submodular Knapsack Polytope
Abstract: The submodular knapsack set is the discrete lower level set of a submodular function. The modular case reduces to the classical linear 0-1 knapsack set. One motivation for studying the submodular knapsack polytope is to address 0-1 programming problems with uncertain coefficients. Under various assumptions, a probabilistic constraint on 0-1 variables can be modeled as a submodular knapsack set. In this talk we describe cover inequalities for the submodular knapsack set and investigate their lifting problem. Each lifting problem is itself an optimization problem over a submodular knapsack set. We give sequence-independent upper and lower bounds on the valid lifting coefficients and show that whereas the upper bound can be computed in polynomial time, the lower bound problem is NP-hard. Furthermore, we present polynomial algorithms based on parametric linear programming and computational results for the conic quadratic 0-1 knapsack case.

(Joint work with Alper Atamturk)

George L. Nemhauser (Georgia Tech, USA)
Lifted Inequalities for 0-1 Mixed Integer Programs: A Computational Study
Abstract: We describe four families of strong inequalities for 0-1 mixed integer programming (MIP) problems. We first show how these inequalities can be applied to the simplex tableaux of the LP relaxations of 0-1 MIPs. We then show how these inequalities can be applied to the formulation of 0-1 MIPs and propose different separation algorithms. Finally we present the results of a computational study comparing the performance of these cuts.

(Joint work with Amar Narisetty and Jean-Philippe Richard)

Shmuel Onn (Technion, Israel)

N-Fold Integer Programming and Multicommodity Flows

Abstract: I will describe our recently developed theory of n-fold integer programming, which enables polynomial time solution of fundamental linear and nonlinear integer programming problems in variable dimension.

I will demonstrate the power of this theory by deriving a polynomial time algorithm for multicommodity flow problems where the cost of flow over a channel is a more realistic, nonlinear, function of the flow, accounting for channel congestion under heavy traffic or communication load.

We present a simple and efficient sum-of-squares based method for the formulation of convex relaxations for optimization problems. These relaxations are of importance in the context of branch-and-bound for nonconvex optimization. As opposed to term-based relaxations (e.g.,
McCormick's), the proposed method is based on barycentric Lagrange interpolation, requiring only pointwise evaluations of the function. The interpolation-based technique yields semidefinite programs that are numerically stable, well-conditioned, and with low-rank and sparsity properties, that can be exploited by current SDP solvers. The results are particularly attractive in the case of cubic splines, in which case the corresponding convex optimization problem reduces to a quadratically constrained quadratic program.

Anureet Saxena (Axioma Inc., USA)

Convex Relaxations of Non-Convex Mixed Integer 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 variables Yij to represent each of the products xi xj of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can be efficiently strengthened by using the (convex) SDP constraint Y - x xT \succeq 0 and disjunctive programming. On the other hand, their main drawback is their huge size, even for problems of moderate size. In this talk, we discuss methods to build low-dimensional relaxations of MIQCP that capture the strength of the extended formulations. To do so, we use projection techniques pioneered in the context of the lift-and-project methodology. We show how the extended formulation can be algorithmically projected to the original space by solving linear programs. Furthermore, we extend the technique to project the SDP relaxation by solving SDPs. In the case of an MIQCP with a single quadratic constraint, we propose a subgradient-based heuristic to efficiently solve these SDPs. We also propose a new "eigen reformulation" for MIQCP, and a cut generation technique to strengthen this reformulation using polarity. We present extensive computational results to illustrate the efficiency of the proposed techniques. Our computational results have two highlights. First, on the GLOBALLib instances, we are able to generate relaxations that are almost as strong as those proposed in our companion paper even though our computing times are about 100 times smaller, on average. Second, on the box QP instances, the strengthened relaxations generated by our code are almost as strong as the well-studied SDP+RLT relaxations and can be solved in less than 2 sec even for larger instances with 100 variables; the SDP+RLT relaxations of the same set of instances can take up to a couple of hours to solve using a state-of-the-art SDP solver. 

Algebraic Symmetry in Semidefinite Programs

Bernd Sturmfels (University of California, Berkeley, USA)
Convex Algebraic Geometry
Abstract: Convex algebraic geometry is an emerging field at the interface of convex optimization and algebraic geometry. A primary focus lies on the geometric underpinnings of semidefinite programming. This lecture offers a self-contained introduction, starting with elementary questions concerning multifocal ellipses in the plane, but also touching upon singularities and projections of spectrahedra.

Formulations and Algorithms for the Train Platforming Problem

Abstract: The objective of train platforming, which is the routing problem that generally follows any timetabling phase, is to find an assignment of trains to platforms in a railway station. The practical relevance of the problem inspired the definition of a few different versions, which are relatively easy to solve for small contexts, corresponding to stations with very few platforms and alternative paths to route the trains, but become extremely difficult when applied to complex railway station topologies such as those associated with the main European stations, leading to instances with hundreds of trains and tens of platforms. Moreover, most versions are not concerned with the station topology and ignore the routing phase, whereas the main European stations frequently have complex topologies and the routing issue can be quite a complicated task.

In this paper we study a general formulation of the train platforming problem, which contains as special cases all the versions previously considered in the literature, as well as a case study from Rete Ferroviaria Italiana, the Italian Infrastructure Manager. In particular, motivated by our case study, we consider a general quadratic objective function, and propose a new way to linearize it by using a small number of new variables along with a set of constraints that can be separated efficiently by solving an appropriate linear program. The resulting integer linear programming formulation has a continuous relaxation that leads to strong bounds on the optimal value. An effective heuristic algorithm driven by this relaxation is proposed. For the instances in our case study, the proposed approach produces solutions that often turn out to be (nearly-)optimal and that are much better than those produced by the simple heuristic method currently in use.

An SDP Relaxation for Sparse Max-Cut Problems

Abstract: We investigate semidefinite relaxations of the Max-Cut problem, which are formulated in terms of the edges of the graph, thereby exploiting the (potential) sparsity of the problem. We show how this is related to higher order liftings of Anjos and Wolkowicz and Lasserre. Contrary to the basic semidefinite relaxation, which is based on the nodes of the graph, the present formulation leads to a model which is significantly more difficult to solve.

To solve the resulting SDP we developed an algorithm where we factorize the matrix in the dual SDP and apply an augmented Lagrangian algorithm to the resulting minimization problem. We present computational results that indicate that this model is manageable for sparse graphs on a few hundred nodes and yields very tight bounds.

(Joint work with Veronica Piccialli and Franz Rendl)

Abstract: We consider the network loading problem under polyhedral demand uncertainty. Given an underlying network, a set of commodities, a demand polyhedron, and installation costs for equipment, we would like to select routes for commodities and install equipment on the edges of the network, at minimum cost, under the constraint that the network should be feasible for any demand vector from the demand polyhedron. We provide a mixed integer programming formulation for this problem. This formulation involves flow and capacity variables as in the case of the deterministic problem, as well as some dual variables which arise from the transformation used to incorporate robustness into the problem. 

These dual variables break the ties between flow and capacity variables in such a way that when we project out the flow variables, the projection inequalities are simple cut inequalities. Then we focus on a specific demand polyhedron description, called the hose model. Here the polyhedron is defined by nonnegativity of individual demands and upper bounds on the total demands adjacent at terminal nodes. We investigate the polyhedral properties of the associated convex hull and propose a branch and cut algorithm. We also present some preliminary results on a more restricted uncertainty description obtained by adding box constraints to the hose model. 

(Joint work with A. Altin and M.C. Pinar)