Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
478488 | European Journal of Operational Research | 2011 | 4 Pages |
We consider a system of m linear equations in n variables Ax = d and 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 as m is larger than n/2, then the linear programming reformulation succeeds for most instances, but if m is less than n/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.
► Uniqueness of integer solution of linear equations. ► Reformulation as a linear program. ► Unique primal minimal solution.