Home
Organizers
Registration
Speakers
Program
Abstracts
Posters
Local Information
Sponsors
Contact Us
Recent Advances with the Reformulation-Linearization-Technique
The Reformulation-Linearization-Technique (RLT) is a general methodology for obtaining tight polyhedral outer-approximations of discrete sets. Given a mixed 0-1 linear (or polynomial) program, the RLT conducts two distinct steps of reformulation and linearization. During the reformulation step, "product factors" are formed from the binary variables and their complements. The original problem constraints are multiplied by these factors to generate additional, redundant restrictions. The linearization step then lifts the problem into a higher-dimensional space by substituting a continuous variable for each resulting product term.
Since its inception in the mid 1980's, the RLT has been successfully applied to a variety of problem types and structures. Notably, the underlying convex hull arguments rely on two key results. The first is the idempotent property that the square of a binary variable equals the binary variable itself. The second is that the problem constraints are polynomial in the decision variables, so that the reformulation step preserves polynomial expressions.
This talk addresses two recent RLT advances. First, we show that general discrete variables can be similarly handled by generalizing the "product factors" to Lagrange Interpolating Polynomials (LIPs). The LIPs allow for a reinterpretation of the idempotent property of binary variables, and thus a broadening of the entire RLT theory. Interestingly, RLT relaxations based on LIPs require more constraints and variables than with the binary case. We examine projection operations that reduce the numbers of variables.
The second advance extends the RLT to handle general mixed-discrete convex programs, where the constraints are no longer restricted to be polynomial in form. This is accomplished by first applying the RLT to an equivalent semi-infinite representation, and then translating back to a lifted convex relaxation.
Portions of this work were joint efforts with Hanif Sherali and Stephen Henry.
Higher dimensional split closures. (Presentation)
(Joint work with Q. Louveaux and R. Weismantel)Split cuts are cutting planes for mixed integer programs whose validity is derived from maximal lattice point free polyhedra of the form $S:=\{ x : \pi_0 \leq \pi^T x \leq \pi_0+1 \}$ called split sets. The set obtained by adding all split cuts is called the split closure, and the split closure is known to be a polyhedron. A split set has max-facet-width equal to one in the sense that $\max\{ \pi^T x : x \in S \}-\min\{ \pi^T x : x \in S \} \leq 1$ for all facets $\pi^T x \geq \pi_0$ of $S$.
In this talk we consider using general maximal lattice point free polyhedra to derive valid inequalities for mixed integer sets. We call maximal lattice point free polyhedra with max-facet-width equal to $w>0$ for split sets with rank $w$. A split cut of rank $w$ is then a valid inequality whose validity follows from a split set of rank at most $w$. The $w^{\textrm{th}}$ split closure is the set obtained by adding all valid inequalities of split rank at most $w$.
Our main result is that the $w^{\textrm{th}}$ split closure is a polyhedron. We also characterize which split rank $w^*$ is required to design a finite cutting plane proof for the validity of an inequality. Specifically, for this value $w^*$, there is a finite cutting plane proof that only uses split sets of split rank at most $w^*$, and no finite cutting plane proof that only uses split sets of rank smaller than $w^*$.
Two Submodular Optimization Problems On Risk Aversion. (Presentation)
Given a finite ground set N and two vectors a, b in R^N, we consider optimization problems involving a submodular utility function of the form u(S)= f(a(S))+b(S), where S is a subset of N, f is a strictly concave, increasing, differentiable function, and a(S), b(S) denote the sum of the components of a and b over S.
Both minimization and maximization of u arise frequently in modeling risk aversion in probabilistic combinatorial optimization problems. We will give applications for both types. Whereas minimization of u is solvable by a greedy algorithm, maximization of u is NP-hard.
Our goal in this talk is to present structural results that help us to formulate problems with such utility functions effectively so that they can be solved faster using standard mixed-integer programming solvers. We will present computational results on solving risk-averse capital budgeting problems.
This talk is based on the following recent papers:
Computational testing of exact mixed knapsack separation for MIP problems. (Presentation)
Pasquale Avella, DING, Università del Sannio Maurizio Boccia, DING, Università del Sannio Igor Vasilyev, Institute of System Dynamics and Control Theory, Siberian Branch of Russian Academy of Sciences We study an exact separation algorithm for mixed knapsack sets with the aim of evaluating its effectiveness in a cutting plane algorithm for Mixed-Integer Programming. First proposed by Boyd in the 90's, exact knapsack separation has recently found a renewed interest. We present a "lightweight" exact separation procedure for mixed knapsack sets and perform a computational experience on a wide set of mixed-integer programming instances from MIPLIB 2003 and "Mittleman" sets. Computational experiments confirm that MIR inequalities are the most important class of valid inequalities from a computational viewpoint. Nevertheless there are several difficult instances where exact separation is able to further raise lower bounds.Stronger Relaxations for Constrained Quadratic 0-1 Programming. (Presentation)
We consider quadratic 0-1 programs containing linear constraints. In practice, such problems are hard to solve even if the corresponding linear problem is easy, such as, e.g., the assignment problem. The straightforward approach is to linearize the quadratic objective function by introducing new variables and to simply add the given linear constraints; a slightly stronger relaxation can often be obtained by a quadratic reformulation of these constraints.
However, the performance of such an approach usually turns out to be poor, as the size of the problem increases considerably by the new variables and at the same time the standard linearization yields a very weak relaxation. In the talk, we present general methods for strengthening this relaxation.
Moreover, to illustrate the transition from a linear to a quadratic objective function, we discuss the quadratic linear ordering problem. In this example, we show that the polytope of the linearized quadratic problem is a face of the corresponding unconstrained quadratic 0-1 problem. In other words, in order to obtain a full description of the former polytope, it "suffices" to perfectly model the connection between basic and product variables, while most polyhedral knowledge about the linear problem is useless for the quadratic version.
Performance variability in mixed integer programming. (Presentation)
The solving time for a given MIP model sometimes varies dramatically if the branch-and-cut algorithm used to solve it is modified slightly, even if the algorithmic change is theoretically neutral with respect to performance. We will present evidence of this performance variability, examine its causes, describe its consequences, propose a few ideas to address it, and raise several related questions.
Computing with multi-row Gomory cuts. (Presentation)
Cutting planes for mixed integer problems (MIP) are nowadays an integral part of all general purpose software to solve MIP. The most prominent, and computationally significant, class of general cutting planes are Gomory mixed integer cuts (CG). Unfortunately, finding other classes of general cuts for MIP that work well in practice has been elusive.
Recent advances on the understanding of valid inequalities derived from the infinite relaxation introduced by Gomory and Johnson for mixed integer problems, has opened a new possibility of finding such an extension, and moreover, a simple geometrical interpretations for cuts derived from multiple tableau rows.
In this talk, we present some known results related to valid inequalities derived from the infinite group relaxation of groups of tableau rows, and investigate the computational impact of using several subclasses of minimal valid inequalities for this relaxation.
We also propose some new ground sets to generate inequalities, and possible ways to find custom-made ground sets for a given set of tableau rows. We test these ideas on a set of MIPs, including MIPLIB 3.0 and MIPLIB 2003.
Reformulations, Relaxations and Cutting Planes for Linear Generalized Disjunctive Programming. (Presentation)
Generalized disjunctive programming (GDP) is an extension of the well-known disjunctive programming paradigm developed by Balas. The GDP formulation involves Boolean and continuous variables that are specified in algebraic constraints, disjunctions and logic propositions, which is an alternative representation to the traditional mixed integer programming (MIP) formulation. Our research in this class of problems, which has been motivated by its potential for improved modeling and solution methods, has led to the development of customized algorithms that exploit the underlying logical structure of the problem in both the linear and nonlinear cases. However, an outstanding question that has remained is the exact relationship between GDP and disjunctive programming. In this work, we establish for the linear case connections between disjunctive programming and generalized disjunctive programming, which provide new theoretical and computational insights that allow us to exploit the rich theory developed Balas. In particular, we propose a novel family of MIP reformulations corresponding to the original GDP model that result in tighter relaxations and stronger cutting planes than reported in previous work. We illustrate this theory on the strip-packing problem for which computational results are presented. We also describe the application of these ideas to the global optimization of bilinear GDP problems.
This talk is based on the PhD work by Nick Sawaya and Juan Pablo Ruiz
Algorithms for Stochastic Lot-Sizing Problems with Backlogging. (Presentation)
As a traditional model in the operations research and management science domain, lot-sizing problem is embedded in many application problems such as production and inventory planning and has been consistently drawing attentions from researchers. There is significant research progress on polynomial time algorithm developments for deterministic uncapacitated lot-sizing problems based on Wagner-and-Whitin property. However, in practice, problem parameters are seldom known in advance. For most cases, even the distribution of the problem parameters is not known. In this talk we consider basic versions of deterministic lot-sizing models in which problem parameters (e.g., demand) are stochastic and develop corresponding scenario tree based stochastic lot-sizing models. For these models, a backward dynamic programming recursion framework is developed based on production path properties. This framework allows us to show that the optimal value function is piecewise linear and contin uous, which we can further use to define polynomial time algorithms for several different problems, including those with backlogging and varying capacities under certain scenario tree structure. Moreover, we develop polynomial time algorithms with complexities O(n^2) and O(n^2Tlog n) respectively for stochastic uncapacitated and constant capacitated lot-sizing problems, both with backlogging and regardless of scenario tree structure.
Mingling: Mixed-Integer Rounding with Bounds. (Presentation)
Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid inequalities for mixed-integer programs. When used as cutting planes, MIR inequalities are very effective for problems with unbounded integer variables. For problems with bounded integer variables, however, cutting planes based on lifting techniques appear to be more effective. This is not surprising as lifting techniques make explicit use of the bounds on variables, whereas the MIR procedure does not. In this paper we describe a simple procedure, which we call mingling, for incorporating variable bound information into mixed-integer rounding. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets with bounded variables. We show that facets of the mixed-integer knapsack sets derived earlier by superadditive lifting techniques are mingling inequalities. In particular, the mingling inequalities developed in this paper subsume the continuous cover and reverse continuous cover inequalities of Marchand and Wolsey as well as the continuous integer knapsack cover and pack inequalities of Atamturk. In addition, mingling inequalities give a generalization of the two-step MIR inequalities of Dash and Gunluk under some conditions.
Joint work with Alper Atamturk
A Principled Approach to MILP Modeling. (Presentation)
A problem can be formulated as an MILP if and only if the projection of its feasible set onto continuous space is a finite union of polyhedra with the same recession cone. This provides a general approach to MILP modeling, but it can lead to large or impractical formulations because it relies wholly on a disjunctive analysis. In this talk I present a alternative method for constructing MILP models that analyzes a problem in terms of disjunctive, knapsack, and logical constraints. I show by a series of examples that this approach generates, in a principled way, models that have come to be regarded through folklore or practical experience as "good" models for a wide variety of problems.
Seven Things Everyone Should Know about Gomory's Group Problem. (Presentation)
An Implementation of the Barvinok-Woods Integer Projection Algorithm. (Presentation)
We describe the first implementation of the Barvinok--Woods (2003) algorithm, which computes a short rational generating function for an integer projection of the set of integer points in a polytope in polynomial time, when the dimension is fixed. The projection algorithm is based on Kannan's partitioning lemma and the application of set operations to generating functions that correspond to these sets. We use a variant of the recent strengthening of the partitioning lemma due to Eisenbrand and Shmonin (2007) and provide several algorithmic refinements to avoid performing redundant set operations.
(Joint work with Sven Verdoolaege and Kevin Woods)
Cascade Knapsack Problems. (Presentation)
There are many ways to "engineer" difficult integer programs. Difficult knapsack problems that are provably hard for branch-and-bound have been proposed by Jeroslow in 1974, Chvatal and Todd, Chvatal and Avis in 1980, and later on by Cornuejols et al., Nemhauser et al., Hunsaker et al., and Aardal and Lenstra. Another notable class of hard IPs is the marketshare problems, proposed by Cornuejols and Dawande. These instances either are 1) theoretically hard for branch-and-bound, but easily solved by preprocessing; or 2) have large coefficients; or 3) have unbounded variables, or 4) have several constraints. We propose a family of 0-1 knapsack problems, in which one generates one node, when branching on a vector, say p1; after this, NO node, when branching on another vector, say p2. Thus, the right branching sequence has a "cascade" effect. The coefficients are of modest size, but the resulting instances seem comparably hard for commercial solvers as the marketshare problems. In a typical instance with n=30, the largest coefficient is 8933; and CPLEX 9.0 takes 56,937,604 nodes to prove infeasibility. The cascade problems illustrate another phenomenon studied by Cook and Kannan, namely the geometric width not being a good predictor of the integer width.
Joint work with Gabor Pataki at UNC Chapel Hill.
On Mixed-Integer Quadratic Programming with Box Constraints. (Presentation)
We consider a new, yet fundamental, non-linear mixed-integer programming problem, that we call Mixed-Integer Quadratic Programming with Box Constraints and denote by MIQPB. By this, we mean minimising a quadratic function of a set of variables, subject to lower and upper bounds on the variables, together with integrality constraints on a subset of the variables. (The objective function need not be convex or concave.) MIQPB includes as special cases two classical NP-hard problems: Unconstrained Boolean Quadratic Programming and Non-Convex Quadratic Programming with Box Constraints. As a result, one needs concepts from both combinatorial optimisation and global optimisation to tackle MIQPBs adequately.
We study the convex hull of feasible solutions to MIQPBs. (Note that they are not polyhedral unless all variables are integer-constrained.) We prove several results concerned with the structure of these convex sets and then present several classes of valid inequalities and facets. Our results generalise results of Yajima and Fujie and complement some recent results of Anstreicher and Burer.
Branch-and-Refine for Mixed Integer Nonconvex Optimization. (Presentation)
Authors: Sven Leyffer, Argonne Annick Sartenaer, University of Namur Emilie Wanufelle, University of NamurThe efficient management of energy is one of the most important challenges of this century. We consider an application arising in the efficient management of energy, namely the problem of optimal power flow. This problem is pivotal to the management of transmission systems. Especially, we focus on the tertiary voltage control (TVC) problem, whose aim it is to predict the effects of an expansion of the network, or to determine the optimal operating conditions of the existing network. This application gives rise to a nonconvex mixed-integer nonlinear programming (MINLP) problem.
Nonconvex MINLPs are among the most difficult optimization problem: they combine the difficulty of optimizing over discrete variable sets with the challenges of handling nonconvex functions. We propose a new global optimization method for solving nonconvex MINLPs. Our method decomposes the nonlinear functions into one- and two- dimensional components for which piecewise linear envelopes are constructed using ideas similar to special ordered sets. The resulting relaxation is then successively refined by branching on integer or continuous variables. We prove many interesting results, and present some preliminary numerical experience.
Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility. (Presentation)
Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert's Nullstellensatz certificates for polynomial systems arising in combinatorics and on large-scale linear-algebra computations over K. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph problem instances having thousands of nodes and tens of thousands of edges.
The talk is based on a paper of the same name with Jesus De Loera, Jon Lee and Susan Margulies, which is available on the arxiv at http://arxiv.org/abs/0801.3788
Strong Bounds for Linear Optimization Problems with k-of-m Constraint Systems. (Presentation)
By Ronald L. Rardin, Ph.D., University of Arkansas Ali Tuncel, Purdue University Mark Langer, M.D., Indiana School of Medicine Jean-Philippe P. Richard, Purdue UniversityOptimization problems arise in a variety of applications that would be linear programs except for one or more constraint systems in which up to a specified number k of the m constraints in the system are allowed to be violated. Our own work has focused on such systems in the context of "dose-volume limits" in radiation therapy planning wherein constraints correspond to implied dose at distinct points in some tissue, and the requirement is that at least a given percent of the points must satisfy a maximum dose restriction while other points may receive heavier doses. In finance, a similar structure exists in portfolio optimization problems where the constraints correspond to investment return under different scenarios and the requirement is to permit investments where no more than some specified percent of scenarios fall short of a specified return limit.
Such problems are NP-hard yet can easily be modeled as linear integer programs with 0-1 variables. However, such mixed-integer-programming models often exhibit massive gaps between optimal and LP-relaxation solution values. In this paper, we investigate families of cutting planes derived from viewing the underlying problem as a disjunctive program. In addition, we consider novel families of one-row-at-a-time restrictions of the given model that combine to produce a valid bound for the full problem. Motivations behind these ideas are explained, and computational results are provided.
How to solve challenging MIP problems faster.
We are often asked by our customers to solve MIP problems never before solved and to solve MIP problems that can be solved faster than ever. These two objectives, while seemingly unrelated, has led our development team to come up with a new way to meet both objectives and to put this power in the hands of the Xpress-MP User. This talk will focus on our new product, Xpress-Tuner, and how this tool allows Xpress-MP users to (i) automatically fine tune the Xpress-Optimizer to solve MIP problems that are unsolvable with any out-of-the box optimization software and to (ii) automatically tune the Xpress-Optimizer to solve MIP problems faster, frequently by a factor of 5 to 10 times.
Small Chvatal Rank. (Presentation)
We introduce a new measure of complexity of the integer hull of a rational polyhedron called its small Chvatal rank. While the Chvatal rank counts the number of rounds of cuts that need to be added to a polyhedron to obtain its integer hull, the small Chvatal rank is the number of iterations of a Hilbert basis procedure needed to obtain just the facet normals of the integer hull. In many situations, the small Chvatal rank is very small. For instance, in the plane, this rank is always at most one while Chvatal rank can be arbitrarily high. If G is a perfect graph on n vertices, the small Chvatal rank of the standard relaxation of the stable set polytope of G is at most two while the Chvatal rank is O(log n). We present bounds for polytopes in the unit cube and characterize the rank 0 case. In general, the two ranks have the same asymptotic growth.
Joint work with Tristram Bogart, Annie Raymond, Andreas Schulz and Sebastian Pokutta
Combinatorial Benders' Cuts for Sports Scheduling Optimization. (Presentation)
Combinatorial, or logical, Benders' cuts are a generalization of Benders' original linear programming dual based cuts, where information from the subproblem is passed back to the master problem in the form of cuts that embed the information "Any better (or feasible) solution must satisfy this constraint". Such cuts have proven particularly useful in sports scheduling due to the nested layers of decisions that must be made. An example of this nesting is the decision on the home versus away choice, followed by the decision of who to play compatible with that choice. We illustrate the use of combinatorial Benders' cuts in a variety of sports scheduling related applications, including a heuristic guided by Benders' cuts for umpire scheduling.
Mixed integer programming models for wind farm design. (Presentation)
Stuart Donovan, Gary Nates, Hamish Waterer, Rosalind ArcherThere is significant potential for optimizing the design of a wind farm in New Zealand. The complex nature of the wind resource and the larger size of the wind farms being built increase the complexity of the decisions that need to be made, while tight economic margins create a drive for greater efficiency. Current industry practice utilises commercial packages that are heuristic in nature and limited in the types of constraints that can be modelled.
A mixed integer programming model for optimizing the layout of a wind farm has been developed that is capable of determining the optimal locations of turbines subject to constraints on the number of turbines, turbine proximity, and turbine wake. Results have shown that this model produces layouts that are comparable to those from a commercial package. Moreover, this model can be extended to include capital budget constraints, noise and line of sight restrictions, constraints relating to wind quality such as maximum gusts, inflow angles and turbulence, as well as modelling reticulation and different mixes of turbines.
A generalization of the integer linear infeasibility problem
Does a given system of linear equations $Ax = b$ have a nonnegative integer solution? This is a fundamental question in many areas, such as operations research, number theory, and statistics. In terms of optimization, this is called an integer feasibility problem. A generalized integer feasibility problem is to find a finite representation of all $b$ such that there does not exist a nonnegative integral solution in the system with a given $A$. One such problem is the well-known Frobenius problem. In this paper we study the generalized integer feasibility problem and also the multi-dimensional Frobenius problem. To study a family of systems with no nonnegative integer solution, we focus on a commutative semigroup generated by a finite subset of $\Z^d$ and its saturation. An element in the difference of the semigroup and its saturation is called a ``hole''. We show the necessary and sufficient conditions for the finiteness of the set of holes. Also we define fundamental hol es and saturation points of a commutative semigroup. Then, we show the simultaneous finiteness of the set of holes, the set of non-saturation points, and the set of generators for saturation points. As examples we apply our results to some three- and four-way contingency tables and two-way contingency tables under the commen effect diagonal model from statistics. Then we will discuss the time complexities of our algorithms using generating functions.
This is joint work with A. Takemura.