**Shabbir Ahmed**

Polyhedral stochastic integer programming

We present polyhedral results for scenario based models of some stochastic
integer programs. The key idea is to combine valid inequalities from
scenario subproblems to derive new inequalities for the overall problem.
We illustrate the procedure by developing inequalities for the stochastic
uncapacitated lot-sizing problem and some other stochastic integer
programs.

Based on joint work with George L. Nemhauser, Yongpei Guan, Andrew Miller, and Jim Luedtke

**Alper Atamturk**

On connections between mixed-integer rounding and superadditive lifting

PDF

Mixed-integer rounding and superadditive lifting are two common ways for generating valid inequalities for mixed-integer programming. Mixed-integer rounding is a prescriptive approach that consists of simple disjunction and rounding rules. On the other hand, superadditive lifting is descriptive in the sense that it requires the characterization of superadditive lifting functions. Proving validity of an inequality is easier with mixed-integer rounding, whereas proving the strength of an inequality is easier with superadditive lifting. It is well-known that mixed-integer rounding is a special case of superadditive lifting and in several cases mixed-integer rounding leads to strong valid inequalities.

In this talk we will explore the connections between mixed-integer
rounding and superadditive lifting. We will give techniques that
generalize mixed-integer rounding as well as two-step mixed-integer
rounding. These simple prescriptive techniques lead to strong
superadditive lifting inequalities that are difficult to describe
explicitly.

(joint work with Oktay Gunluk)

**Pierre Bonami**

An hybrid branch-and-cut for solving MINLPs

PDF

We present some recent work related to developing Bon-min, an open-source solver for MINLP (Mixed Integer NonLinear Programming). Bon-min implements several exact algorithms for solving MINLPs which exhibits a convex continuous relaxation : a branch-and-bound, an outer-approximation decomposition and an hybrid branch-and-cut algorithm.

We focus here on presenting the hybrid algorithm. This algorithm
is a flexible branch-and-cut where linear and nonlinear continuous
relaxations are solved alternatively at the nodes of the tree search. The
linear relaxation is obtained by considering an outer approximation of
the nonlinear constraints of the problem and solving nonlinear programs
allows us to improve this approximation. The interest of using linear
relaxations is that they can be solved much faster than nonlinear
continuous relaxations and the goal of the algorithm is to build a
good enough outer approximation while not solving too many nonlinear
programs. In its extreme settings this algorithm can be made similar
either to a branch-and-bound based only on non-linear programming,
or to an outer-approximation decomposition algorithm.
This algorithm is compared to classical algorithms (as implemented both
in commercial solvers and in Bon-min) on a new publicly available library
of convex mixed integer nonlinear program which we have put together.

(This work is part of an ongoing project funded by IBM and conducted
both at Carnegie Mellon University and IBM to study novel algorithmic
approaches for solving MINLPs.)

**Alberto Caprara**

On solving combinatorial optimization problems without known decent ILP formulations

We illustrate our experience on some NP-hard combinatorial optimization problems that share the following characteristics: (1) they arise in real-world applications, (2) they are very simple to state, (3) they do not seem to admit any decent ILP formulation, i.e., all the formulations that were tried do not allow the solution of toy instances by modern, general-purpose ILP solvers. Focusing attention on the optimal solution of (real-world) medium-size instances, we briefly illustrate what could be achieved for each of these problems, ranging from basically nothing to effective solution by strong ILP formulations of suitable relaxations, which are defined after a careful analysis of the combinatorial structure of the problem.

**Sebastian Ceria**

Robust Portfolio Construction

PDF PPT

In this talk, we will describe how modern optimization techniques can help overcome important issues that "traditional" mean-variance optimizers face in practical portfolio management when dealing with Model and Estimation Error. In particular, we will discuss Robust Optimization, an optimization framework that considers errors in the input parameters directly and explicitly in the optimization problem itself, by considering a worse-case scenario for all uncertain parameters. We will introduce a new variant of Robust Optimization, called Robust Mean-Variance Optimization, that considers error in expected returns as well as risk parameters. We will demonstrate how Robust Mean Variance Optimization can be used to significantly reduce the error-maximization property found in classical mean-variance optimizers. We show how the portfolios generated through Robust Mean Variance are also more stable and intuitive. We will present a series of computational experiments to demonstrate the significant economic benefits of investing in portfolios computed using Robust Mean Variance Optimization.

**Sanjeeb Dash**

Separating from the MIR closure of
polyhedra

PDF PS

We study the problem of separating an arbitrary point from the MIR
closure of a polyhedron (finding violated rank-1 MIR cuts). Motivated
by the work of Fischetti and Lodi (2005), who gave an MIP model for
separating from the Chvatal closure of a polyhedron, we describe an
MIP model for separating from the MIR closure of a polyhedron. Our
analysis yields a short proof of the result of Cook, Kannan and
Schrijver (1990) that the split closure of a polyhedron is again a
polyhedron. We present computational results on finding violated MIR
cuts using this model.

Coauthors: Oktay Gunluk and Andrea Lodi.

**Milind Dawande**

Computing Forecast Horizons: An
Integer Programming Approach

PDF PPT

The concept of a forecast horizon has been widely studied in the Operations Research/Management literature in the context of evaluating the impact of future conditions on current decisions in a multi-period decision making environment. While the forecast horizon literature is extensive, the use of integer programming to analyze and compute forecast horizons has been limited. The recent significant developments in computational integer programming coupled with the modelling and structural simplicity of the integer programming approach make for a strong case for its use in computing forecast horizons. We first demonstrate the viability of the integer programming approach for computing classical forecast horizons. We then present structural and computational investigations of a new class of weak forecast horizons -- minimal forecast horizons under the assumption that future demands are integer multiples of a given positive real number. Throughout the discussion, we will use the dynamic lot-size problem to illustrate the ideas.

**Jesus De Loera**

Recent Progress in the Test Set method for Integer Programming

PDF

A test set for a family of integer programs is a finite collection of integral vectors with the property that every feasible non-optimal solution of any integer program in the family can be improved by adding a vector in the test set. There has been considerable activity in the area of test sets and primal methods (e.g. Graver and Gr\obner bases, the integral basis method, etc.). In the past, test sets were considered problematic due to their large entry size or their difficulty of computation. Here we report on fresh progress, made in the past year, that yields interesting algorithmic results and addresse some of the problems:

1) In joint work with Shmuel Onn we created polynomial-time algorithm to canonically rewrite any polyhedral system $\{x : Ax=b, \ x \geq 0\}$ as a face of a $m \times n \times k$ axial transportation polytope. Axial transportation polytopes are very special. For instance, one can decide whether they are empty or not in only linear time without relying on linear programming algorithms. Using one explicitly known Grobner basis for axial transportation problems we propose a new combinatorial, constant-memory algorithm for testing integer feasibility of polyhedra.

We present a new kind of linear integer programs of variable dimension, but constructed from a fixed block matrix, that admit a polynomial time solution. Interestingly enough we employed in the proof algebraic techniques such as Graver test sets and the equivalence of augmentation and optimization oracles. We discuss several applications of our algorithm to multiway transportation problems and to packing problems. One important consequence of our results is a polynomial time algorithm for the d-dimensional integer transportation problem for long multiway tables. Another interesting application is a new algorithm for the classical cutting stock problem. This is joint work with R. Hemmecke, S. Onn, and R. Weismantel.

**Matteo Fischetti**

MIP models for MIP separation

PDF

In this talk we show how the separation problem for some general classes of MIP inequalities can be modeled itself as a MIP, and discuss possible ways to use this approach in practice.

**Illya Hicks**

Branchwidth via Integer Programming

PDF PPT

Branch decompositions were first introduced by Robertson and Seymour in
their proof of the Graph Minors Theorem. In addition, dynamic
programming algorithms utilizing branch decompositions have recently
been proposed for addressing difficult problems in combinatorial
optimization problems modeled on graphs. The efficacy of these
algorithms depends on obtaining a branch decomposition of the input
graph with the smallest width possible. However, determining the
smallest width (i.e., the branchwidth) of a graph is NP-hard. This talk
offers a brief overview of research in branch decompositions and focuses
on an integer programming methodology for establishing the branchwidth
of a graph.

Coauthors: Elif Kolotoglu and Cole Smith.

**Brady Hunsaker**

Evaluating progress of branch-and-bound trees

PDF

We consider methods of evaluating the progress of branch-and-bound
algorithms by analyzing the data available about the branch-and-bound
tree. Our goal is to provide users with more useful information about
the progress of the algorithm than traditional measures such as the
optimality gap and number of active nodes. We use two open-source
codes, CBC and GLPK, and study tree development for a number of
instances from the MIPLIB library. We present visualization tools to
help make sense of the data and to guide intuition for further
research.

Coauthor: Osman Ozaltin

**Matthias Koeppe**

Intermediate Integer Programming Representations Using Value Disjunctions

PDF

We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one ``linking polyhedron'' per block and the ``aggregated polyhedron''. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables. Based on this theory, we propose a new branching scheme that analyzes the problem structure. It is designed to be applied in those subproblems of hard integer programs where LP-based techniques do not provide good branching decisions. Preliminary computational experiments show that it is successful for some benchmark problems of multi-knapsack type. Coauthors: Quentin Louveaux and Robert Weismantel

**Arie Koster**

Treewidth and Integer Programming

PDF PPT

For combinatorial optimization problems that turn out to be extremely difficult for integer programming techniques (for example frequency assignment), one has to search for alternative algorithms in order to find an optimal solution. If the problem is defined on a graph, a dynamic programming algorithm along a tree decomposition or branch decomposition of the graph could be a possibility. For many NP-hard optimization problems, there exist such algorithms that run in polynomial time, except for the width of tree/branch decomposition. The minimum width over all possible tree decompositions of a graph is called the treewidth of the graph. Hence, for graphs of bounded treewidth, such algorithms are polynomial. In this talk, we give an update on the efforts to exploit the notion of treewidth for solving combinatorial optimization problems. We in particular discuss algorithms to determine the treewidth of graphs; among them an integer programming formulation. Some new computational results for the minimum interference frequency assignment problem conclude the talk.

**Laci Ladanyi**

Decomposition and Mixed Integer Programs

PDF

MIPs with a constraint matrix that is mostly block diagonal with relatively few connecting constraints (resp. variables) can be solved via Dantzig-Wolfe (resp. Benders) decoposition. In this talk we explore how decomposition can be applied to MIPs when *both* connecting constraints and variables are present besides the block diagonal core. We introduce a true branch-cut-price algorithm that, due to its massively parallizable nature, has the potential to reach and prove optimality faster (in wall clock time) than any branch-and-cut based method. Preliminary computational results will be presented.

**Giuseppe Lancia**

Mathematical Programming Approaches in
Computational Biology

PDF

Computational Biology has emerged in the past years as an established new branch of Computer Science, bordering with Combinatorial Optimization, Statistics, Applied Mathematics and, of course, Molecular Biology. The field has provided researchers with a whealm of new exciting problems to work on. Of much interest to us, it provides "mathematical programming people" with a large set of optimization problems on which they can try their standard techniques. The use of O.R. techniques for Computational Biology problems has steadly increased in the last few years. In this seminar we will survey some of the problems on which these techniques have proved successful, and outline directions for future research on challenging problems. In particular, we will mention alignment problems (for both sequences and protein structures), genome rearrangements, protein folding, and, more in detail, the recent research area of polymorphism haplotyping. Time permitting, we will also describe some problems where optimization can still play a major role, such as microarray data analysis, virus barcoding, primer design.

**Jon Lee**

An MINLP solution method for a
water-network optimization problem

PDF (Paper)

We discuss a formulation and solution method for a water-network
design problem using mixed-integer nonlinear programming (MINLP). The
problem is to decide on the diameters of the pipes, chosen from a
discrete set of available pipes, to support demand at the network
junctions. A primary source of nonnliearity is related to the
Hazen-Williams friction loss equation. By paying careful attention to
the modeling and using available MINLP software, we are able to find
very good solutions to problem instances from the literature as well
as some real-world data.

Coauthors: Claudia D'Ambrosio, Cristiana Bragalli, Andrea Lodi, Paolo
Toth

**Alex Martin**

Branching Rules Revisited

PDF

We present a new generalization called reliability branching of today's state-of-the-art strong and pseudo-cost branching strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of the proposed new strategy. If time permits we also give some generalizations and new applications of SOS branching.

**Lisa Miller**

Valid inequalities for MIPs and group polyhedra from approximate liftings

PDF

We present an approximate lifting scheme to derive valid inequalities for
general mixed integer programs and for the group problem. This scheme uses
superadditive functions as the building block of integer and continuous
lifting procedures. It yields an alternate simple derivation of new as
well as known families of cuts that correspond to faces of the group
polyhedron. Furthermore, it can be used to obtain new families of two-,
three- and four-slope facet-defining inequalities for the master cyclic
group problem. This lifting approach is simple and constructive. We
highlight its potential computational advantages.

This is joint work with Jean-Philippe Richard and Yanjun Li.

**Ted Ralphs**

Biobjective Mixed Integer Programming

PDF

Multiobjective mathematical programs arise naturally in applications where an analysis of the tradeoff between multiple competing objectives is required. In the first part of this talk, we review the basic principles surrounding the analysis of biobjective mixed-integer programs. We then discuss several related methods for enumerating the Pareto outcomes of a biobjective mixed-integer program and present details of their implementation within the SYMPHONY MILP solver framework. Finally, we compare the performance of these methods on several applications and discuss the performance of a parallel implementation developed using the MW framework.

**Jean-Philippe P Richard**

MIP Lifting Techniques for Mixed Integer
Nonlinear Programs

PDF PPT

Lifting locally valid inequalities to make them globally valid is a
successful methodology for obtaining cuts in MILPs. We show how to
extend the approach to generate both linear and nonlinear cuts for
MINLPs. We illustrate the approach in two different ways. First, we
obtain cuts for mixed integer bilinear sets without adding
variables. These cuts are obtained through lifting from a
generalization of the concept of a cover and can not be obtained from
any single-row relaxation of the IP reformulation of the nonlinear
set. Second, we show how to obtain the nonlinear convex hull of
various disjunctive nonlinear sets through lifting.

Coauthor: Mohit Tawarmalani

**Tallys Yunes**

An Integrated Solver for Optimization Problems

PDF

One of the central trends in the optimization community over the past several years has been the steady improvement of general-purpose solvers. A logical next step in this evolution is to combine mixed integer linear programming, global optimization, and constraint programming in a single system. Recent research in the area of integrated problem solving suggests that the right combination of different technologies can simplify modeling and speed up computation substantially. In this talk we address this goal by presenting a general purpose solver that achieves low-level integration of solution techniques with a high-level modeling language. We validate our solver with computational experiments on problems in production planning, product configuration and job scheduling. Our results indicate that an integrated approach reduces modeling effort, while solving two of the three problem classes substantially faster than state-of-the-art commercial software.