Dimension reduction techniques for mixed integer programs

这个提议的发现资助研究计划将研究解决混合整数优化模型的方法。这些模型经常用于解决各种行业和商业部门的各种问题。通常，求解混合整数模型的困难部分是大量的整数值变量，我们称之为模型的维数。在这个程序中，我们将重点关注如何减少模型的维度，以便更有效地解决问题。我们将从以下四个方面进行研究。(i)具有线性约束的混合整数模型用于解决商业、工程和医疗保健中的问题。解决这些模型的经典工具包括引入新的约束和分治方法。我们计划通过检查实际需要多少整数变量来计算最优解来添加到这个工具箱中。这项研究将使我们能够确定何时可以通过简单地优化低维模型来优化模型，其中一些整数约束被放松。 (ii)许多模型在其约束中显示模式。例如，当我们对一段时间内做出的决策进行建模时，例如决定如何在一天内在电网中分配能量。在这里，我们将研究如何利用模式来重新构建模型，使其具有更少的整数变量。此外，我们将研究出现在现实世界问题模型中的模式，包括来自调度和能源规划的模式。(iii)研究方向（i）和（ii）简化了高维模型，以便可以通过为低维模型设计的算法来求解。或者，可以扩展连续模型的算法，即，没有整数变量的模型，因此它们适用于整数模型。连续凸模型捕捉统计和金融中的问题。梯度下降是求解连续凸模型的一种特别有效的算法。在这条研究路线下，我们将扩展梯度下降来处理整数变量。 (iv)启发式经常用于优化，以立即朝着最佳解决方案取得进展。近年来，机器学习（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.