This paper presents a generic reformulation framework for binary integer programs (BIPs) that does not impose additional specifications on the objective function or constraints. To enable this generality, we introduce a set system approximation theory designed to identify the tightest inner and outer approximations for any binary solution space using special types of set systems. This approach leads to flexible reformulation strategies for BIPs, particularly focusing on the combination of set covering and subtour elimination inequalities. We provide an efficient separation subroutine based on a given membership oracle, and derive facet-defining conditions of these inequalities for general BIPs. We also explore the implications of this methodology on various problem instances, uncovering new solution strategies and structural insights for classic problems such as the longest path and traveling salesman. Additionally, we extend the structural aspect of max-flow min-cut theorem to a broader context of set system duality. Finally, we demonstrate the flexibility and efficiency of the proposed framework through a case study on a network site selection problem with distributionally robust chance constraints.
Article
View Binary Integer Program Reformulation: A Set System Approximation Approach