A Note on the Asymptotic Theory of Integer Programming and the 0-1 Case
Auteur : Egon Balas
Date de publication : 1971
Éditeur : Management Sciences Research Group, Graduate School of Industrial Administration, Carnegie-Mellon University
Nombre de pages : 10
Résumé du livre
While asymptotic theory is in many ways useful for 0-1 problems too, in this note the author shows that in the case of a 0-1 program the sufficient condition given by Gomory for a solution to the asymptotic problem to solve the initial integer program, is never satisfied. A much weaker (and less than sufficient) condition is also never satisfied. This underscores the need to use information about the constraints that are slack at the linear programming optimum. (Author).