Cost-Effective Capacity Planning Involving Differently Sized Capacity Modules
Cost-effective operation of many systems critical to the U.S. economy and society, such as power grids, data centers, telecommunication networks, medical facilities, on/off-shore pipelines, transportation, construction, production, and service systems, is highly dependent on cost-effective planning of capacity installation/deployment/usage in these systems (e.g., for processing, transmission, transportation, production, or service capacity). The concept of capacity in these systems is oftentimes modular, i.e., the total capacity is composed of identical capacity modules that are installed/deployed/used as needed. Cost-effective capacity planning in such systems is a challenging problem. Mixed integer programming is well suited to model this problem but to date research on mixed integer programming cutting plane theory has almost entirely focused on problems with a single modularity (module size). This is while in the aforementioned systems, the available capacity modules are, almost always, of several different sizes, which makes cost-effective capacity planning much more challenging.
This research aims to address this gap by developing and evaluating cutting planes to solve mixed integer programs involving multi-modularity capacity constraints with a particular focus on multi-modularity capacitated lot-sizing, facility location, and network design. The complex integer rounding methodologies developed by the investigation team in their previous project provide an appropriate machinery to initiate this research.
Complex Integer Rounding Cuts for Mixed Integer Programming
The overarching goal of this research is to create and evaluate new cutting plane methods for mixed integer programming using a new approach here called Complex Integer Rounding. It involves the generalization of Mixed Integer Rounding (MIR) in several fundamental ways. The general approach is to identify and study the structure of simple polyhedra and use them to develop new general cuts. Both single-constraint and multi-constraint cuts are considered and facet-defining properties of the developed cuts are investigated. The customization of the cuts to a collection of important special-structure problems is studied. In order to evaluate performance of the developed cuts, efficient separation methods are developed and comprehensive computational experiments are performed.