Cost-Effective Capacity Planning Involving Differently Sized Capacity Modules

涉及不同容量模块的经济高效的容量规划

• 批准号: 1435526
• 负责人: Kiavash Kianfar
• 金额: $ 26.5万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1435526&HistoricalAwards=false
• 关键词: Cost; Effective; Capacity; Planning; Involving

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.

对美国经济和社会至关重要的许多系统（例如电网、数据中心、电信网络、医疗设施、陆上/海上管道、运输、建筑、生产和服务系统）的经济高效运行高度依赖于对这些系统中的容量安装/部署/使用进行经济有效的规划（例如，处理、传输、运输、生产或服务容量）。这些系统中的容量概念通常是模块化的，即总容量由根据需要安装/部署/使用的相同容量模块组成。此类系统中具有成本效益的容量规划是一个具有挑战性的问题，可以使用先进的数学技术来解决。尽管在这些系统中，可用容量模块几乎总是具有几种不同的大小，但是现有的用于容量规划的数学技术仅解决所有容量模块具有相同大小的问题。这就是为什么不同尺寸模块的存在使得具有成本效益的容量规划变得更具挑战性。该奖项支持旨在通过开发数学方法来解决涉及多个不同大小的容量模块的具有成本效益的容量规划问题来解决这一差距的基础研究。因此，它将带来前所未有的快速解决大量此类问题的能力，从而显着提高上述系统中具有成本效益的容量规划能力，从而使美国经济和社会受益。这项研究还将为学生（包括来自代表性不足群体的学生）提供高级培训。混合整数规划非常适合对本研究中感兴趣的问题进行建模，但迄今为止，混合整数规划割平面理论的研究几乎完全集中在具有单一模块性（模块大小）的问题上。这项研究将开发和评估切割平面，以解决涉及多模块容量约束的混合整数程序，特别关注多模块容量批量大小、设施位置和网络设计。调查小组在先前资助的项目中开发的复杂整数舍入方法为启动这项研究提供了适当的机制。切割平面将通过新颖的多参数复杂整数舍入方法来开发。先前开发的内核面以及对某些新的多参数内核集进行多面体分析所产生的内核面将用于导出新的切割。将研究所有切割的刻面定义特性。将开发强大的扩展公式和优化算法。将设计用于所开发的切口的有效分离方法，并且将进行计算实验以评估所开发的切口与现有技术相比的性能。