Dimension reduction techniques for mixed integer programs

这个提议的发现基金研究项目将研究解决混合整数优化模型的方法。这些模型经常用于解决各种行业和业务部门的各种问题。通常，求解混合整数模型的难点在于大量的整数值变量，我们称之为模型的维数。在本课程中，我们将重点讨论降低模型维度的方法，以便更有效地求解模型。我们将进行以下四个方向的研究。(i)具有线性约束的混合整数模型用于解决商业、工程和医疗保健中的问题。解决这些模型的经典工具包括引入新的约束和分治方法。我们计划通过检查实际需要多少整数变量来计算最优解决方案来增加这个工具箱。这项研究将允许我们确定何时可以通过简单地优化低维模型来优化模型，其中一些整数约束是放松的。许多模型在其约束条件中表现出模式。例如，当我们对一段时间内做出的决定进行建模时，比如决定如何在一天内将能量分配到电网中，这种情况就会发生。在这里，我们将研究如何利用模式来重新制定模型，以减少整数变量。此外，我们将研究出现在现实世界问题模型中的模式，包括来自调度和能源规划的模型。（iii）研究方向(i)和（ii）对高维模型进行简化，使其可以用针对低维模型设计的算法求解。或者，我们可以扩展连续模型的算法，即没有整数变量的模型，这样它们就可以应用于具有整数模型的模型。连续凸模型捕获了统计学和金融学中的问题。梯度下降法是求解连续凸模型的一种特别有效的算法。在这一行中，我们将扩展梯度下降来处理整数变量。在优化中经常使用启发式方法，以便立即取得最优解决办法。近年来，机器学习（ML）已被用于改进(i)中提到的经典优化工具的启发式。我们将实现ML技术来设计启发式方法，以重新制定(i)和（ii）中概述的整数变量。本研究计划将开发用于降低混合整数模型维数的通用工具。我们期望这些新工具对最先进的优化软件进行长期改进。混合整数模型已经用于解决加拿大社会的问题；例如，匹配器官捐赠者和患者的问题，或者绘制当地电网的问题。因此，我们预计这项研究也将导致更快的方法来解决加拿大组织和企业使用的现有模型。

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.