Computational Methods for Discrete Conic Optimization

Lehigh University, Bethlehem PA

Investigators

Abstract

This project's goal is to develop and implement methodology for solving mixed integer conic linear optimization problems (MICLPs), which are to minimize a linear function subject to both conic and linear constraints, as well as integrality constraints on a subset of the variables. The primary focus of this work is on computational methods for solving MICLPs involving so-called second order cones, which form the basis for the most tractable class of conic optimization problems. Although both discrete and conic optimization models have been the subject of intense study, their integration is a challenging task; only recently have the two areas gained enough maturity to make the development of efficient solution methodologies for MICLPs realistic. The PI proposes a new paradigm, called branch and constrain, that generalizes the disjunctive methods so successfully applied in the case of discrete linear models. The work involves study of the geometric structure of the feasible regions of these models and the disjunctive sets that arise, as well as the development of methodology to exploit this knowledge in a general computational framework. An optimization problem is that of choosing values for a set of variables that minimize the value a given objective function (function of the variables) subject to the restriction that the values of a set of constraint functions (also functions of the variables) are constrained to be between given bounds. One may also require the variables to take values from a certain restricted set (such as the integers). The most tractable optimization problems are those involving linear functions and for which the variables may take any real value. The addition of nonlinear functions or variables whose values must be taken from a discrete set significantly impacts the efficiency with which the model can be solved. Among nonlinear constraints, conic constraints are the easiest to accommodate, so the development of methods for solving discrete conic optimization problems is the first natural step in developing approaches to more general models that have both discrete and nonlinear structure. Many real-world applications involve a combination of these two modeling paradigms. For example, financial optimization models often involve constraints on the level of risk, which can be expressed using conic constraints. In supply chain logistics, bounds on the distance between two geospatial locations can also be expressed using conic constraints. In both of these classes, applications naturally arise in which there are also discrete choices to be made. For example, in portfolio optimization, one often wants to restrict the number of investments in a given portfolio. In facility location models, one wants to restrict the choice of locations to a given list of candidates. Models of maximizing returns subject to risk bounds or minimizing costs subject to geospatial constraints are examples of the kinds of models whole solution this work will enable.