Integrating Dynamic Programming within Mixed-Integer Programming Techniques

This NSF funding is awarded to J. Cole Smith and Joseph Hartman. 

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).