Computational Methods for Discrete Conic Optimization

这个项目的目标是开发和实现解决混合整数圆锥线性优化问题(MICLP)的方法，该问题旨在最小化同时受圆锥和线性约束以及变量子集的完整性约束的线性函数。这项工作的主要焦点是解决涉及所谓的二阶锥的MICLP的计算方法，这构成了最容易处理的一类圆锥优化问题的基础。虽然离散优化模型和二次优化模型都是深入研究的对象，但它们的集成是一项具有挑战性的任务；直到最近，这两个领域才获得足够的成熟，使开发有效的MICLP求解方法成为现实。PI提出了一种新的范式，称为分支和约束，它概括了在离散线性模型中成功应用的析取方法。这项工作包括研究这些模型的可行域和产生的析取集的几何结构，以及开发在一般计算框架中利用这些知识的方法。优化问题是在一组约束函数(也是变量的函数)的值被约束在给定界之间的约束下，为一组变量选择最小值的值的问题。还可以要求变量从特定的限制集中取值(例如整数)。最容易处理的优化问题是那些涉及线性函数的问题，对于这些问题，变量可以取任何实值。非线性函数或变量的加入极大地影响了模型的求解效率。在非线性约束中，二次曲线约束是最容易适应的，因此发展离散二次曲线优化问题的方法是将方法发展到具有离散和非线性结构的更一般模型的第一自然步骤。许多真实世界的应用程序都涉及这两种建模范例的组合。例如，金融优化模型通常涉及对风险水平的约束，这可以用二次曲线约束来表示。在供应链物流中，两个地理空间位置之间的距离界限也可以用二次曲线约束来表示。在这两个类别中，应用程序自然会出现，在这些应用程序中也有需要做出的离散选择。例如，在投资组合优化中，人们经常想要限制给定投资组合中的投资数量。在设施选址模型中，人们希望将地点的选择限制在给定的候选列表中。受风险约束的收益最大化或受地理空间约束的成本最小化的模型是整个解决方案将启用的模型类型的例子。

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.