Interval Linear Programming under Transformations: Optimal Solutions and Optimal Value Range
Elif Garajová Milan Hladík Miroslav Rada

	
	
	
	


Interval Linear Programming under Transformations: Optimal Solutions and Optimal Value RangeThe first two authors were supported by the Czech Science Foundation under Grant P403-18-04735S and by the Charles University, project GA UK No. 156317. The third author was supported by the Czech Science Foundation under Grant P403-17-13086S.
	
    
        Elif Garajová[
Charles University, Faculty  of  Mathematics  and  Physics,
Department of Applied Mathematics, 
Malostranské nám. 25, 11800, Prague, Czech Republic, 
e-mail: 
]
Milan Hladík[
Charles University, Faculty  of  Mathematics  and  Physics,
Department of Applied Mathematics, 
Malostranské nám. 25, 11800, Prague, Czech Republic, 
e-mail: 
]
Miroslav Rada[
University of Economics, Faculty of Finance and Accounting, Department of Financial Accounting and Auditing, W. Churchill's Sq. 4, 130 67 Prague, Czech Republic,
e-mail: 
]

    December 30, 2023
========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


		Interval linear programming provides a tool for solving real-world optimization problems under interval-valued uncertainty. Instead of approximating or estimating crisp input data, the coefficients of an interval program may perturb independently within the given lower and upper bounds. However, contrarily to classical linear programming, an interval program cannot always be converted into a desired form without affecting its properties, due to the so-called dependency problem.
		
		In this paper, we discuss the common transformations used in linear programming, such as imposing non-negativity on free variables or splitting equations into inequalities, and their effects on interval programs. Specifically, we examine changes in the set of all optimal solutions, optimal values and the optimal value range. Since some of the considered properties do not holds in the general case, we also study a special class of interval programs, in which uncertainty only affects the objective function and the right-hand-side vector. For this class, we obtain stronger results. 
	
	
Keywords. Interval linear programming; Optimal set; Optimal value range; Transformations


	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

§ INTRODUCTION

	
	When handling real-world optimization problems by means of mathematical modeling, it is often necessary to treat inexact or uncertain input data due to various measurement errors or estimations. Throughout the years, several approaches for solving optimization problems with imprecise data have emerged, based on different sources of uncertainty and different requirements imposed on the solutions. This paper adopts the approach of interval linear programming, which can be considered a special case of multi-parametric optimization with no dependencies among the coefficients. Interval-valued coefficients have been used for modeling uncertainty in many practical applications, such as portfolio selection <cit.>, environmental management <cit.> or group decision making <cit.>.
	
	In interval optimization, it is assumed that the coefficients may perturb independently within the given lower and upper bounds. However, rather than focusing on the worst case and trying to find a stable solution (as in robust optimization), we aim to cover the properties of all possible scenarios. This approach leads to questions such as describing the set of feasible solutions over all scenarios <cit.> and the set of all optimal solutions <cit.>, computing the optimal value range <cit.> or characterizing the duality gaps <cit.>. For an overview of other results in interval linear programming see the survey by <cit.>.
	
	This paper discusses an ever-present issue in interval optimization and interval analysis in general: the dependency problem. Since we do not allow any dependencies among the coefficients of an interval program and assume that the values of the coefficients perturb independently, any transformation that changes the program and duplicates some of the interval coefficients will also create new possible scenarios. Due to the dependency problem, transforming an interval program into a desired form by applying the standard transformations used in classical linear programming may change its feasible or optimal solutions and other important properties. Therefore, it may be necessary to study different types of programs separately, since the results obtained for one type do not have to hold for other types.
	
	We examine the effects of the transformations on the optimal solution set and the optimal value range in order to identify the transformations that are also applicable to interval linear programs while preserving the considered properties. This will allow us to directly generalize the results known for one type of programs to other forms, as well as highlight the cases in which the particular properties may differ. We will also study the problem on a special class of interval linear programs with interval coefficients only appearing in the objective function and the right-hand-side vector in order to derive stronger results. These types of programs arise in applications, where the coefficient matrix represents some known relations, such as transportation problems <cit.> or network flow problems <cit.>.
	
	The paper is structured as follows: Section <ref> introduces the basic notions and terminology of interval linear programming. In Section <ref>, we review the standard transformations used in classical linear programming and discuss their applicability on interval programs. Sections <ref> and <ref> explore the effects of the transformations on the set of all optimal solutions and optimal values of an interval linear program. Section <ref> summarizes and concludes the paper. 
	
	

§ INTERVAL LINEAR PROGRAMMING

	Given two real matrices A, A∈ℝ^m× n satisfying A≤A, we define an interval matrix as the set 
    A = [A, A] = {A ∈ℝ^m × n : A≤ A ≤A}.

	The matrices A, A are the lower and upper bound of A, respectively. Alternatively, we can also define an interval matrix by its center A_c = 1/2(A + A) and radius A_Δ = 1/2(A - A).
	Throughout the paper, we denote interval objects by bold lowercase (for one-dimensional intervals and interval vectors) and bold uppercase (for interval matrices) letters. The symbol 𝕀ℝ is used to denote the set of all (real) intervals.
	
	Furthermore, let us extend the classical definition of linear programs to the case of uncertain interval coefficients. We define an interval linear program (ILP) as a family of linear programs
	
    {minimize  c^T x 
    	 subject to  x ∈ℳ(A,b) : A ∈A, b ∈b, c ∈c}

	where ℳ(A,b) denotes the feasible set described by some linear constraints. For the sake of brevity, we usually write ILPs in the form of linear programs with interval coefficients (see (<ref>)–(<ref>) below for examples). A particular linear program in the family is called a scenario. Given an interval linear program, we can define its dual ILP as the family of all dual linear programs.
	
	Similarly, we can also generalize the notion of feasibility and optimality to the interval case. We say that a vector x ∈ℝ^n is a (weakly) feasible/optimal solution to the interval linear program, if there exists a scenario determined by the triplet A ∈A, b ∈b, c ∈c such that x is a feasible/optimal solution for the scenario (see <cit.> and <cit.> for an overview of the feasibility properties of interval linear systems). 
	The (weakly) feasible/optimal set is the set of all weakly feasible/optimal solutions of an ILP.
	We often omit the word “weakly”, since no confusion should arise in the paper.
	
	Considering the optimal objective values, we may be interested in the best and the worst value that can be achieved as optimal for some scenario of the given ILP. For a minimization program, these bounds are defined as 
	
    f(A, b, c) = inf{f(A,b,c): A ∈A, b ∈b, c ∈c},
       f(A, b, c) = sup{f(A,b,c): A ∈A, b ∈b, c ∈c},

	where f(A,b,c) denotes the optimal value of the corresponding linear program, allowing the values -∞ and ∞ for unbounded programs or infeasible programs.
	The interval [f(A, b, c), f(A, b, c)] is called the optimal value range.
	
	Due to the dependency problem, we usually assume that an ILP is given either in the general form
	
    [                minimize 5lc_1^T x_1 + c_2^T x_2;              subject to                    Ax_1                       +                    Bx_2                       =                    b_1,;                                            Cx_1                       +                    Dx_2                       ≤                    b_2,;                                                              2rx_1, x_2                       ≥                      0, ]

	or in one of the following forms often encountered in optimization problems:
	
    minimize c^T x  subject to Ax = b, x ≥ 0, I
       minimize c^T x  subject to Ax ≤b, II
       minimize c^T x  subject to Ax ≤b, x ≥ 0. III

	
	

§ TRANSFORMATIONS OF INTERVAL LINEAR PROGRAMS

	Let us now briefly review the basic transformations that are used in linear programming to convert a given program into the desired form. While some of them can also be applied to interval programs, other transformations may change the set of feasible or optimal solutions and affect the properties of the program. The effects of these transformations on the set of all optimal solutions and optimal values will be discussed in more detail in Sections <ref> and <ref>.
	
	

  
Changing the objective. A commonly used trick in linear programming is to switch the objective from maximization to minimization (or vice versa) by taking the opposite of the objective function. Since this transformation does not duplicate any coefficients, it can also be directly applied to interval programs: an interval objective maxc^T x can be equivalently rewritten as - (min -c^T x).
	
	

  
Adding slack variables. In order to convert inequality constraints to equations in a linear program, sign-restricted slack variables are added to the constraints. Analogously, we can transform an interval inequality system Ax ≤b into an interval system 
    Ax + Iy = b,  y ≥ 0.

	Again, the transformation does not duplicate any of the existing coefficients and only introduces some new crisp coefficients. Applying this transformation to a set of constraints results in an equivalent interval linear program, since each new scenario is equivalent to a corresponding scenario in the original interval system.
	
	

  
Splitting equations into inequalities. When changing a general linear program into an inequality-constrained form, we split each equation into two opposite inequalities. However, splitting an interval equation into interval inequalities while preserving all properties is not always possible, due to the dependency problem. Breaking dependencies among multiple occurrences of an interval coefficient leads to generating new scenarios that do not have a counterpart in the original problem. More precisely, while an interval equation a^T x = b consists of the scenarios a^T x = b with all possible choices of a ∈a, the system of two interval inequalities a^T x ≤ b, a^T x ≥ b corresponds to the (possibly larger) set of all scenarios in the form a_1^T x ≤ b, a_2^T x ≥ b with coefficients a_1, a_2 ∈a.
	
	

  
Imposing non-negativity. Another transformation used in linear programming is substituting the difference of two non-negative variables for a free variable. Along with introducing two new variables for each original free variables, the operation also duplicates the corresponding coefficients. This, again, leads to breaking the dependency in case of interval constraints: By replacing a constraint a^T x = b with a^T x^+ - a^T x^- = b and x^+, x^- ≥ 0, we create two independent occurrences of the interval coefficient a, which can take on different values in a particular scenario.
	
	

§ OPTIMAL SOLUTION SET UNDER TRANSFORMATIONS

	

 §.§ General Case

	In this section, we discuss the two types of transformations that can possibly change the properties of an interval linear program: splitting equation constraints and imposing non-negativity on the variables. First, we present examples of ILPs showing that these transformations can change the optimal solution set. Note that in both cases, the transformed interval program contains all of the original scenarios, therefore, the original optimal set is always a subset of the transformed one.
	
	We have seen in Section <ref> that splitting an interval equation into two inequalities can cause a dependency problem and possibly change the feasible or optimal solutions of an ILP. However, it was proved by <cit.> that this is not the case for the feasible set.
	
	
		A vector x ∈ℝ^n is a weakly feasible solution of an interval linear system Ax = b if and only if it is a weakly feasible solution of the system Ax ≤b, Ax ≥b.
	
	
	Even though the transformation preserves the weakly feasible solution set, the following example shows that creating new scenarios may, in fact, lead to expanding the set of optimal solutions.
	
	
		Consider the interval linear program
		
    [            minimize              2l-x_1;          subject to [0,1]x_1 - x_2 = 0,;                                x_2 ≤ 1,;                           x_1, x_2 ≥ 0. ]

		The optimal solution set of (<ref>) consists of all values with x_1 ∈ [1, ∞) and x_2 = 1. By splitting the equation [0,1]x_1 - x_2 = 0 into two inequalities, we allow the value for each coefficient to be chosen independently. This results in introducing additional scenarios into the problem, such as the scenario 
		
    1x_1 - x_2 ≤ 0,   0x_1 - x_2 ≥ 0

		with the optimal solution (0,0). Therefore, the optimal solution sets of the two problems are not equivalent.
	
	
	The second type of transformation affected by the dependency problem is restricting the sign of the variables. However, unlike all of the other transformations, replacing a free variable by a difference of two non-negative variables does not even preserve the feasible solution set of an interval linear program, as already noted by <cit.>. This implies that the set of optimal solutions may also change, in general.
	
	

 §.§ Special Case: Fixed Coefficient Matrix

	This section is devoted to a special class of interval linear programs, in which uncertainty only affects the objective function and the right-hand-side vector. We show that, unlike general interval linear programs, programs with a fixed coefficient matrix allow for all types of transformations while preserving the optimal solution set. Theorem <ref> presents the result for the transformation of splitting an equation into two opposite inequalities, i.e. converting a program of type (<ref>) with a fixed matrix into a program of type (<ref>).
	
	
		Let 𝒮(A,b,c) be the optimal solution set of an interval linear program of type (<ref>) with a fixed coefficient matrix given by the triplet (A, b, c). Then, 𝒮(A,b,c) is equal to the optimal solution set of the problem
		
    [   minimize    2lc^T x; subject to        A x      ≤b_1,;                  -A x    ≤ -b_2,;                     x       ≥ 0. ]

		with b_1 = b_2 = b.
	
	
		Let 𝒮(A',b',c) denote the optimal solution set of program (<ref>). Clearly, the inclusion 𝒮(A,b,c) ⊆𝒮(A',b',c) holds, since (<ref>) contains all the scenarios of (<ref>).
		
		On the other hand, let x' be an optimal solution of ILP (<ref>) for a scenario determined by the coefficient vectors c ∈c and b_1, b_2 ∈b satisfying 
		
    Ax' ≤ b_1,  -Ax' ≤ -b_2.

		Since we have, b_2 ≤ Ax' ≤ b_1, there exists b_3 ∈ [b_2, b_1] ⊆b with Ax' = b_3. We claim that x' is also an optimal solution of program (<ref>) for the scenario
		
    [   minimize    2lc^T x; subject to         Ax      =b_3,;                     x       ≥ 0. ]

		Suppose, for the sake of contradiction, that there exists another feasible solution x^* with c^T x^* < c^T x'. By the choice of b_3, the vector x^* is also feasible for scenario (<ref>). However, since the objective function is the same for both problems, this contradicts the assumption that x' is optimal in scenario (<ref>).
	
	
	Note that while the transformation preserves the optimal solutions, it may still change other properties of the program, such as the existence of infeasible scenarios or the range of optimal values, which will be discussed in more detail in Section <ref>. Theorem <ref> shows an analogous result for the transformation of free variables into non-negative variables.
	
	
		Let 𝒮(A, b, c) denote the optimal solution set of an interval linear program of type (<ref>) with a fixed coefficient matrix and let 𝒮(A', b, c') be the optimal solution set of the program
		
    [                minimize 2lc_1^T x^+ - c_2^T x^-;              subject to           A x^+ - A x^-                     ≤b,;                                        x^+, x^-                     ≥ 0 ]

		with c_1 = c_2 = c. Then, the following properties hold:
		
			
  * If x ∈𝒮(A,b,c), then there exists (x^+, x^-) ∈𝒮(A', b, c') with x = x^+ - x^-.
			
  * Conversely, if (x^+, x^-) ∈𝒮(A', b, c'), then x^+ - x^- ∈𝒮(A,b,c).
		
	
	
		Let x ∈𝒮(A,b,c) be an optimal solution for a scenario c ∈c, b ∈b. Decompose x into the non-negative vectors x^+ = max(0,x) and x^- = -min(0,x), where the operations max and min are understood entry-wise. The vectors satisfy x = x^+ - x^- and it is easy to see that the pair (x^+, x^-) is optimal in ILP (<ref>) for the scenario determined by the objective vector (c, -c) and the right-hand side b.
		
		Now, let (x^+, x^-) ∈𝒮(A', b, c') be optimal for some b ∈b and c_1, c_2 ∈c. By duality in linear programming, there exists a dual feasible vector y satisfying
		
    c_1^T x^+ - c_2^T x^- = b^T y,
          A x^+ - Ax^- ≤ b,  x^+ ≥ 0,  x^- ≥ 0,
          A^T y ≤ c_1,  -A^T y ≤ -c_2,  y ≤ 0.

		From the dual feasibility constraints, we have A^T y = c_3 for some c_3 ∈ [c_2, c_1] ⊆c. We will prove that x = x^+ - x^- is optimal for the scenario with objective vector c_3 and right-hand-side vector b in ILP (<ref>), by showing that it satisfies the system
		
    c_3^T x = b^T y,  Ax ≤ b,  A^T y = c_3,  y ≤ 0.

		Namely, it remains to show that c_3^T (x^+ - x^-) = b^T y holds. Complementary slackness implies that for each i ∈{1, …, n} we have
		
    (x^+)_i = 0 ∨ (c_1-A^T y)_i = 0,  and
          (x^-)_i = 0 ∨ (A^T y-c_2)_i = 0.

		If (x^+)_i > 0 and (x^-)_i > 0 for some index i, then we have (c_1)_i = (c_2)_i = (c_3)_i by the choice of c_3. For (x^+)_i = 0 and (x^-)_i > 0 we have (c_2)_i = (c_3)_i, and analogically, (c_1)_i = (c_3)_i for the symmetric case. By substituting into the equation
		
    c_1^T x^+ - c_2^T x^- = b^T y,

		we can see that the desired constraint is satisfied in all cases. Therefore, x^+ - x^- is an optimal solution of program (<ref>).
	
	
	Figure <ref> provides an overview of the transformations preserving the feasible and optimal solution set of general interval linear programs, as presented in Section <ref>. Note that ILPs of type (<ref>) are a special case of type (<ref>) and the transformation of type (<ref>) to type (<ref>) can be obtained by transitivity. As shown in Figure <ref>, all of the considered transformations preserve the optimal solution set for ILPs with a fixed coefficient matrix. Apart from the direct consequences of Theorem <ref> and Theorem <ref>, the remaining results follow again by transitivity.
	
	
	
	

§ OPTIMAL VALUES UNDER TRANSFORMATIONS

	Let us now discuss the effects of transformations on the set of all optimal values of an interval linear program and the optimal value range. Recall that the optimal value range refers to the interval [f, f], which is the smallest interval that encloses all optimal values. This interval may differ from the set of optimal values, since not all values in the range have to be attained as optimal for a scenario. Again, we consider the two transformations that can possibly lead to a dependency problem: splitting equations into inequalities and substituting a difference of two non-negative variables for a free variable.
	
	

 §.§ General Case

	We have already seen in Section <ref> that splitting an equation into two opposite inequalities may change the optimal solution set of an interval linear program. This also holds for the optimal value range, namely, the transformation can change the worst-case bound (f for a minimization program). Moreover, this is caused not only by creating an infeasible scenario resulting in f = ∞, but can also happen due to an expansion of the set of finite optimal values.
	example-1
	[continued]
		The optimal value range of the interval linear program
		
    [            minimize              2l-x_1;          subject to [0,1]x_1 - x_2 = 0,;                                x_2 ≤ 1,;                           x_1, x_2 ≥ 0. ]

		is the interval (-∞, -1]. However, by splitting the equation [0,1]x_1 - x_2 = 0 into two inequalities, the solution (0,0) becomes optimal and, thus, the value 0 belongs to the set of optimal values (and the optimal value range) of the transformed program. This shows that f = -1 is no longer the worst-case optimal value.
	
	
	On the other hand, we will now show that the transformation preserves the best-case optimal value f. The proof is a consequence of a result on a unified approach for computing the optimal value range by <cit.>. For the purposes of the following theorem, let us consider an interval linear program in the general form
	
    [                minimize 5lc_1^T x_1 + c_2^T x_2;              subject to                    Ax_1                       +                    Bx_2                       =                    b_1,;                                            Cx_1                       +                    Dx_2                       ≤                    b_2,;                                                              2rx_1, x_2                       ≥                      0. ]

	Let b = (b_1, b_2), c = (c_1, c_2) and let ℳ denote the set of all feasible solutions. Furthermore, let 𝒩 be the weakly feasible set of the dual ILP. Then, we can apply the formulas presented in Theorem <ref> to compute the optimal value range.
	
	
		We have
		
    f = inf{c_c^T x - c_Δ^T | x | : x ∈ℳ}.

		If f < ∞, then
		
    f = sup{b_c^T y + b_Δ^T | y | : y ∈𝒩}.

	
	
	Theorem <ref> proves that the transformation of splitting an equation into two opposite inequalities does not change the best-case optimal value of an interval linear program. The result implies that it is possible to convert an equation-constrained ILP of type (<ref>) into an inequality constrained ILP of type (<ref>), while preserving the best optimal value.
	
	 
		Transforming Ax = b into Ax ≤b, Ax ≥b does not change the best optimal value f of a minimization ILP.
	
	
		By Theorem <ref>, the best optimal value f of a general interval linear program can be found by minimizing the fixed objective function c_c^T x - c_Δ^T | x | over the set of all weakly feasible solutions. Since the applied transformation of splitting an equation into two inequalities does not change the weakly feasible set of an interval system (see Theorem <ref>), the value of f remains the same.
	
	
	By the property of strong duality in classical linear programming, we can also derive analogous results for the second considered transformation. For this case, let us first show that substituting the difference of two non-negative variables for a free variables can change the best-case bound f, as well as the set of optimal values.
	
	
		Consider the dual interval linear program to (<ref>), which can be rewritten into a minimization form as
		
    [   minimize     5l-y_2; subject to   [0,1]y_1                                ≤        -1,;                  -y_1          +        y_2          ≤         0,;                            2ry_2          ≤         0. ]

		The optimal value range of program (<ref>) is the interval [1, ∞). Let us now substitute the term y_1^+-y_1^- with y_1^+, y_1^- ≥ 0 for the free variable y_1. Analogously to the previous example, the set of optimal values changes and the best-case bound f = 1 is no longer valid (again, the value 0 becomes optimal).
	
	
	However, we can show that the transformation preserves the worst-case bound f. The proof uses the notion of strong feasibility, which also provides a characterization of finiteness of the bound f, as stated in Theorem <ref>. An interval linear program is said to be strongly feasible, if each scenario of the program is feasible.
	
	
		An interval linear program (in the general form) is strongly feasible if and only if f < ∞.
	
	
	
		Substituting x = x^+ - x^- with x^+, x^- ≥ 0 for a free variable x does not change the worst optimal value f of a minimization ILP.
	
	
		Let us denote by f and f^± the worst-case optimal value of the original program and the transformed program created by the introducing the substitution, respectively. 
		
		First, assume that f = ∞. Since all of the original scenarios are also included in the transformed ILP, the latter is a relaxation of the original program and f≤f^± holds. Therefore, we also have f^± = ∞.
		
		Further, let f < ∞ hold for the original interval program. Then, the program is strongly feasible. Since the conditions for strong feasibility of the original and the transformed program are equivalent for both equation and inequality constraints (see <cit.>), the latter is also strongly feasible and,  by Theorem <ref>, the property f^± < ∞ holds. By formula (<ref>) of Theorem <ref> we can calculate the worst-case optimal values by optimizing the objective function b_c^T y + b_Δ^T | y | over the dual feasible set of the respective ILPs. Note that applying the substitution to a free variable in the primal ILP corresponds to splitting an equation into two opposite inequalities in the dual ILP. As this preserves the set of feasible solutions (Theorem <ref>), the dual feasible sets of the original and the transformed program are equal, and thus f = f^±. 
	
	
	

 §.§ Special Case: Fixed Coefficient Matrix

	In Section <ref> we have seen that the optimal values and bounds of the optimal value range may change under some transformations. Therefore, it is natural to ask whether these properties are preserved at least for ILPs with a fixed coefficient matrix. Unfortunately, even for this special class of programs, the transformations may change the optimal value range, as shown by the following trivial examples.
	
	
		Consider the following interval linear programs:
		
			.5
				
    [   minimize   5l[0,1]x; subject to          x          ≥         1,;            ]

			
			.5
				
    [   minimize       5l-y; subject to          y          =     [0,1].;            ]

			
		
		The optimal value range of ILP (<ref>) is the interval [0,1], for ILP (<ref>) it is the opposite interval [-1,0]. By substituting x^+-x^- with non-negative variables x^+, x^- for the free variable x in (<ref>), we introduce an unbounded scenario (setting the objective to 0x^+ - 1x^-) and the best-case bound of the optimal value range changes to f = -∞.
		Similarly, by splitting the equation in (<ref>) into two opposite inequalities y ≤ [0,1], y ≥ [0,1], we create an infeasible scenario leading to f = ∞.
	
	
	However, note that there is an important difference between Example <ref> and the previous examples with an interval coefficient matrix. While in the examples of Section <ref> we have seen that a transformation may cause a change in the set of optimal values, in programs (<ref>) and (<ref>) the transformations only change one of the bounds in the optimal value range due to infeasibility or unboundedness of a newly introduced scenario.
	
	Let us now consider the set of all finite optimal values of an interval linear program with a fixed coefficient matrix. The following theorems prove that even though the optimal value range may still change when transforming a program with a fixed matrix, this can only be caused by the infinite optimal values for infeasible or unbounded scenarios and the finite optimal values remain the same.
	
	
		Transforming Ax = b into Ax ≤b, Ax ≥b does not change the set of all finite optimal values of an ILP with a fixed coefficient matrix.
	
	
		Clearly, all optimal values of the original program remain optimal in the transformed program. Let a solution x^* be optimal for a scenario given by c ∈c and b_1, b_2 ∈b in the transformed program. It is easy to see that x^* is also optimal for the scenario determined by c and b_3 = Ax^* of the original program, since it has the same objective function and a restricted feasible set. Therefore, the optimal value c^T x^* of the transformed ILP is also optimal for the original ILP.
	
	
	
		Substituting x = x^+ - x^- with x^+, x^- ≥ 0 for a free variable x does not change the set of all finite optimal values of an ILP with a fixed coefficient matrix.
	
	
		By strong duality of linear programming, the sets of finite optimal values of an interval linear program and its dual are the same. As introducing the substitution in the primal ILP corresponds to the transformation of splitting an equation into two inequalities in the dual ILP, applying Theorem <ref> yields the result.
	
	
	

§ CONCLUSION

	We addressed the dependency problem in transforming interval linear programs using the techniques known from classical linear programming. We showed that while it is possible to switch the objective of an interval linear program or add slack variables to convert inequalities into equations, other transformations are not always applicable to interval programs without affecting some of their properties.
	
	Namely, we considered three commonly used forms of interval linear programs. It was shown that the set of all optimal solutions may change, in general, under the transformations among these forms. Therefore, we also studied a special class of interval programs with a fixed coefficient matrix, for which we proved that all of the transformations preserve the optimal set.
	
	Furthermore, we also studied the effect of the transformations on the set of optimal values and the optimal value range of an interval linear program. We proved that the best-case optimal value f of a minimization program remains the same when an equation is split into two opposite inequalities, while the worst-case optimal value f is preserved when substituting the difference of two non-negative variables for a free variable. The complementary results do not hold, even in the case of a fixed coefficient matrix. However, the set of all finite optimal values does not change for transformations on the special class of programs.
	
	The results allow us to generalize the theory that was derived for a particular form of ILPs to all other types that can be obtained by a transformation respecting the studied properties. We believe that they also provide a better insight into the nature of the dependency problem in interval optimization.
	
	
	
	
	
	
	
	
	
	
	
abbrv      
	   
	
