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.