Minimal Cut-Generating Functions Are Nearly Extreme

We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory-Johnson setting as well as a recent extension by Cornuejols and Yildiz. We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions are "dense" in the set of continuous (strongly) minimal functions.

By: Amitabh Basu , Robert Hildebrand, Marco Molinaro

Published in: Lecture Notes in Computer Science, volume 9682, (no ), pages 201-13 in 2016

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .