Polyherdral Methods in Integer and Combinatorial Optimization

整数和组合优化中的多面体方法

• 批准号: 9424348
• 负责人: Egon Balas
• 金额: $ 39.61万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-08-01 至 1998-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9424348&HistoricalAwards=false
• 关键词: Polyherdral; Methods; Integer; Combinatorial; Optimization

9424348 Balas This objective of this research is to extend some earlier work undertaken by the investigators in integer and combinatorial optimization problems. The research on which the current work is built was supported also by the National Science Foundation. In earlier research, the investigators developed a new approach to solving mixed integer programming problems based on a framework described as 'lift-and-project cuts' within the context of the branch and bound technique. The procedure has been founded to be robust and more efficient than any of the approaches currently used in solving mixed integer programs. The current research is aimed at investigating some other unresolved questions associated with the improved technique. Included in the questions to be resolved are matters related to the characterization of the computational behavior of the algorithm, development of some other new algorithms, and the design and implementation these algorithms to solve a broader class of problems. The lift-and-project cut approach to mixed integer programming has applications to several areas of design, manufacturing, distribution, facility location, and civil infrastructure development. One such application is the optimal design of multi-product batch plants in chemical engineering, where the optimization is concerned with the choice of unit plants sizes for various stages of the process and the batch sizes for the products. Another example is the design of a cost-effective fiber optics network that protects services against the consequences of equipment failure. In the area of civil infrastructure development, one example is the design of a minimum weight truss consisting of a number of specified bars with fixed modal locations, under specified conditions on stresses, bar elongations, and nodal displacement. Another class of problems studied in this research is the generalized traveling salesman problem where the development technique can be used to construct optimal rolling cycles i n a hot strip mill. This research has the potential to significantly enhance the advancement and the understanding of integer and combinatorial optimization problems. Furthermore, several sectors of the economy stand to benefit from the results.

小行星9424348 这项研究的目的是扩展一些早期的工作所进行的调查，在整数和组合优化问题。 目前工作所基于的研究也得到了国家科学基金会的支持。 在早期的研究中，研究人员开发了一种新的方法来解决混合整数规划问题的基础上描述为“提升和项目削减”的背景下的分支和绑定技术的框架。 该程序已被发现是强大的，更有效的比目前使用的任何方法在解决混合整数规划。 目前的研究旨在调查与改进技术相关的其他一些未解决的问题。 包括在要解决的问题是有关的问题的算法的计算行为的表征，其他一些新的算法的发展，以及设计和实施这些算法来解决更广泛的一类问题。 混合整数规划的升降机和项目切割方法在设计、制造、配送、设施选址和民用基础设施开发等多个领域都有应用。 一个这样的应用是化学工程中的多产品间歇工厂的优化设计，其中优化涉及到过程的各个阶段的单元工厂大小和产品的批量大小的选择。 另一个例子是设计一个具有成本效益的光纤网络，保护服务免受设备故障的影响。 在民用基础设施开发领域，一个例子是在特定的应力、杆件伸长和节点位移条件下，由若干具有固定模态位置的特定杆件组成的最小重量桁架的设计。 另一类问题的研究是广义旅行商问题的发展技术可以用来构建最佳轧制周期在热连轧机。 这项研究有可能显着提高整数和组合优化问题的进步和理解。 此外，若干经济部门也将受益于这些成果。