Finding the minimum weight IIS cover of an infeasible system of linear inequalities

被引：40

作者：

Parker, M

Ryan, J

机构：

[1] UNIV COLORADO,DEPT MATH,DENVER,CO 80401

[2] US WEST,TECHNOL,BOULDER,CO 80303

来源：

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE | 1996年 / 17卷 / 1-2期

关键词：

D O I：

10.1007/BF02284626

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Given an inconsistent set of inequalities Ax less than or equal to b, the irreducible inconsistent subsystems (IISs) designate subsets of the inequalities such that at least one member of each subset must be deleted in order to achieve a feasible system. By solving a set covering problem over the IISs, one can determine a minimum weight set of inequalities that must be deleted in order to achieve feasibility. Since the number of IISs is generally exponential in the size of the original subsystem, we generate the IISs only when they are violated by a trial solution. Computational results on the NETLIB infeasible LP library are given.

引用

页码：107 / 126

页数：20