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 that is solved using advanced mathematical techniques. Although in these systems, the available capacity modules are, almost always, of several different sizes, the existing mathematical techniques for capacity planning only address problems in which all capacity modules are of the same size. This is why the existence of differently sized modules makes cost-effective capacity planning much more challenging. This award supports fundamental research aimed to address this gap by developing mathematical methodologies to solve cost-effective capacity planning problems involving several differently sized capacity modules. Consequently, it will lead to unprecedented capability to solve large instances of such problems quickly, which will in turn significantly improve cost-effective capacity planning capabilities in the aforementioned systems, hence will benefit the U.S. economy and society. This research will also generate advanced training for students including those from underrepresented groups.
Mixed integer programming is well suited to model the problem of interest in this research but to date research on mixed integer programming cutting plane theory has almost entirely focused on problems with a single modularity (module size). This research will develop and evaluate 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 a previously funded project provide an appropriate machinery to initiate this research. Cutting planes will be developed through novel multi-parameter complex integer rounding approaches. Previously developed kernel facets as well as those resulting from polyhedral analysis of certain new multi-parameter kernel sets will be used to derive new cuts. Facet-defining properties of all cuts will be studied. Strong extended formulations and optimization algorithms will be developed. Efficient separation methods for the developed cuts will be devised and computational experiments will be conducted to evaluate the performance of the developed cuts compared to the state of the art.
