This paper presents a generic reformulation framework for binary integer programs (BIPs) without imposing additional specifications for the objective function or constraints. To facilitate such 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 development leads to an exact reformulation framework for general BIPs, centered around set covering and subtour elimination inequalities. We investigate the implications of this methodology on various instance problems, uncovering new solution strategies and structural insights. Building upon these advancements, we also extend the classic max-flow min-cut theorem into a broader context of set system duality. Overall, our framework explores a new direction in the field of integer programming by examining the algebraic properties of set systems and their operators, which may spur additional research questions and further enrich the field.
Article
View Binary Integer Program Reformulation: A Set System Approximation Approach