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

点击翻译按钮获取中文摘要

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.