This objective of this award is to improve the solvability of combinatorial optimization problems by integrating information obtained from a partial application of dynamic programming (DP) within valid inequality generation schemes for mixed-integer programming (MIP) algorithms. Computationally, the advantage of this technique is that one can execute a partial DP algorithm (up to a tractable number of stages) for the problem at hand. The optimal state values obtained in this process can then be used to provide lower bounds (for minimization problems) on partial objective function values, as a function of a small number of key variables. A deeper analysis of the technique reveals that the process uses DP to project the MIP feasible region onto a key subset of MIP variables. The state information obtained from the truncated DP execution yields valid inequalities, which provide bounds on a portion of the problem objective as a function of these key variables. It is hoped that these investigations will shift focus from not only examining facet-defining inequalities for MIP polyhedra, but also to generating inequalities that capture strong relationships between a set of designated key variables and partial objective function values.
A number of important problems in production, supply chain management and national security can be modeled as combinatorial optimization problems. For example, the capacitated lot-sizing problem (CLSP) is solved in numerous industries to make periodic inventory re-ordering and production scheduling decisions. Unfortunately, this, and other combinatorial problems, can be hard to solve. Preliminary analysis has shown the proposed solution method to be successful at solving the CLSP. If successful, we hope the method can improve the solvability of other hard, but important, problems in supply chain management (generalized assignment and prize-collecting routing), finance (knapsack) and security (node detection and network monitoring).
This research focused on improving our ability to solve large combinatorial optimization problems (COPs). A COP essentially defines a set of rules that solutions must satisfy, and a scoring function used to rate the quality of the solution. The goal is to find a solution that scores the best and satisfies all rules. For instance, consider a replacement schedule for a fleet of aircraft. Depending on capital budgeting constraints, a limited number of aircraft can be replaced (depending on their age and annual maintenance costs) each year. One may attempt to minimize the cost of replacement and maintenance costs, minus salvage values. Hence, the solution in this case would represent a replacement schedule that obeys the capital budgeting constraints, and the "score" would be cost to execute that replacement plan. The primary difficulty confronting such problems is that there are many solutions; so many that even the fastest computers in the world could not enumerate and score all possibilities within centuries of computational time. The goal is therefore to design algorithms that intelligently search over the solutions, identifying optimal solutions within practical computational limits. One such method is called mixed-integer programming (MIP), and another is called dynamic programming (DP). The methods are conceived as different alternatives for solving COPs, although there are a few conceptual linkages that can be drawn between them. This proposal makes those linkages more explicit, and takes the vital step of incorporating information gleaned from one method within the other. As a result, we obtain hybrid algorithms that can be used to solve real-world problems much more quickly than before. For instance, DP algorithms are usually solved in stages: In the context of the equipment replacement problem, we would generate candidate solutions through one year, then through two years, propagate those solutions to a third year, and so on. DP would fail to be practical after a certain number of years, though, because of the memory and computational requirements associated with this process. The key would be to accumulate the information from a partial application of DP within an MIP. One could terminate the DP approach at a certain point and derive functional information that makes solving the MIP much easier. The research took this concept, and developed it in several ways that were not foreseen when the research began. Most of these developments are theoretical, but they have practical implications in improving how well the given problems were solved. We then embedded this information in several applied settings. The equipment replacement problem was one such setting, and another came in production planning models (how much to produce to minimize a combination of storage and seasonal production costs, in order to satisfy periodic demands). However, the proposed techniques saw many applications beyond these more industrial settings. For instance, we used this to determine how to optimally quarantine a transportation network in the case of a rapidly spreading disease. One can imagine a case in which an outbreak is detected, and travelers must be monitored to prevent the spread of disease. Because travelers cannot be monitored at each hub (node) of a transportation network due to resource limitations, one wishes to select a subset of nodes to monitor. The goal is to minimize the extent to which the disease could spread through the network, if monitoring the selected set of nodes blocks the spread of disease through those nodes. Other applications of our techniques arose in ecological applications and various network optimization models during the course of our project. The value of studying fundamental COP algorithm theory is that a very large, important, and diverse set of problems can be modeled as COPs, and research that enables their solution simultaneously improves our ability to solve all such vital applications.
