Computational Methods for Discrete Conic Optimization

离散圆锥优化的计算方法

• 批准号: 1319893
• 负责人: Theodore Ralphs
• 金额: $ 30万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319893&HistoricalAwards=false
• 关键词: Computational; Methods; Discrete; Conic; Optimization

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.

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