We present an MCMC algorithm for sampling from the complement of a polyhedron. Our
approach is based on the Shake-and-bake algorithm for sampling from the boundary of a set
and provably covers the complement. We use this algorithm for data augmentation in a
machine learning task of classifying a hidden feasible set in a data-driven optimization
pipeline. Numerical results on simulated and MIPLIB instances demonstrate that our
algorithm, along with a supervised learning technique, outperforms conventional …