This research will develop new lift-and-project methods for 0-1 mixed-integer programming. These methods will encompass two classes of techniques. The research team will consider lifting an n-dimensional point to a zeta-vector of the subset algebra of the n-dimensional hypercube, thereby extending the Lovasz-Schrijver, Sherali-Adams, Lasserre methods, as well as the disjunctive programming ('lift and project') method of Balas, Ceria and Cornuejols. Such a lifting appears promising in that it produces higher-dimensional objects "faster" than the previously mentioned methods. The second class of techniques will consider successively refining a disjunction to generate deeper cutting planes.
Integer programming embodies the systematic solution of planning problems arising in numerous practical settings, e.g. transportation, logistics, supply chain, finance, power generation and others. Such problems are inherently non-continuous: they involve the allocation of discrete units of resources. As such, they are extremely intractable. At the same time, accurate solutions translate into substantial savings, and thus there is a need for effective solution methodologies. The impact of this research will be to broaden the class of problems that can be successfully tackled, using innovative techniques.
