EUVIMEDEUVIMED entdecken
Crossref

Locating Minimal Infeasible Constraint Sets in Linear Programs

John W. Chinneck, Erik W. Dravnieks

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →