Probability of unique integer solution to a system of linear equations
| Autor: | Benjamin Recht, Olvi L. Mangasarian |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Discrete mathematics
Information Systems and Management General Computer Science Linear programming Branch and price Management Science and Operations Research System of linear equations Industrial and Manufacturing Engineering Linear-fractional programming Modeling and Simulation Branch and cut Integer programming Linear equation Mathematics Integer (computer science) |
| Zdroj: | European Journal of Operational Research. 214:27-30 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2011.04.010 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect