Dimension reduction techniques for mixed integer programs

点击翻译按钮获取中文摘要

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.