Abstract and Talk Materials

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.