Monday, July 22
9:45 – 10:30am: Tobias Achterberg, IBM CPLEX Optimization
Title: Probing, Probing, Probing, and Probing
Abstract:
We present four enhancements to the probing algorithm that have been added recently to CPLEX: cover probing, orbital probing, parallel probing, and delayed lifting.
11:00 – 11:30am: George L. Nemhauser, Georgia Institute of Technology
Title: Restrict-and-Relax Search for 0-1 Mixed Integer Programs*
Abstract:
A highly desirable characteristic of methods for solving 0-1 MIPs is that they should be capable of producing high quality solutions quickly. Restrict-and-relax search is a branch-and-bound algorithm that explores the solution space not only by fixing variables (restricting), but also by unfixing (relaxing), previously fixed variables. Starting from a restricted 0-1 MIP, the branch-and-bound algorithm can, at any node of the search tree, selectively relax and restrict variables using dual or structural information. This process yields a dynamic search that is likely to find high quality feasible solutions more quickly than a traditional search and that is also capable of proving optimality. A proof-of-concept computational study demonstrates its potential. An implementation in SYMPHONY, an open source solver for MIPS, is shown to generate high-quality solutions for many MIPLIB instances as well as for large-scale multicommodity fixed charge network flow instances much more quickly than SYMPHONY itself.
(Joint work with Menal Guzelsoy and Martin Savelsbergh)
11:30 – 12:00pm: Pietro Belotti, Clemson University
Title: Branch and bound for mixed integer biobjective optimization.
Abstract:
Solving a biobjective optimization problem consists of enumerating all of its Pareto-optimal solutions. In the continuous linear case, this can be obtained by applying the parametric simplex method. The problem is more difficult if a subset of variables is constrained to be integer. We describe a branch-and-bound algorithm for this type of problems. One of the main features of algorithm is a set of fathoming rules, which eliminate portions of the feasible set by proving that they contain no Pareto optimal solutions. We report on results obtained using a preliminary implementation of our biobjective branch-and-bound, which was written on top of a well-known commercial branch-and-bound library.
(Joint work with Banu Soylu and Margaret Wiecek)
2:00 – 2:30pm: John Hooker, Carnegie Mellon University
Title: MIP Modeling with Metaconstraints and Semantic Typing
Abstract:
Given the advanced state of MIP solvers, one might argue that a logical next step in MIP technology is communicating problem structure to the solver. This can be achieved by modeling with metaconstraints, which are high-level constraints that a pre-solve routine converts to a tight MIP formulation that exploits special structure. However, this process poses a fundamental problem of variable management. Conversion of different constraints often creates auxiliary variables in their MIP models that should be identified or otherwise related so as to obtain a tight overall relaxation. We discuss how this can be accomplished automatically by declaring semantic types for variables. The method applies equally well to an integrated solver in which constraint propagation and other techniques are combined with MIP.
(Joint work with Andre Cire and Tallys Yunes)
2:30 – 3:00pm: One-minute introductions of the posters by the poster presenters.
3:30 – 4:00pm: Mathieu Van Vyve, Catholic University of Louvain, BE
Title: Models and algorithms for the European day-ahead electricity market problem
Abstract:
The European day-ahead electricity market model is usually described as a linear or quadratic integer optimization problem with additional complementarity constraints expressing the existence of “equilibrium” market prices. We show how to eliminate the complementarity constraints from the formulation without introducing additional binary variables. This new formulation is based on a new combinatorial characterization of feasibility. In the linear case, using off-the-shelve MIP solvers on the new formulation is competitive with currently used algorithms. In the quadratic case, such a direct approach is not practical, and we derive a branch-and-cut algorithm derived from the new formulation.
4:00 – 4:30pm: Muhong Zhang, Arizona State University
Title: Valid Inequalities for Bilevel Integer Programs
Abstract:
Bilevel integer programs optimize hierarchical or conflict objective functions with integer variables. It has wide applications in economics, multi-stage decision making process, and game theories. In this talk, we analyze the valid inequalities for the feasible upper level optimal solutions with consideration of the second level solution and discuss corresponding branch and bound algorithms. Numerical experiments will be presented to compare different bounding strategies and computational efficiency.
4:30 – 5:00pm: One-minute introductions of the posters by the poster presenters.
5:00 – 7:30pm: Poster session and reception.
Tuesday, July 23
9:30 – 10:15am: Greg Blekherman, Georgia Institute of Technology
Title: Sums of Squares Relaxations on The Hypercube
Abstract:
The goal of the talk is to answer the following basic question: Given a quadratic function f nonnegative on the hypercube, in what degree does there exist a sum of squares certificate for nonnegativity of f? By sums of squares certificate I mean a sum of squares function h such that f (1+h) is a sum of squares on the hypercube. This certificate is different from the usual (Lasserre) sum of squares relaxation, which sets h=0 but our certificate is more general and still leads to semidefinite relaxations for finding a minimum of a quadratic function on the hypercube, which is relevant for combinatorial optimization problems.
(Joint work with Joao Gouveia and James Pfeiffer)
10:45 – 11:30am: Mohit Singh, Microsoft Research
Title: Computability of Maximum Entropy distributions and Counting Problems
Abstract:
Given a polytope P and a point x in the P, there can be many ways to write x as a convex combination of vertices of P. Interpreting any convex combination as a probability distribution over vertices of P, the distribution that maximizes entropy has received considerable interest. Interest in such distributions arises due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and, more recently, approximation algorithms. In this talk, I will discuss the computability of maximum entropy distributions. A key difficulty in computing max-entropy distributions has been to show that they have polynomially-sized descriptions. We show that such descriptions exist under general conditions. Subsequently, we show how algorithms for (approximately) counting the vertices of P can be translated into efficient algorithms to (approximately) compute maxentropy distributions. In the reverse direction, we show how access to algorithms that compute maxentropy distributions can be used to count, which establishes an equivalence between counting and computing max-entropy distributions.
(Joint work with Nisheeth Vishnoi)
11:30 – 12:00pm: Thomas Rothvoss, MIT
Title: Bin packing with a fixed number of item types
Abstract:
We consider a bin packing instance with item sizes s1,…,sd where we have bi many copies of item type i. It was an open question whether this problem admits a polynomial time algorithm for d=3. We solve this open question affirmatively (for all constants d).
(Joint work with Michel Goemans)
2:15 – 2:45pm: Daniel Dadush, New York University
Title: On the existence of 0/1 polytopes with high semidefinite extension complexity
Abstract:
In 2011, Rothvoß showed that there exists a 0/1 polytope such that any higher-dimensional polytope projecting to it must have a subexponential number of facets, i.e., its linear extension complexity is subexponential. The question as to whether there exists a 0/1 polytope having high PSD extension complexity was left open, i.e. is there a 0/1 polytope such that any spectrahedron projecting to it must be the intersection of a subexponential sized semidefinite cone and an affine space? We answer this question in the affirmative using a new technique to rescale semidefinite factorizations.
2:45 – 3:15pm: Sergei Chubanov, University of Siegen
Title: A projection algorithm for systems with implicit variables
Abstract:
In this talk we consider a projection algorithm for systems consisting of linear equations and nonnegativity constraints. To find a feasible solution, the algorithm constructs non-negative linear combinations of the columns of the coefficient matrix. At each iteration, an appropriate column is found by solving an optimization problem, i.e., by using a column generation technique.
3:45 – 4:30pm: Carla Michini, ETH Zurich
Title: On the diameter of lattice polytopes
Abstract:
We prove a bound on the diameter of lattice polytopes that improves on a previous result by Kleinschmidt and Onn. Our result implies a bound on the diameter of half-integral polytopes, and we prove that such bound is tight. This is a joint work with Alberto Del Pia.
4:30 – 5:00 pm: Business meeting
Wednesday, July 24
9:30 – 10:15am: Marco Di Summa, University of Padova
Title: Reverse split rank
Abstract:
Given a rational polyhedron Q, the split rank of Q is the number of times one has to apply the split closure operator in order to find the integer hull of Q, i.e., the integral polyhedron P defined as the convex hull of the integer points in Q. It is well known that this number is always finite. However, if we reverse our viewpoint, for a given integral polyhedron P, there might be no upper bound on the split rank of every rational polyhedron Q whose integer hull is P. In this talk we characterize those integral polyhedra P for which such an upper bound exists.
(Joint work with Michele Conforti, Alberto Del Pia, and Yuri Faenza)
10:45 -11:15am: Yuri Faenza, EPFL Lausanne
Title: On the convergence of the affine hull of the Chvátal-Gomory closures
Abstract:
Let Q be a full-dimensional polyhedron of Rn, and P be its non-full-dimensional integer hull. We investigate how many iterations of the Chvátal-Gomory procedure are needed to reduce Q into the affine hull of P. It is well-known that this can be upper bounded by a function of Q (for Q will always converge to P after a finite number of iterations), but can we upper bound it by a function f depending only on of P? It turns out that two different behaviors appear: if P has no integer point in its relative interior, then such an f does not exists. If conversely P has an integer point in its relative interior, then f does exist, and in fact it depends only on n. We also provide examples showing that f(n) must be doubly exponential. Joint work with Gennadiy Averkov, Michele Conforti, Alberto Del Pia, and Marco Di Summa.
11:15 – 12:00pm: Laurence Wolsey, Catholic University of Louvain
Title: On the Facets of Continuous Knapsack Constraints
Abstract:
Given a single constraint mixed integer program with n unbounded integer variables and m bounded continuous variables, our aim is to understand when all the nontrivial facets of the convex hull of solutions have 0-1 coefficients on the continuous variables. The special case with n = 1 is the single arc set studied by Magnanti et al., and the case with n = 2 and one unbounded continuous variable is treated by Agra and Constantino. We show that the number of distinct non-zero coefficients for the continuous variables is bounded above by 2n− n and that for n = 2 the bound is exactly one. Our main result is to show that when n = 2 the property holds and then to provide a complete description of the convex hull.
(Joint work with Oktay Gunluk and Sanjeeb Dash)
2:00 – 2:45pm: Quentin Louveaux, University of Liege
Title: Solving a mixed-integer program with power flow equations using Lagrangian relaxation
Abstract:
We consider a problem arising in power systems where a distribution network operator needs to decide on the activation of a set of load modulations in order to avoid congestion in its network. The problem can be modeled as a mixed-integer nonlinear program where the nonconvex nonlinearities come from the powerflow equations. We follow the approach of Phan by dualizing the power flow equations in order to tackle the nonlinearities. We report on some preliminary computational experiments.
(Joint work with Bertrand Cornélusse and Quentin Gemine)
2:45 – 3:15pm: Eduardo Moreno, Universidad Adolfo Ibañez
Title: Dealing with sample average approximated problems with a huge number of samples
Abstract:
Sample average approximation (SAA) techniques provide a methodology to deal with stochastic programming problems where the analytic solution cannot be found explicitly, by solving a sampled mixed-integer-programming model. This is the case of chance-constrained problem or two-stage problems with complicated (or even, unknown) probabilities. However, in many case we require a huge number of samples in order to well approximate the real underlying distributions, which in some cases is computationally intractable. Some examples of this are minimizing risk measure under heavy-tailed distributions, when the dimension of the probability space is too large, or a chance-constraint that must be satisfied with a near-one probability. In this talk, we discuss different techniques to deal with these problems. Particularly, we discuss the use of importance sampling techniques and scenario aggregation, which allow us to obtain good approximation of the real problem. We apply these techniques to solve
CVaR minimization problems and telecommunication network design problems with chance-constraints that need to be satisfied with a very high probability.
3:45 – 4:15pm: Bo Zeng, University of South Florida
Title: Two-stage robust optimization (RO): algorithms, formulations and implications.
Abstract:
In this talk, we present a study on two-stage robust mixed integer programs. We first describe a computing algorithm for a two-stage RO formulation, the column-and-constraint generation method. Then, a few non-traditional two-stage RO formulations will be presented, along with a discussion with respect to scenario-based stochastic programs. Finally, implications of the algorithm on solving typical multi-level optimization will be discussed and demonstrated.
4:15 – 5:00pm: Juan Pablo Vielma, MIT
Title: Cuts for Nonlinear MIP: Closed Form Expressions and Extended Formulations
Abstract:
One of the advantages of the Mixed Integer Rounding (MIR) cut for linear Mixed Integer Programming (MIP) is that it that it can be described through a simple closed form expression. In this talk we consider the possibility of constructing cuts with similar properties for (convex) nonlinear MIP. We show that for special structures we can derive closed form expressions for split cuts, cross cuts and other intersection cuts. In addition, through the use of nonlinear extended formulations we are able to relate back some of these cuts with the conic and original MIR cuts.
(Joint work with M. Kilinc and S. Modaresi)
Thursday, July 25
Time: 9:30 – 10:15am: Matthias Koeppe, University of California – Davis
Title: The Gomory-Johnson infinite group problem: A 42-year update
Abstract:
I present new results on the Gomory-Johnson infinite group problem, which appear in a series of papers with A. Basu and R. Hildebrand. The infinite group problem is an infinite-dimensional abstraction of mixed-integer linear programs for the purpose of deriving cutting planes. We present the first ever algorithm for testing the extremality of minimal valid functions for the infinite group problem on R1/Z1 that are piecewise linear (possibly discontinuous) with rational breakpoints. We also present an interesting function with irrational breakpoints, which requires a new type of extremality proof. We extend these results to all piecewise linear functions on a standard triangulation of R2/Z2. This generalizes results presented at IPCO 2013.
Time: 10:45 – 11:15am: Jim Ostrowski, University of Tennessee
Title: Dominance-strengthened symmetry breaking constraints in the unit commitment problem
Abstract:
Adding symmetry-breaking to a highly symmetric instance of a MILP problem can reduce the size of the problem’s feasible region considerably. The same can be said for good dominance constraints. In this talk we will examine the impact of using dominance arguments to strengthen symmetry breaking constraints for the Unit Commitment (UC) problem. Symmetry is present in (traditional formulations of) the UC problem when there are several generators of the same type. We show that by adding dominance strengthened cuts, the number of feasible solutions that need to be considered only grows polynomially as the number of generators increases (so long as the number of unique generators is fixed).
(Joint work with Jianhui Wang)
Time: 11:15 – 11:45am: Oktay Gunluk, IBM T.J. Watson Research
Title: Multi-branch split cuts
Abstract:
Split cuts are among the most important and well-understood cuts for general mixed-integer programs. We discuss some generalizations of split cuts, namely multi-branch split cuts. We compare the elementary closures of these cuts and cuts obtained from multi-row and basic relaxations. We also show that the closure of 2-branch split cuts (also known as cross cuts) is polyhedral.
(Joint work with Sanjeeb Dash, Marco Molinaro and Diego Moran)