Name
Abstract | ||
|---|---|---|
This paper deals with the problem of linear programming with inexact data represented by real closed intervals. Optimization problems with interval data arise in practical computations and they are of theoretical interest for more than forty years. We extend the concept of duality gap (DG), the difference between the primal and its dual optimal value, into interval linear programming. We consider two situations: First, DG is zero for every realization of interval parameters (the so called strongly zero DG) and, second, DG is zero for at least one realization of interval parameters (the so called weakly zero DG). We characterize strongly and weakly zero DG and its special case where the matrix of coefficients is real. We discuss computational complexity of testing weakly and strongly zero DG for commonly used types of interval linear programs and their variants with the real matrix of coefficients. We distinguish the NP-hard cases and the cases that are efficiently decidable. Based on DG conditions, we extend previous results about the bounds of the optimal value set given by Rohn. We provide equivalent statements for the bounds |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s10957-019-01610-y | Journal of Optimization Theory and Applications |
Keywords | Field | DocType |
Interval analysis, Linear programming, Interval linear programming, Duality gap, Computational complexity, 90C05, 90C31, 65G40 | Applied mathematics,Mathematical optimization,Duality gap,Interval linear programming,Matrix (mathematics),Linear programming,Interval arithmetic,Mathematics,Special case,Computational complexity theory | Journal |
Volume | Issue | ISSN |
184 | 2 | 1573-2878 |
Citations | PageRank | References |
2 | 0.41 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jana Novotná | 1 | 2 | 2.10 |
| Milan Hladík | 2 | 268 | 36.33 |
| Tomáš Masařík | 3 | 6 | 6.97 |