共 2 条
[1]
Aho A. V., 1974, DESIGN ANAL COMPUTER
[2]
Gale D., 1960, THEORY LINEAR EC MOD
A NOTE ON RESOLVING INFEASIBILITY IN LINEAR-PROGRAMS BY CONSTRAINT RELAXATION
被引：38
作者：
SANKARAN, JK
机构：
[1] Department of Management Studies, Indian Institute of Science, Bangalore
关键词：
LINEAR PROGRAMMING;
POST-INFEASIBILITY ANALYSIS;
CONSTRAINT RELAXATION;
D O I：
10.1016/0167-6377(93)90079-V
中图分类号：
C93 [管理学];
O22 [运筹学];
学科分类号：
070105 ;
12 ;
1201 ;
1202 ;
120202 ;
摘要：
We study the problem of finding a set of constraints of minimum cardinality which when relaxed in an infeasible linear program, make it feasible. We show the problem is NP-hard even when the constraint matrix is totally unimodular and prove polynomial-time solvability when the constraint matrix and the right-hand-side together form a totally unimodular matrix.
引用
收藏
页码：19 / 20
页数：2
相关论文