Locating Minimal Infeasible Constraint Sets in Linear Programs
ORSA Journal on Computing · 1991-05 · 3 (2) · 157-168
DOI: 10.1287/ijoc.3.2.157 ↗Kurz gefasst
Fachartikel in der Zeitschrift ORSA Journal on Computing, 1991-05. Verfasst von John W. Chinneck und 1 weiteren Autor:innen. Die Arbeit wurde bisher 195-mal zitiert (Crossref).
Abstract (Originalsprache)
With ongoing advances in hardware and software, the bottleneck in linear programming is no longer a model solution, it is the correct formulation of large models in the first place. During initial formulation (or modification), a very large model may prove infeasible, but it is often difficult to determine how to correct it. We present a formulation aid which analyzes infeasible LPs and identifies minimal sets of inconsistent constraints from among the perhaps very large set of constraints defining the problem. This information helps to focus the search for a diagnosis of the problem, speeding the repair of the model. We present a series of filtering routines and a final integrated algorithm which guarantees the identification of at least one minimal set of inconsistent constraints. This guarantee is a significant advantage over previous methods. The algorithms are simple, relatively efficient, and easily incorporated into standard LP solvers. Preliminary computational results are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Zitieren
APA
Chinneck, J. W., & Dravnieks, E. W. (1991). Locating Minimal Infeasible Constraint Sets in Linear Programs. ORSA Journal on Computing, 3(2), 157-168. https://doi.org/10.1287/ijoc.3.2.157
Vancouver
Chinneck JW, Dravnieks EW. Locating Minimal Infeasible Constraint Sets in Linear Programs. ORSA Journal on Computing. 1991;3(2):157-168. doi:10.1287/ijoc.3.2.157
BibTeX
@article{Chinneck1991,
author = {Chinneck, John W. and Dravnieks, Erik W.},
title = {Locating Minimal Infeasible Constraint Sets in Linear Programs},
journal = {ORSA Journal on Computing},
year = {1991},
volume = {3},
number = {2},
pages = {157--168},
doi = {10.1287/ijoc.3.2.157}
}
EUVIMED