Research

Mixed Integer Optimization deals with mathematical optimization problems with two types of variables: variables taking values in an integer domain, and variables taking values in a continuous domain. The fact that Mixed Integer Optimization problems naturally appear in many contexts has led to an increased interest in the design of strong algorithms for different variants of the problem. Unfortunately, Mixed Integer Optimization problems are much less understood then their "non-mixed" counterparts, like Integer Programming or Linear/Convex Programming. This is not surprising, since to tackle Mixed Integer Optimization problems one has to overcome several new technical challenges that do not appear in the better studied non-mixed counterparts.

The design of strong algorithms for various Mixed Integer Programming problems, as well as their general study, is one of the main research thrusts at IFOR.

Mixed Integer Linear Optimization

Mixed Integer Linear Optimization problems, or MILPs, are optimization problems involving only linear functions and finitely many variables. There is a great variety of solution techniques, which can be mainly subdivided into primal and dual methods. A standard (dual) approach to solve an MILP is to apply cutting plane methods. Here, the underlying MILP is used to construct a sequence of linear optimization problems, that result from a successive addition of linear constraints, the so-called cutting planes, until the optimal solution of one of the linear optimization problems satisfies the integrality requirements. For many combinatorial problems, it is possible to deduce several families of cutting planes by exploiting the inherent combinatorial structure of the problem. Unfortunately, similar approaches seem illusive for general MILPs. The generation of cutting planes is normally based on the objective function and the given set of linear equations and inequalities. Most of the currently available cutting plane algorithms are based on geometric concepts. In order to generate strong cutting planes, one needs to understand the interplay between algebra and geometry. Promising classes of cutting planes are those based on so-called lattice-free polyhedra. The structure and algorithmic use of this type of cutting planes is a central research direction at IFOR to tackle MILPs.

Mixed Integer Convex Optimization

Whereas Mixed Integer Linear Optimization problems are the natural mixed integer counterparts of linear programs, Mixed Integer Convex Optimization problems, or MICPs, generalize convex problems to mixed integer domains. It is not surprising that solving MICPs is a difficult task in general. Already in the pure continuous case, i.e., classical convex optimization problems, can only be solved up to a certain accuracy. Furthermore, also in the pure integer case with constant dimension it is already a challenge to invent efficient algorithms. Classical Convex Optimization has some strong advantages compared to the mixed integer case: we have at our disposal necessary and sufficient optimality conditions, a powerful duality theory, and reliable algorithms for reasonably large subclasses of these problems. Among all the subclasses of Convex Optimization, Semidefinite Programming plays a distinguished role: virtually every field of engineering has found applications of Semidefinite Programming. Moreover, this class is particularly well-suited for Interior-Point Methods, a family of efficient algorithms for Convex Optimization. However, the intrinsic complexity of Interior-Point Method limits the size of the problems that they can handle. In the last years, new and cheaper approaches have been developed to attack much larger semidefinite problems. These algorithms, called First-Order Methods, are very sophisticated extensions of old Gradient Methods. Their scope of applicability and the impressive acceleration possibilities that they offer are not fully understood yet. Many development strategies can still be investigated to further improve them, to make them an indispensable tool to tackle huge-size semidefinite problems, or to leverage their versatility in the context of Mixed Integer Convex Optimization.

Below we list some ongoing projects at IFOR in this field.

Mixed integer convex minimization (T. Oertel, R. Weismantel)

The aim of this project is to develop efficient algorithms for mixed integer convex minimization problems in fixed dimension. For that, mixed integer linear optimization techniques are combined with algorithms from convex optimization. The approach that we have in mind uses cutting plane algorithms together with polytope shrinking techniques in order to generate deep cutting planes.

Mirror-Descent Methods (M. Baes, T. Oertel, R. Weismantel)

This project addresses the problem of minimizing a convex function over a convex set with the additional requirement that some variables must be integer. It is known that this problem is NP-hard, even when the function under consideration is piecewise linear. However, we are interested in algorithmic approaches to this problem, where the hardness is postponed to the realization of an oracle. If this oracle can be realized in polynomial time, then the problem itself can be solved in polynomial time as well. A natural question is whether this oracle can be implemented efficiently for problems with only two integer variables, and if so, how could such a subroutine be extended to solve general mixed integer convex problems. The first step in this project is the design of a finite-time algorithm for mixed integer convex optimization. In a second step, the focus should lie on the efficiency of the algorithm.

Minimizing Lipschitz-continuous strongly convex functions over integer points in polyhedra (M. Baes, R. Weismantel)

This project is concerned with the minimization of Lipschitz-continuous and strongly convex functions over integer points in polyhedral regions. Our results are related to the rate of convergence of a black box algorithm that iteratively solves special quadratic integer problems with a constant approximation factor. Despite the generality of the underlying problem, we prove that we can detect efficiently, with respect to our assumptions regarding the encoding of the problem, a feasible solution whose objective function value is close to the optimal value. We also show that this proximity result is the best possible up to a polynomial factor. Joint work with Y. Nesterov and S. Onn.

Mixed Integer Nonlinear Optimization

Many real-world problems lead to Mixed Integer Nonlinear Optimization problems (MINLP) that need to be solved to global optimality. This is a further generalization of Mixed Integer Convex Optimization, where nonlinear function beyond convex functions are considered. To develop new mathematical methods for the global optimization of MINLPs, theoretical results that allow us to construct strong mixed-integer convex relaxations for MINLPs are needed. In particular, we focus on identifying combinatorial substructures induced by integral variables that can be exploited to improve global optimization algorithms, and on bound tightening techniques.

Below we list some ongoing projects at IFOR in this field.

Integer Polynomial Optimization in Fixed Dimension (K. Zemmer, R. Weismantel)

Linear integer programming has been studied extensively over the recent decades and several fundamental results have been found. While some of those have been extended to various classes of convex problems, comparatively little is known about general nonconvex problems. This project focuses on one particular case of nonconvex integer optimization, namely polynomial optimization in fixed dimension. Some recent advances have been made for quadratic polynomials, but many open questions still remain.

Mixed-Integer Nonlinear Optimization with Applications in Chemical Engineering (M. Ballerstein, D. Michaels, R. Weismantel)

A general approach in global optimization is to combine local search methods with algorithms computing strong globally valid bounds on the optimal function value of the underlying MINLP. This is achieved by constructing and solving a hierarchy of (mixed integer) convex relaxations. For this, the non-linearities involved in the model description are typically replaced by convex under- and concave overestimators. A key step to obtain reasonable bounds is to build strong convex relaxations. The tightest convex under- and the tightest concave overestimator are called the convex and the convex envelope of a function, and are only known explicitly for a few special classes of functions. It is the goal of this research project to develop new mathematical methods for the global optimization of MINLPs. The usefulness of the developed algorithms are demonstrated by considering MINLPs arising in the context of the Collaborative Research Centre SFB/TR 63 "InPROMPT - Integrated Chemical Processes in Liquid Multiphase Systems" funded by the German Research Foundation (DFG).