Cutting Plane Methods for Integer Programming
Date/Time: Tuesday 14:45-16:15
Cluster: Integer Programming
Room: Crystal Parlor C
Chair: Wilbert E. Wilhelm
Chair Address: TX A&M Univ., Dept. of IE, College Station, TX 77843-3131,
Optimizing Chvatal-Gomory Cuts Sebastian Ceria, G. Cornuejols, M. Dawande --- Columbia Univ., 417 Uris Hall, Grad. Sch. of Bus., New York, NY 10027 , (sebas@firstname.lastname@example.org)
- 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.
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 (email@example.com)
- 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.
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.
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.