Using separation algorithms to generate mixed integer model reformulations (Q1178714)

The linear relaxation of mixed integer programming models can be strengthened by introducing auxiliary variables. The author develops a new method for generating auxiliary variable reformulations for problems where the separation algorithm for finding violated cuts can be formulated as a linear program. The results have important consequences for integrality proofs and efficient formulations. Typical examples of the method are graph optimization and fixed charged problems. Computational results for one of the graph optimization problems (a traversal matroid) suggest that the new method is more stable than a conventional cutting plane method in the computational time required.