Skip to content

Probability of Unique Integer Solution to a System of Linear Equations

Authors: O. L. Mangasarian, Benjamin Recht

Published: 2011 (Journal Paper)

Source: European Journal of Operational Research

Algorithm: Linear programming relaxation

DOI: 10.1016/j.ejor.2011.04.010

Summary

Analyzes when a binary solution to an underdetermined linear system is uniquely recoverable through a linear-programming reformulation. The result is a sharp-ish phase transition around m greater than n/2 for typical random instances.

Abstract

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 in {-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.

Primary

Paper people.eecs.berkeley.edu

Standard

DOI 10.1016/j.ejor.2011.04.010

Tags

  • Integer programming

  • Linear programming

  • Unique solution

  • Binary systems

  • Optimization theory

  • Random matrices