Paper Info
Title
Checking weak optimality and strong boundedness in interval linear programming
Abstract
Interval programming provides a mathematical tool for dealing with uncertainty in optimization problems. In this paper, we study two properties of interval linear programs: weak optimality and strong boundedness. The former property refers to the existence of a scenario possessing an optimal solution, or the problem of deciding non-emptiness of the optimal set. We investigate the problem from a complexity-theoretic point of view and prove that checking weak optimality is NP-hard for all types of programs, even if the variables are restricted to a single orthant. The property of strong boundedness implies that each feasible scenario of the program has a bounded objective function. It is co-NP-hard to decide for inequality-constrained interval linear programs. For this class of programs, we derive a sufficient and necessary condition for testing strong boundedness using the orthant decomposition method. We also discuss the open problem of checking strong boundedness of programs described by equations with nonnegative variables.
Year
DOI
Venue
2019
10.1007/s00500-018-3520-3
soft computing
Keywords
Field
DocType
Interval linear programming, Weak optimality, Strong boundedness, Computational complexity
Mathematical optimization,Open problem,Orthant,Interval programming,Interval linear programming,Computer science,Decomposition method (constraint satisfaction),Optimization problem,Bounded function,Computational complexity theory
Journal
Volume
Issue
ISSN
23
SP9
1433-7479
Citations 
PageRank 
References 
0
0.34
9
Authors
2
Name
Order
Citations
PageRank
Elif Garajová131.44
Milan Hladík226836.33