We address the problem of testing weak optimality of a given solution of a given interval linear program. The problem was recently wrongly stated to be polynomially solvable. We disprove it. We show that the problem is NP-hard in general. We propose a new algorithm for the problem, based on orthant decomposition and solving linear systems. Running time of the algorithm is exponential in the number of equality constraints. Interval linear programs with inequality constraints only can be processed in polynomial time.
This paper considers optimal solutions of interval linear programming problems, in a unified framework. Necessary and sufficient conditions for checking (A,b)-strong optimality and (A,b,c)-strong optimality of interval linear programming with inequality constraints are developed. The features of the proposed methods are illustrated by some examples. Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ j , μ ij , μ i ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ ij = μ i = λ j = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ j , μ ij and μ i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set. We introduce a novel kind of robustness in linear programming. A solution x* is called robust optimal if for all realizations of the objective function coefficients and the constraint matrix entries from given interval domains there are appropriate choices of the right-hand side entries from their interval domains such that x* remains optimal. We propose a method to check for robustness of a given point, and also recommend how a suitable candidate can be found. We discuss topological properties of the robust optimal solution set, too. We illustrate applicability of our concept in transportation and nutrition problems. Since not every problem has a robust optimal solution, we introduce also a concept of an approximate robust solution and develop an efficient method; as a side effect, we obtain a simple measure of robustness. A system of interval linear equations is formed and solved.Solutions of system specify the optimal solution set of interval linear programming.Solution space of some solving methods and the optimal solution set are compared.The solutions obtained by proposed method and Monte Carlo method are compared.By solving a large-scale model, the applicability of proposed method is illustrated. Based on the binding constraint indices of the optimal solution to the linear programming (LP) model, a feasible system of linear equations can be formed. Because an interval linear programming (ILP) model is the union of numerous LP models, an interval linear equations system (ILES) can be formed, which is the union of these conventional systems. Hence, a new algorithm is introduced in which an arbitrary characteristic model of the ILP model is chosen and solved. The set of indices of its binding constraints is then obtained. This set is used to form and solve an ILES using the enclosure method. If all the components of the interval solutions to this system are strictly non-negative, the optimal solution set (OSS) of the ILP model is determined as the subscription of the zone created by reversing the signs of the binding constraints of the worst model and the binding constraints of the best model. The solutions to several problems obtained by the new algorithm and a Monte Carlo simulation are compared. The proposed algorithm is applicable to large-scale problems. To this end, an ILP model with 270 constraints and 270 variables is solved. We consider a linear programming problem with interval data. We discuss the problem of checking whether a given solution is optimal for each realization of interval data. This problem was studied for particular forms of linear programming problems. Herein, we extend the results to a general model and simplify the overall approach. Moreover, we inspect computational complexity, too. Eventually, we investigate a related optimality concept of semi-strong optimality, showing its characterization and complexity.  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  