Validated Infeasible Interior-Point Predictor–Corrector Methods for Linear Programming

Autor:	Ismail I. Idriss, Wolfgang V. Walter
Rok vydání:	2004
Předmět:	Predictor–corrector method Mathematical optimization Linear programming Duality gap Applied Mathematics Numerical analysis Theory of computation Structure (category theory) Interval (mathematics) Interior point method Mathematics
Zdroj:	Numerical Algorithms. 37:177-185
ISSN:	1017-1398
DOI:	10.1023/b:numa.0000049465.66643.ce
Popis:	Many problems arising in practical applications lead to linear programming problems. Hence, they are fundamentally tractable. Recent interior-point methods can exploit problem structure to solve such problems very efficiently. Infeasible interior-point predictor–corrector methods using floating-point arithmetic sometimes compute an approximate solution with duality gap less than a given tolerance even when the problem may not have a solution. We present an efficient verification method for solving linear programming problems which computes a guaranteed enclosure of the optimal solution and which verifies the existence of the solution within the computed interval.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8bd10d825bd3489ab0c920af03c9e1dd https://doi.org/10.1023/b:numa.0000049465.66643.ce Zobrazit plný text záznamu Full text from SpringerLink