| Article ID: | iaor1994722 |
| Country: | Netherlands |
| Volume: | 13 |
| Issue: | 1 |
| Start Page Number: | 19 |
| End Page Number: | 20 |
| Publication Date: | Feb 1993 |
| Journal: | Operations Research Letters |
| Authors: | Sankaran Jayaram K. |
| Keywords: | combinatorial analysis |
The paper studies the problem of finding a set of constraints of minimum cardinality which when relaxed in an infeasible linear program, make it feasible. It shows the problem is NP-hard even when the constraint matrix is totally unimodular and proves polynomial-time solvability when the constraint matrix and the right-hand-side together form a totally unimodular matrix.