Polyherdral Methods in Integer and Combinatorial Optimization

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

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.