论文标题
通过决策图扩展配方
Extended Formulations via Decision Diagrams
论文作者
论文摘要
我们提出了一种构建具有整数系数的任何给定线性约束的扩展公式的一般算法。我们的算法由两个阶段组成：首先构建决策图$（v，e）$，以某种方式代表给定的$ m \ times n $约束矩阵，然后在$ n+| v | $ variables上构建等效的$ | e | $线性约束。也就是说，所得的扩展配方的大小不明确取决于原始约束的数量$ m $，而是其决策图表示。因此，我们可以通过在扩展公式下求解整数约束矩阵的优化问题的计算时间，尤其是当我们获得矩阵的简洁决策图表示时。我们可以将我们的方法应用于$ 1 $ norm的二进制实例空间$ \ {0,1 \}^n $的正规化硬边缘优化，可以将其配置为具有$ \ { - { - 1,0,1,1 \} $的$ m $约束条件的线性编程问题，$ n $ n $ n $ variables，$ n $ $ $ $ $ $ $ $。此外，在决策图的边缘引入松弛变量，我们建立了软边缘优化的变体公式。我们证明了扩展配方在整数编程中的有效性以及$ 1 $ norm的正规化软边距优化任务对合成和真实数据集的有效性。
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 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 can apply our method to $1$-norm regularized hard margin optimization over the binary instance space $\{0,1\}^n$, which can be formulated as a linear programming problem with $m$ constraints with $\{-1,0,1\}$-valued coefficients over $n$ variables, where $m$ is the size of the given sample. Furthermore, introducing slack variables over the edges of the decision diagram, we establish a variant formulation of soft margin optimization. We demonstrate the effectiveness of our extended formulations for integer programming and the $1$-norm regularized soft margin optimization tasks over synthetic and real datasets.
