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