Fast heuristics for the maximum feasible subsystem problem

被引：58

作者：

Chinneck, JW ^{[1
]}

机构：

[1] Carleton Univ, Ottawa, ON K1S 5B6, Canada

来源：

INFORMS JOURNAL ON COMPUTING | 2001年 / 13卷 / 03期

关键词：

linear programming; artificial intelligence; heuristic; analysis of algorithms;

D O I：

10.1287/ijoc.13.3.210.12632

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Given an infeasible set of linear constraints, finding the maximum cardinality feasible subsystem is known as the maximum feasible subsystem problem. This problem is known to be NP-hard, but has many practical applications. This paper presents improved heuristics for solving the maximum feasible subsystem problem that are significantly faster than the original, but still highly accurate.

引用

页码：210 / 223

页数：14

共 25 条

[1] THE COMPLEXITY AND APPROXIMABILITY OF FINDING MAXIMUM FEASIBLE SUBSYSTEMS OF LINEAR RELATIONS [J].