Cutting Plane Methods for Integer Programming

TD06.1 Optimizing Chvatal-Gomory Cuts Sebastian Ceria, G. Cornuejols, M. Dawande --- Columbia Univ., 417 Uris Hall, Grad. Sch. of Bus., New York, NY 10027 , (sebas@cumparsita@gsb.columbia.edu)

We propose a new procedure for obtaining strong Chvatal-Gomory cuts¨ for general 0-1 programs. Our approach, contrary to the classic cut¨ generation procedure of Gomory, works directly on the original space¨ of variables without using the basis inverse. Computational results¨ will be reported.

TD06.2 On the Diversity of Scheduling Polyhedra Andreas S. Schulz --- Tech. Univ. at Berlin, Fachbereich Mathematik, MA6-1, Strasse des 17.Juni 136, Berlin, , Germany D-10623 (schulz@math.tu-berlin.de)

There has been recent success in using polyhedral formulations of¨ scheduling problems to obtain provably good lower and upper bounds.¨ We compare and analyze the strength of different types of LP¨ relaxations for various problems. We also discuss which model¨ performs best in practice.

TD06.3 A Simplex-Like Method for Generating Facets Radu Gadidov, Wilbert E. Wilhelm --- TX A&M Univ., Dept. of IE, College Station, TX 77843-3131,

We describe the theoretical basis for a simplex-like method for¨ generating facets of underlying polytopes, including proof that the¨ method converges finitely. In addition, computational results are¨ reported.

TD06.4 Solving Very Large Fleet Assignment Problems Using Column Generation & Branch & Cut Peter Ball, Karla L. Hoffman --- George Mason Univ., OR & Op. Eng. Dept., 4400 University Dr., Fairfax, VA 22024 ,

We examine the assignment of aircraft types to flight legs using a¨ column-generation approach. The resulting set partitioning¨ formulation provides a natural way of modeling the additional¨ revenue obtained by having connecting flights flown by the same¨ aircraft-type. Computational results are provided.