MIXED-0-1 PROGRAMMING BY LIFT-AND-PROJECT IN A BRANCH-AND-CUT FRAMEWORK

We investigate the computational issues that need to be addressed when incorporating general cutting planes for mixed 0-1 programs into a br anch-and-cut framework. The cuts we use are of the lift-and-project va riety. Some of the issues addressed have a theoretical answer, but oth ers are of an experimental nature and are settled by comparing alterna tives on a set of test problems. The resulting code is a robust solver for mixed 0-1 programs. We compare it with several existing codes. On a wide range of test problems it performs as well as, or better than, some of the best currently available mixed integer programming codes.