Probability of unique integer solution to a system of linear equations
Probability of unique integer solution to a system of linear equations
复制标题
线性方程组唯一整数解的概率
DOI：
10.1016/j.ejor.2011.04.010
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Benjamin Recht
中科院分区：
文献类型：
--
作者：
O. Mangasarian;Benjamin Recht
本文考虑了一个非线性常微分方程组Ax = d，给出了该方程组存在唯一解的充要条件，即x∈ {−1，1}n.我们实现这一点，通过重新制定的问题作为一个线性规划，并推导出必要和充分条件的整数解是唯一的原始最优解。我们证明了，只要mis大于坦恩/2，则线性规划的重构在大多数情况下都是成功的，但如果mis小于坦恩/2，则线性规划的重构在大多数情况下都是失败的.我们还表明，这些预测匹配的线性规划制定非常高的准确性的经验表现。
We consider a system ofmlinear equations innvariablesAx=dand give necessary and sufficient conditions for the existence of a unique solution to the system that is integer:x∈ {−1, 1}n. We achieve this by reformulating the problem as a linear program and deriving necessary and sufficient conditions for the integer solution to be the unique primal optimal solution. We show that as long asmis larger thann/2, then the linear programming reformulation succeeds for most instances, but ifmis less thann/2, the reformulation fails on most instances. We also demonstrate that these predictions match the empirical performance of the linear programming formulation to very high accuracy.