Extended Formulations via Decision Diagrams

We propose a general algorithm of constructing an extended formulation for any given set of linear constraints with integer coefficients. Our algorithm consists of two phases: first construct a decision diagram (V, E) that somehow represents a given \(m \times n\) constraint matrix, and then build an equivalent set of |E| linear constraints over \(n+|V|\) variables. That is, the size of the resultant extended formulation depends not explicitly on the number m of the original constraints, but on its decision diagram representation. Therefore, we may significantly reduce the computation time and space for optimization problems with integer constraint matrices by solving them under the extended formulations, especially when we obtain concise decision diagram representations for the matrices. We demonstrate the effectiveness of our extended formulations for mixed integer programming and the 1-norm regularized soft margin optimization tasks over synthetic and real datasets. Eligible for best student paper.