A Theoretical and Computational Comparison of "Equivalent" Mixed-Integer Formulations

Abstract

This paper provides a theoretical and computational comparison of alternative mixed integer programming formulations for optimization problems involving certain types of economy-of-scale functions. Such functions arise in a broad range of applications from such diverse areas as vendor selection and communications network design. A "non-standard" problem formulation is shown to be superior in several respects to the traditional formulation of problems in this class.