Mixed Integer and Combinatorial Optimization: Lift-and-Project and Polyhedral Combinatorics

该项目的目标是通过主要基于提升和项目方法的更好的凸化技术的研究，加快过去15年来发生的整数和组合优化技术革命的步伐。主要研究人员打算在三个主要研究方向中应用线性代数的分析工具，如投影、提升、极性、基归约、析取模块化、凸船体生成，沿着算法技术，如旋转、切割平面生成、缩放技术、分离程序等：（i）如何减少生成具有所需特征的切割的计算成本;（ii）如何产生新的、更强的切割，或具有增强的联合强度的切割组，能够加速收敛到解，并且足够稳定而不会引起数值问题;以及（iii）如何通过更好的切割评估和选择技术等，在求解混合整数规划的整个过程中更好地利用切割。这三条攻击线预期在混合整数和组合优化器的算法工具箱中产生显著的改进。如果成功的话，这项研究将大大提高我们解决混合整数和组合优化问题的能力。这种进展将影响范围极为广泛的活动，从工业生产-供应链管理、排序和时间安排、装配线平衡-到物流、设施地点和分销的其他方面;从电信网络设计到网络运营;从飞机分配到跑道到登机口分配到飞机和行李运送到乘客;从飞机到达和起飞的调度到机组人员分配的调度;从优化产量管理到最大限度地提高服务运营中的客户满意度。这里开发的工具可能会在改善国土安全和加强我们的技术领先地位方面同样有用。

The goal of this project is to accelerate the pace of the revolution in the state of the art of integer and combinatorial optimization that has been taking place over the last 15 years, through research aimed at better convexification techniques, based primarily on the lift-and-project approach. The principal investigators intend to apply analytical tools of linear algebra, like projection, lifting, polarity, basis reduction, disjunctive modularization, convex hull generation, along with algorithmic techniques like pivoting, cutting plane generation, scaling techniques, separation procedures, etc. in three main directions of research: (i) how to reduce the computational cost of generating cuts with the required characteristics; (ii) how to produce new, stronger cuts, or groups of cuts with enhanced joint strength, capable of speeding up the convergence to a solution and yet stable enough not to cause numerical problems; and (iii) how to make better use of the cuts within the overall process of solving a mixed integer program, by better cut evaluation and selection techniques, etc. Together, these three lines of attack are expected to yield significant improvements in the algorithmic tool-kit of mixed integer and combinatorial optimizers. If successful, the research will lead to a substantial enhancement of our ability to solve mixed integer and combinatorial optimization problems. Such progress would affect an extremely broad range of activities, from industrial production--supply chain management, sequencing and scheduling, assembly line balancing--to logistics, facility location and other aspects of distribution; from telecommunications network design to network operation; from airplane allocation to runways to gate allocation to airplanes and luggage delivery to passengers; from the scheduling of arrivals and departures of airplanes to scheduling the airplane crew assignments; from optimizing yield management to maximizing customer satisfaction in service operations. The tools developed here may turn out to be as useful in improving homeland security as in reinforcing our technological leadership.