Polyherdral Methods in Integer and Combinatorial Optimization

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

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.