Dimension reduction techniques for mixed integer programs

混合整数规划的降维技术

• 批准号: RGPIN-2021-02475
• 负责人: Paat, Joseph
• 金额: $ 2.62万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=764606
• 关键词: Dimension; reduction; techniques; mixed; integer

This proposed Discovery Grant research program will investigate methods for solving mixed integer optimization models. These models are frequently used to solve a wide array of problems in various industry and business sectors. Typically, the difficult part of solving a mixed integer model is the large number of integer-valued variables, which we refer to as the dimension of the model. In this program, we will focus on ways of reducing a model's dimension so that it can be solved more efficiently. We will pursue the following four directions of research. (i) Mixed integer models with linear constraints are used to solve problems in business, engineering, and health care. Classic tools for solving these models include the introduction of new constraints and divide-and-conquer methods. We plan to add to this toolbox by examining how many integer variables are actually needed to compute an optimal solution. This study will allow us to determine when a model can be optimized by simply optimizing a lower-dimensional model, where some integer constraints are relaxed.  (ii) Many models exhibit patterns in their constraints. This occurs, for instance, when we model decisions made over time such as deciding how to distribute energy in a power grid over the course of a day. Here, we will study how patterns can be leveraged to reformulate a model to have fewer integer variables. Furthermore, we will investigate patterns that appear in models of real-world problems, including those from scheduling and energy planning. (iii) Research directions (i) and (ii) simplify a high-dimensional model so that it can be solved by an algorithm designed for low-dimensional models. Alternatively, one can extend algorithms for continuous models, i.e., models with no integer variables, so that they apply to models with integer models. The continuous convex model captures problems in statistics and finance. Gradient descent is a particularly effective algorithm for solving continuous convex models. Under this investigative line, we will extend gradient descent to handle integer variables. (iv) Heuristics are frequently used in optimization to make immediate progress towards an optimal solution. In recent years, machine learning (ML) has been used to improve heuristics for the classic optimization tools mentioned in (i). We will implement ML techniques to design heuristics for reformulating integer variables as outlined in (i) and (ii). This research program will develop general tools for reducing the dimension of a mixed integer model. We expect these new tools to make long-term improvements to state-of-the-art optimization software. Mixed integer models are already used to address problems in Canadian society; for example, the problem of matching organ donors with patients or the problem of mapping local power grids. Therefore, we anticipate that this research will also lead to faster methods for solving preexisting models used by Canadian organizations and businesses.

这项拟议的发现拨款研究计划将研究求解混合整数优化模型的方法。这些模型经常被用来解决各种工业和商业部门的各种问题。通常，求解混合整数模型的困难部分是大量的整数值变量，我们将其称为模型的维度。在本节目中，我们将重点介绍如何降低模型的维度，以便更有效地求解。我们将进行以下四个方面的研究。(I)线性约束的混合整数模型用于解决商业、工程和医疗保健方面的问题。解决这些模型的经典工具包括引入新的约束和分而治之的方法。我们计划通过检查实际需要多少个整数变量来计算最优解来增加此工具箱。这项研究将使我们能够确定何时可以通过简单地优化低维模型来优化模型，其中一些整数约束被放松。(Ii)许多模型在其约束中表现出模式。例如，当我们对随着时间推移所做的决策进行建模时，例如决定如何在一天的过程中在电网中分配能源时，就会发生这种情况。在这里，我们将研究如何利用模式来重新制定模型，使其具有更少的整数变量。此外，我们将研究现实世界问题模型中出现的模式，包括来自调度和能源规划的模式。(3)研究方向(一)和(二)简化高维模型，以便可以用为低维模型设计的算法来求解。或者，人们可以扩展用于连续模型的算法，即没有整数变量的模型，以便它们适用于具有整数模型的模型。连续凸模型捕捉了统计学和金融学中的问题。梯度下降算法是求解连续凸模型的一种特别有效的算法。在这一研究思路下，我们将把梯度下降扩展到处理整数变量。(4)在优化中经常使用启发式方法，以便立即获得最优解。近年来，机器学习(ML)被用于改进(I)中提到的经典优化工具的启发式算法。我们将实现ML技术来设计启发式算法，以重新定义整数变量，如(I)和(Ii)所述。这项研究计划将开发用于混合整数模型降维的通用工具。我们预计这些新工具将对最先进的优化软件进行长期改进。混合整数模型已经被用来解决加拿大社会中的问题；例如，器官捐赠者与患者匹配的问题或绘制当地电网图的问题。因此，我们预计这项研究还将导致解决加拿大组织和企业使用的先前存在的模型的更快方法。