Inverse optimization: towards the optimal parameter set of inverse LP with interval coefficients

Abstract

We study the inverse optimization problem in the following formulation: given a family of parametrized optimization problems and a real number called demand, determine for which values of parameters the optimal value of the objective function equals to the demand. We formulate general questions and problems about the optimal parameter set and the optimal value function. Then we turn our attention to the case of linear programming, when parameters can be selected from given intervals (“inverse interval LP”). We prove that the problem is NP-hard not only in general, but even in a very special case. We inspect three special cases—the case when parameters appear in the right-hand sides, the case when parameters appear in the objective function, and the case when parameters appear in both the right-hand sides and the objective function. We design a technique based on parametric programming, which allows us to inspect the optimal parameter set. We illustrate the theory by examples.

1 Introduction

1.1 Inverse optimization: definition

Consider the parametric optimization problem

$$\begin{aligned} \left\{ \min _{x \in \mathbb {R}^n} f(x,\theta ) \text { subject to } g(x,\theta ) \le 0\right\} , \quad \theta \in \varTheta , \end{aligned}$$

where the vector of parameters $\theta \in \mathbb {R}^k$ is assumed to be restricted into a given set $\varTheta \subseteq \mathbb {R}^k$, called admissible parameter set, $f: \mathbb {R}^{n} \times \mathbb {R}^k \rightarrow \mathbb {R}$ is the objective function and $g : \mathbb {R}^{n} \times \mathbb {R}^k \rightarrow \mathbb {R}^m$ is the constraint function.

Definition 1

The inverse optimization problem $(f,g,\varTheta ,f_0)$ is the following task: find $\theta _0 \in \varTheta$ such that

$$\begin{aligned} \min _{x \in \mathbb {R}^n}\{f(x,\theta _0): g(x,\theta _0) \le 0\} = f_0 \end{aligned}$$

or state that none exists. The number $f_0$ is called demand.

In other words, the formulation is as follows: given a parametrized optimization problem, a set of admissible parameters, and a demand, find admissible values of parameters such that the optimal value is equal to the demand or state that no such choice of parameters is possible.

Remark 1

We have started with the formal definition of the inverse optimization problem at the very beginning because the term “inverse optimization” is still unsettled within the optimization community and various authors use it in various meanings. For example, Ahmed and Guan (2005) consider the case of linear programming, where the objective function coefficients (cost coefficients) are to be chosen from a given admissible set to achieve that the optimal value is as close as possible to a specified value. This is near to our problem formulation and our paper can be understood as a contribution to this branch of research. Another well-known example is the work of Ahuja and Orlin (2001), who understand “inverse optimization” as follows: we are given a feasible point of an optimization problem and we are to perturb the objective function coefficients in order the feasible solution become optimal and the perturbation is in some sense minimal. In decision support, “inverse problems” are often understood as models of partial knowledge about the data which are to be completed or reconstructed. An important example is the problem of completion of comparison matrices in MCDM (Bozóki et al. 2010, 2011).

1.2 Motivation and examples

The following examples should illustrate some applications of our formulation of the inverse problem from Definition 1. In the examples, the case when $\varTheta$ is finite is trivial; the reader should think of the infinite case.

Let e denote the all-one vector.

Example A

Designing a network. The Network Flow Problem can be written as a linear programming problem the data of which are capacities of arcs of the network. Given admissible values of the capacities (say, intervals from which the capacities can be selected), we are to select the capacities to achieve a prescribed value of the maximum network flow.

Example B

Unit transportation prices. Let $a,b \ge 0$ be given. Consider the following version of the Transportation Problem:

$$\begin{aligned}&f_{TP}(\theta ) = \min _{x_{ij} \ge 0} \left\{ \sum _{i=1}^p \sum _{j=1}^{q} \theta _{ij}x_{ij}\ \Bigg |\ (\forall j = 1, \ldots , q) \sum _{i=1}^p x_{ij} = a_j,\right. \\&\quad \qquad \qquad \left. (\forall i = 1, \ldots , p) \sum _{j=1}^q x_{ij} = b_i\right\} . \end{aligned}$$

Now, given $\varTheta \subseteq \mathbb {R}^{p \times q}$ and $f_0$, we are to find $\theta \in \varTheta$ such that $f_{TP}(\theta ) = f_0$. In other words, we ask how to adjust unit transportation prices $\theta$ such that the transporter’s profit is at the prescribed level $f_0$. Here $\varTheta$ formalizes the admissible adjustments.

A nonlinear version of this problem can be considered when the objective function is nonlinear (e.g. when there is an incentive to transport larger volumes).

Example C

A version of the Matrix Casino problem (Mostafaee et al. 2015). Given a family $\varTheta$ of payoff matrices and a prescribed game value $f_0$, find the payoff matrix such that the game value is attained. In other words: given $\varTheta \subseteq \mathbb {R}^{p \times q}$ and $f_0 \in \mathbb {R}$, find $A \in \varTheta$ such that $\max _{\gamma ,x}\{\gamma \ |\ A^{\mathrm {T}}x \ge \gamma e,\ e^{\mathrm {T}}x = 1,\ x \ge 0\} = f_0$.

Example D

Data perturbation problems—an example from geometry. To find the minimum volume covering ellipsoid (MVCE) of a given family of data points $x_1, \ldots , x_p \in \mathbb {R}^q$, we are to solve the problem $f_{MVCE}(x_1, \ldots , x_p) = \min _{V,c}\{\det V\ |\ (\forall i = 1, \ldots , p)\ (x_i - c)^{\mathrm {T}}V^{-1} (x_i - c) \le 1,\ V \text { psd}\}$. Now $\frac{\pi ^{q/2}}{\varGamma (1+q/2)}\sqrt{f_{MVCE}}$ is the volume of the ellipsoid. Assume that we are given an admissible perturbation bound $\varepsilon > 0$ and we are to perturb the data points $x_1, \ldots , x_p$ in a way that the MVCE has a prescribed volume $f_0$. So we are solving the inverse problem with $\varTheta = [x_1 - \varepsilon e, x_1 + \varepsilon e] \times \cdots \times [x_p - \varepsilon e, x_p + \varepsilon e]$.

1.3 Optimal value function and optimal parameter set

The function

$$\begin{aligned} F(\theta ) = \min _{x \in \mathbb {R}^n}\{f(x,\theta ): g(x,\theta ) \le 0\} \end{aligned}$$

is called optimal value function. We admit that $F(\theta ) = \infty$, meaning that the problem $\min \{f(x,\theta _0): g(x,\theta _0) \le 0\}$ is infeasible, and $F(\theta _0) = -\infty$, meaning that the problem is unbounded.

The set

$$\begin{aligned} \varTheta ^* = \{\theta \in \varTheta : F(\theta ) = f_0\} \end{aligned}$$

is called optimal parameter set of the inverse optimization problem $(f,g,\varTheta ,f_0)$.

1.4 Problems and questions

In general, a study of inverse optimization leads to (at least) the following natural questions and problems, the knowledge about which currently is only partial; in particular, nonlinear problems deserve investigation.

Of course, answers and computational complexity of algorithms heavily depend on properties of the underlying optimization problem (on properties of f, g) and on the structure of $\varTheta$. This paper is a contribution to the case of linear programming and the case when $\varTheta$ is a box (i.e., each parameter of $\varTheta$ is restricted by a given lower and upper bound). However, as motivated by Examples A–D in Sect. 1.2, it is natural to state our questions and problems more generally, in a way applicable to nonlinear optimization as well. To “solve” a problem means: either design an efficient algorithm, or prove NP-hardness. In the case of NP-hardness, find special cases or additional conditions under which the problem is efficiently solvable.

• Problem 1. Decide whether $\varTheta ^* \ne \emptyset$. (Decide whether the inverse optimization problem has a solution.)

• Problem 2. Find some $\theta _0 \in \varTheta ^*$. (Find a solution.)

• Problem 3. Determine set-theoretic properties of $\varTheta ^*$ (e.g. whether it is bounded, connected, “large” in some well-defined sense etc.).

• Problem 4. Define an ordering $\le ^*$ on $\varTheta ^*$ and find $\theta _0 \in \varTheta ^*$ which is $\le ^*$-maximal. (If there are more solutions to the inverse optimization problem, define a relation “the solution $\theta _0$ is not worse than the solution $\theta _1$” and find the best solution with respect to this relation.)¹

• Problem 5. Describe, either exactly or approximately, the set $\varTheta ^*$ in a user-friendly way. (Example: in Sect. 4.1 we will show that in a particular situation the set $\varTheta ^*$ is a union of polytopes. Another example: when $\varTheta ^*$ is intricate, find a simple object—such as a box—which covers the set and is as tight as possible.²)

In design of algorithms for the inverse optimization problem, we often also face natural question about the optimal value function F. For example:

• Problem 6. Determine whether F is continuous on $\varTheta$.

• Problem 7. Determine the range of F over $\varTheta$.

• Problem 8. Determine a tight box enclosure of the range of F over $\varTheta$.

• Problem 9. Find extreme scenarios: find $\underline{\theta }, \overline{\theta } \in \varTheta$ such that $F(\underline{\theta }) = \inf \{f(\theta ): \theta \in \varTheta \}$ and $F(\overline{\theta }) = \sup \{f(\theta ): \theta \in \varTheta \}$.

• Problem 10. Determine whether F restricted to $\varTheta$ fulfills the Lipschitz condition (or another condition measuring that the function cannot be too “wild”).

Bibliographic remark. Some particular results are known for nonlinear programming where $\varTheta$ is in a form of intervals (Bhurjee and Panda 2012; Hladík 2011; Karmakar and Bhunia 2014). The linear case has been intensively investigated in the last years and considerably more results are known than for the nonlinear case; see, e.g., the surveys and recent developments in Fiedler et al. (2006), Hladík (2012, 2013, 2014a, b), Li et al. (2014), Luo et al. (2014), Mostafaee et al. (2015).

1.5 Illustration: how to construct an efficient method

To illustrate why questions about the optimal value function F are useful in design of algorithms, assume that

• (i) $\varTheta$ is compact and convex,

• (ii) F is continuous on $\varTheta$,

• (iii) F is a polynomial-time computable function,

• (iv) there are polynomial-time algorithms for finding $\underline{\theta }$ and $\overline{\theta }$.

Then we can solve the inverse optimization problem efficiently as follows. Let a demand $f_0$ be given. By (iii) and (iv) we can test $f_0 \in [F(\underline{\theta }), F(\overline{\theta })]$ and we have solved Problem 1. To solve Problem 2, we run Binary Search (known also as the Bisection Method) over the line segment $S_0 \,{:}{=}\, \{\lambda \underline{\theta } + (1 - \lambda )\overline{\theta } : 0 \le \lambda \le 1\} \subseteq \varTheta$; this is correct by (i). By (ii) F we find a point $\theta _0 \in S_0$ such that $|F(\theta _0) - f_0| < \varepsilon$ for an arbitrarily small $\varepsilon > 0$. The method is very simple:

Assumption (iii) assures that every step of the Binary Search is efficient. Then, an answer to Problem 10 will help us in estimation of the number of steps required to achieve $\varepsilon$-convergence, as shown by the following proposition.

Proposition 1

If, in addition to (i)–(iv), F is $\kappa$-Lipschitz on $\varTheta$, then $\varepsilon$-convergence is achieved after

$$\begin{aligned} \ell _0 \,{:}{=}\, \left\lceil \log _2\frac{\kappa \Vert \overline{\theta } - \underline{\theta }\Vert }{\varepsilon }\right\rceil \end{aligned}$$

(1)

steps.

Proof

Let S(x, y) denote a line segment with endpoints x, y. At the beginning of Binary Search we start with the line segment $S_0 = S(\underline{\theta }^0\,{:}{=}\,\underline{\theta }, \overline{\theta }^0\,{:}{=}\,\overline{\theta })$, which is then, in the $\ell$-th iteration, changed into a line segment $S(\underline{\theta }^\ell , \overline{\theta }^\ell )$. Let $\theta ^* \in S(\underline{\theta }^{\ell _0}, \overline{\theta }^{\ell _0})$ be such that $F(\theta ^*) = f_0$. In the $\ell _0$-th iteration we have

$$\begin{aligned} |F(\overline{\theta }^{\ell _0}) - f_0|= & {} |F(\overline{\theta }^{\ell _0}) - F(\theta ^*)| \le \kappa \Vert \overline{\theta }^{\ell _0} - \theta ^*\Vert \le \kappa \Vert \overline{\theta }^{\ell _0} - \underline{\theta }^{\ell _0}\Vert \\\le & {} \kappa \cdot 2^{-\ell _0}\Vert \overline{\theta } - \underline{\theta }\Vert \le \varepsilon . \end{aligned}$$

$\square$

We can refine the analysis even further. By (iv) we assume that $\underline{\theta }, \overline{\theta }$ can be computed by a polynomial-time algorithm. Thus there exists a polynomial p such that $\Vert \underline{\theta }\Vert \le 2^{p(L)}$ and $\Vert \overline{\theta }\Vert \le 2^{p(L)}$, where L is the bit-size of the input (i.e., the size of the data structure representing $\varTheta$). Then $\Vert \overline{\theta } - \underline{\theta }\Vert \le 2^{p(L) + 1}$ and (1) tells us that $\varepsilon$-convergence is achieved in a polynomial number of steps, or more precisely, we have an algorithm working in $O(p(L)\log \frac{\kappa }{\varepsilon })$ steps.

1.6 Discussion: continuity of the optimal value function

It was pointed out by one of the referees that the question whether the assumptions (i)–(iv) from the previous section are fulfilled is highly nontrivial and deserves separate research. Of course, the answer depends on the particular problem under consideration. As an illustration we consider the continuity assumption (ii) in case of linear programming. For some classes of linear programs, the continuity assumption is satisfied, and for some it is not; we refer to two examples from Černý (2015a, b). First consider the problem

$$\begin{aligned} F(\theta _1,\theta _2)= & {} \min \{-x_2\ |\ -x_1 + \theta _1 x_2 \le 0, x_1 \le 0, x_2 \le \theta _2\},\nonumber \\ \left( {\begin{array}{c}\theta _1\\ \theta _2\end{array}}\right) \in \varTheta= & {} [-1,1] \times [0, 10]; \end{aligned}$$

(2)

its optimal value function is discontinuous as shown in Fig. 1. The second example is the class of matrix-game LPs (see Example C from Sect. 1.2); in this case, the optimal value function is continuous and nondecreasing in every variable. The instance

$$\begin{aligned} F(\theta _1, \theta _2)= & {} \max _{\gamma ,x}\left\{ \gamma \ \Bigg | \ \left( \begin{matrix} 0 &{} \theta _1 &{} -1 \\ -1 &{} 0 &{} 1 \\ \theta _2 &{} -1 &{} 0 \end{matrix}\right) ^{\mathrm {T}}x \ge \gamma e,\ e^{\mathrm {T}}x = 1,\ x \ge 0\right\} ,\nonumber \\ \left( {\begin{array}{c}\theta _1\\ \theta _2\end{array}}\right) \in \varTheta= & {} [-2,2] \times [-2,2], \end{aligned}$$

(3)

which can be understood as a “perturbation” of the Rock-Scissors-Paper game, is depicted in Fig. 2.

Fig. 1

Illustration of (2)

Fig. 2

Illustration of (3)

Some sufficient conditions for continuity of the objective value function of LP are available, but as far as the authors are aware, a unified characterization of continuity is still not known. And in case of nonlinear problems, even less is known. But there is some progress: except for the seminal paper (Wets 1985), in Mostafaee et al. (2015) a particular sufficient condition is proven, enabling us to prove continuity for various classes of LPs. But, on the contrary, we are aware of many problems where the condition fails, and for other classes, we know that checking that condition is equivalent to solving an NP-hard problem. So there are still pros and cons, showing that further refinements and derivation of new sufficient conditions for continuity is of a great importance, both for linear and nonlinear programming problems.

2 Contribution of this paper to the general framework

This paper is a contribution to the general framework described in previous sections for the case of linear programming, when the admissible space $\varTheta$ is given as a family of intervals of admissible values of LP-coefficients. Before we give a precise statement, we need some definitions.

2.1 Interval matrices and vectors

An interval $(m \times n)$-matrix ${{\varvec{A}}}$ is defined as a family of matrices

$$\begin{aligned} {{\varvec{A}}} = [\underline{A}, \overline{A}] = \{A \in \mathbb {R}^{m \times n}: \underline{A} \le A \le \overline{A}\}, \end{aligned}$$

where the relation “$\le$” is understood componentwise. The boundary matrices $\underline{A}, \overline{A}$ are called endpoints. The center and radius are defined as, respectively,

$$\begin{aligned} {{\varvec{A}}}^c = \tfrac{1}{2}(\overline{A} + \underline{A}), \qquad \quad {{\varvec{A}}}^\varDelta = \tfrac{1}{2}(\overline{A} - \underline{A}). \end{aligned}$$

Interval vectors are one-column interval matrices and are denoted ${{\varvec{a}}}, {{\varvec{b}}}, \ldots$. The space of all $(m \times n)$-interval matrices is denoted ${\mathbb {IR}}^{m\times n}$. Similarly, ${\mathbb {IR}}^n$ denotes the space of n-dimensional interval vectors.

We say that an interval matrix ${{\varvec{A}}}$ is crisp if $\underline{A} = \overline{A}$. The absolute value |A| of a matrix A is understood componentwise.

For more information on computation with interval matrices, we refer the readers to books (Alefeld and Herzberger 1983; Moore et al. 2009; Neumaier 1990).

2.2 Inverse LP with interval coefficients

We consider the linear programming problem in the form

$$\begin{aligned} \min c^{\mathrm {T}}x \text { subject to }Ax = b,\ x \ge 0. \end{aligned}$$

(4)

Let the admissible space $\varTheta$ be given as a triple $({{\varvec{A}}} \in {\mathbb {IR}}^{m \times n}, {{\varvec{b}}} \in {\mathbb {IR}}^{m}, {{\varvec{c}}}\in {\mathbb {IR}}^n)$. We study the inverse optimization problem in the following form: given a demand $f_0$, find $A \in {{\varvec{A}}}$, $b\in {{\varvec{b}}}$, $c\in {{\varvec{c}}}$ such that $f_0 = \min \{c^{\mathrm {T}}x: Ax = b,\ x \ge 0\}.$ In other words, we study the case when we can select every parameter of the LP (4) from a given interval.

Now it is natural to write the optimal value function in the form

$$\begin{aligned} F(A, b, c) = \min \{c^{\mathrm {T}}x : Ax = b, x \ge 0\} \end{aligned}$$

and the optimal parameter space in the form

$$\begin{aligned} \varTheta ^* = \{(A, b, c): A \in {{\varvec{A}}},\ b \in {{\varvec{b}}},\ c \in {{\varvec{c}}},\ F(A,b,c) = f_0\}. \end{aligned}$$

3 A negative result

In this section we prove that the inverse problem stated in the previous section is NP-hard. We prove even a stronger (and surprising) result that even a very special case of the general problem is NP-hard, namely when we restrict ourselves to ${{\varvec{A}}}$ and ${{\varvec{c}}}$ crisp.

Theorem 1

Given $A \in \mathbb {R}^{m \times n}$, ${{\varvec{b}}}\in {\mathbb {IR}}^{m}$, $c \in \mathbb {R}^n$ and $f_0 \in \mathbb {R}$, checking whether there is $b\in {{\varvec{b}}}$ such that $F(A,b,c) = f_0$ is an NP-complete problem.

Proof

By Fiedler et al. (2006), checking solvability of the system

$$\begin{aligned} |Ax|\le e,\ e^T|x|\ge 1 \end{aligned}$$

(5)

is an NP-complete problem on a class of non-negative positive definite matrices. Let such A be given and consider the LP

$$\begin{aligned} \max b^Tx {\ \ \text{ subject } \text{ to }\ \ }-e\le Ax\le e, \end{aligned}$$

where $b\in [-e,e]$, A is non-negative positive definite, and the desired optimal value is $f_0=1$. Notice that this linear program is always feasible ($x=0$ is a feasible point) and bounded (by positive definiteness of A), so it has an optimal solution and finite optimal value for each $b\in [-e,e]$.

We claim that (5) is solvable iff there is $b\in [-e,e]$ such that $f_0 = 1$ is attained as the optimal value.

“If.” Suppose that $f_0 = 1$ is attained as the optimal value for $b\in [-e,e]$ and the corresponding optimal solution $x^*$. Then

$$\begin{aligned} 1=f_0=b^Tx^*\le |b|^T|x^*|\le e^T|x^*|. \end{aligned}$$

That is, $x^*$ solves (5).

“Only if.” Suppose to the contrary that (5) is solvable, but $f_0 = 1$ is optimal value for no $b \in [-e,e]$. If there is $K>1$ such that K is the optimal value for some $b\in [-e,e]$, then $f_0 = 1$ is attained for $b'\,{:}{=}\,\frac{1}{K}b$. So we have proved that all optimal values are $<1$. By solvability of (5) we derive a contradiction: since if x solves (5) and $b\,{:}{=}\,{{\mathrm{sgn}}}(x)$, then x is feasible solution to the linear program and $b^Tx=e^T|x|\ge 1$. Thus the optimal value is at least 1. $\square$

Remark 2

A related result was shown by Gabrel et al. (2010), who proved that it is NP-hard to determine the worst case optimal value $\max _{b\in {\varvec{b}}}F(A,b,c)$.

4 Good news

Theorem 1 shows that in general, inverse LP with interval coefficients is a computationally intractable problem, even in the special case with ${{\varvec{A}}}, {{\varvec{c}}}$ crisp. Though the general result is negative, the situation is not quite disappointing and much can be achieved in a computationally efficient way.

4.1 Case 1: only right-hand sides contain intervals

Here we continue with the case when intervals are only in the right-hand sides (i.e., $A \in \mathbb {R}^{m \times n}$, ${{\varvec{b}}} \in {\mathbb {IR}}^{m}$, $c \in \mathbb {R}^n$). This problem has been partially addressed in Mostafaee et al. (2015).

We will use the usual LP-notation: if B is a basis, $A_B$ denotes the basic columns of A, $A_N$ denotes the nonbasic columns of A. Similarly with $c_B$, $c_N$.

Definition 2

(Basis decomposition of $\varTheta ^*$) Let B be a basis. The B-class of $\varTheta ^*$, denoted $\varTheta ^*_B$, is the set of vectors $b^* \in {{\varvec{b}}}$ such that $F(A, b^*, c) = f_0$ and B is an optimal basis of the LP

$$\begin{aligned} \min c^{\mathrm {T}}x\text { subject to }Ax = b^*,\ x \ge 0. \end{aligned}$$

(6)

This definition was inspired by the theory of multiparametric programming, see Gal (1979), Gal and Greenberg (1997), Hladík (2010), Nožička et al. (1974).

The proof of the following proposition is straightforward.

Proposition 2

Let B be a basis. Now $b \in \varTheta ^*_B$ if and only if the following conditions hold:

• (a) domain condition: $b\in {{\varvec{b}}}$,

• (b) nonnegativity condition: $A_B^{-1}b\ge 0$,

• (c) optimality condition: $c_N^T-c_B^{}A_B^{-1}A_N^{}\ge 0$,

• (d) optimal value condition: $c_B^{}A_B^{-1}b=f_0$.

Corollary 1

$\varTheta ^*_B$ is a polytope.

Proof

Conditions (a)–(d) are linear with respect to b and ${{\varvec{b}}}$ is bounded. $\square$

Corollary 2

If the problem (4) is not dual degenerate, then the sets $\varTheta ^*_B$, $\varTheta ^*_{B'}$ for different bases B and $B'$ are either disjoint or meet at their faces only.

Proof

Due to condition (d) of Proposition 2, the possible non-facial intersection of $\varTheta ^*_B$ and $\varTheta ^*_{B'}$ can happen only if $c_BA_B^{-1}=c_{B'}A_{B'}^{-1}$. This condition, however, implies degeneracy of the dual problem $\max b^Ty \text{ subject } \text{ to } A^Ty\le c$. $\square$

Clearly we have

$$\begin{aligned} \varTheta ^* = \bigcup _{B\ \text { is a basis }} \varTheta ^*_B. \end{aligned}$$

(7)

It follows that $\varTheta ^*$ can be written as a (not necessarily convex) union of polytopes, each of which corresponds to one basis, which is an optimal basis for some class of admissible LPs the objective value of which is $f_0$.

Example 1

Consider the LP

$$\begin{aligned} \min -x_1 - 2x_2 \text { subject to } x_1 + 4x_2 + s_1&= b_1, \\ 2x_1 + 3x_2 + s_2&= b_2, \\ 3x_1 + 2x_2 + s_3&= 4, \\ 4x_1 + x_2 + s_4&= 6, \\ x \ge 0,\ s \ge 0,&\end{aligned}$$

where $b_1 \in [0,8]$ and $b_2 \in [0, 8]$. The admissible set $\varTheta = [0,8] \times [0,8]$ is shown in Fig. 3, together with contour lines of the optimal value function F (which is now understood as a function of $b_1, b_2$). Given a demand $f_0$, the optimal parameter set $\varTheta ^*$ is a contour line of F. The figure illustrates Corollary 1 and the fact (7): each contour line is a connection of line segments.

Fig. 3

Illustration of Example 1

An algorithm for determining the “radius” of $\varTheta ^*$ in a given direction $b^{\varDelta }$. (The algorithm gives us at least partial information about the “width” of $\varTheta ^*$ in the direction $b^\varDelta$, giving a partial answer to Problem 5 of Sect. 1.4.) Here, the “radius” is understood as follows: given $b^* \in \varTheta ^*$ and $\beta ^{\varDelta }$, we are to determine the maximum t such that $b^* + tb^{\varDelta } \in \varTheta ^*$.

Let $b^* \in \varTheta ^*$ be given (e.g. found by the method of Sect. 1.5) and let B be an optimal basis of (6). For the sake of simplicity assume that B is unique (or we must enumerate all optimal bases). Let a perturbation vector $b^{\varDelta }$ be given. If

$$\begin{aligned} c_B^{}A_B^{-1}b^{\varDelta }=0, \end{aligned}$$

then we can move in $\varTheta ^*_B$ from $b^*$ in direction $b^{\varDelta }$ since $b^*+tb^{\varDelta }$ is admissible for a sufficiently small $t\ge 0$.

Step 1. Finding a boundary point of $\varTheta ^*_B$. The furthest admissible point is computed as

$$\begin{aligned} t^*\,{:}{=}\,\max t {\ \ \text{ subject } \text{ to }\ \ }b^*+tb^{\varDelta }\in {{\varvec{b}}},\ A_B^{-1}(b^* + tb^{\varDelta }) \ge 0, \end{aligned}$$

(8)

which is an easy optimization problem. The corresponding point is then $b^{**} \,{:}{=}\, b^*+t^*b^{\varDelta }$. This point lies on the boundary of $\varTheta ^*_B$.

Step 2. Basis switch. If the LP

$$\begin{aligned} \min c^{\mathrm {T}}x\text { subject to }Ax = b^{**},\ x \ge 0 \end{aligned}$$

has another optimal basis $B'$ such that $c_{B'}A_{B'}^{-1}b^{\varDelta }=0$, we set $B \,{:}{=}\, B', b^* \,{:}{=}\, b^{**}$ and repeat (8). In other words, we have switched from $\varTheta ^*_B$ to $\varTheta ^*_{B'}$ and we can move further in the direction $b^{\varDelta }$ through $\varTheta ^*_{B'}$. We repeat until we reach the boundary of $\varTheta ^*$.

4.2 Case 2: only the objective function contains intervals

Suppose that only ${{\varvec{c}}}$ is interval, and the other coefficients in A and b are fixed values. Complexity of checking whether there is some $c\in {{\varvec{c}}}$ such that (4) is an open problem. We can, however, state the following interesting special case.

Proposition 3

If the feasible set $\{x: Ax = b, x \ge 0\}$ is bounded, then checking whether there is some $c^*\in {{\varvec{c}}}$ such that $F(A,b,c^*) = f_0$ holds true is a polynomial time problem.

Proof

Under the assumption, the optimal value function is continuous (Wets 1985), and the optimal value set is $[{\underline{{f}}},{\overline{{f}}}]$, where

$$\begin{aligned} {\underline{{f}}}&=\min {\underline{{c}}}^Tx {\ \ \text{ subject } \text{ to }\ \ }Ax=b,\ x\ge 0,\\ {\overline{{f}}}&=\min {\overline{{c}}}^Tx {\ \ \text{ subject } \text{ to }\ \ }Ax=b,\ x\ge 0. \end{aligned}$$

$\square$

Now we proceed similarly as in Sect. 4.1. The detailed analysis would be similar. We describe the main idea. Let B be an optimal basis (assuming that it is unique for simplicity) and let $x^*$ be the corresponding optimal solution of

$$\begin{aligned} \min (c^*)^{\mathrm {T}}x\text { subject to }Ax = b,\ x \ge 0, \end{aligned}$$

where $c^*\in \varTheta ^*$ is given. This problem was considered by Mostafaee et al. (2015). Now, the set of $c\in {{\varvec{c}}}$ for which $f_0$ is the optimal value and $x^*$ remains optimal is described by

$$\begin{aligned} {\underline{{{c}}}}\le c\le {\overline{{{c}}}},\ \ c^Tx^*=f, \ \ c_N^T-c_B^{}A_B^{-1}A_N^{}\ge 0. \end{aligned}$$

This is a polytope. It follows that $\varTheta ^*$ is a union of polytopes, each of which corresponds to a particular optimal basis.

Let a perturbation vector $c^{\varDelta }$ such that $(c^{\varDelta })^Tx^*=0$ be given. Then we can move in $\varTheta ^*$ from $c^*$ in direction $c^{\varDelta }$ since $c^*+tc^{\varDelta }$ is admissible for a sufficiently small $t\ge 0$. The furthest admissible point is computed as

$$\begin{aligned} t^*\,{:}{=}\,\max t {\ \ \text{ subject } \text{ to }\ \ }c^*+tc^{\varDelta }\in {{\varvec{c}}},\ c_N^T-c_B^{}A_B^{-1}A_N^{}\ge 0, \end{aligned}$$

(9)

which is an easy optimization problem. The corresponding point is then $c^{**}\,{:}{=}\,c^*+t^*c^{\varDelta }$. Now we perform the basis-switch step: we find another optimal basis $B'$ (or: enumerate optimal bases) of the LP

$$\begin{aligned} \min (c^{**})^{\mathrm {T}}x\text { subject to }Ax = b,\ x \ge 0, \end{aligned}$$

and its corresponding solution $x^{**}$. If $(c^{\varDelta })^Tx^{**}=0$, we can set $x^*\,{:}{=}\,x^{**}$ and repeat (9), until we reach the boundary of $\varTheta ^*$.

4.3 Case 3: interval right-hand side and the objective function

Herein, we suppose that both ${{\varvec{b}}}$ and ${{\varvec{c}}}$ are interval, and the entries of A are fixed. Now, the problem is more complicated as the optimal value condition $c_B^{}A_B^{-1}b=f_0$ is nonlinear.

Some specific subproblems are, however, still easily solvable. Let $x^*$ be an optimal solution of the LP

$$\begin{aligned} \min (c^*)^{\mathrm {T}}x \text { subject to } Ax = b^*, x \ge 0, \end{aligned}$$

where $b^*\in {{\varvec{b}}}$ and $c^*\in {{\varvec{c}}}$ are such that $F(A,b^*,c^*) = f_0$ and let B be the corresponding optimal basis. Let perturbation vectors $b^{\varDelta }$ and $c^{\varDelta }$ be given, and consider the problem of what is the maximal distance we can move from $b^*,c^*$ in the direction of $b^{\varDelta },c^{\varDelta }$ in $\varTheta ^*$. (This is another contribution to Problem 5 of Sect. 1.4.) Formally find the maximal $t\ge 0$ such that for $b(t)=b^*+tb^{\varDelta }$ and $c(t)=c^*+tc^{\varDelta }$ we have

• (a) domain condition: $b(t)\in {{\varvec{b}}}$ and $c(t)\in {{\varvec{c}}}$,

• (b) nonnegativity condition: $A_B^{-1}b(t)\ge 0$,

• (c) optimality condition: $c_N^T(t)-c_B^{}(t)A_B^{-1}A_N^{}\ge 0$,

• (d) optimal value condition: $c_B^{}(t)A_B^{-1}b(t)=f_0$.

The conditions describe a B-class $\varTheta ^*_B$ of $\varTheta ^*$ corresponding to the basis B.

Condition (d) is the only nonlinear one. The impact of the nonlinearity is that $\varTheta ^*$ can be no more described as a union of polytopes corresponding to particular bases. This is illustrated by the following example.

Example 2

Consider the LP

$$\begin{aligned} \min -c_1x_1 - 2x_2 \text { subject to }&x_1 + 4x_2 + s_1 = b_1, \\&2x_1 + 3x_2 + s_2 = 3, \\&3x_1 + 2x_2 + s_3 = 4, \\&4x_1 + x_2 + s_4 = 6, \\&x \ge 0,\ s \ge 0, \end{aligned}$$

where $c_1 \in [0,5]$ and $b_1 \in [0, 4]$. Given a demand $f_0$, the optimal parameter set $\varTheta ^*$ is a contour line of the optimal value function F, see Fig. 4.

Fig. 4

Illustration of Example 2

In spite of the nonlinearity in the optimal value condition (d), we can use the following trick. We reformulate (d) as follows:

$$\begin{aligned} f_0&=c_B^{}(t)A_B^{-1}b(t) = (c^*+tc^{\varDelta })_B^{}A_B^{-1}(b^*+tb^{\varDelta })\\&= c^*_BA_B^{-1}b^* +t\left( c^*_BA_B^{-1}b^{\varDelta }+c^{\varDelta }_BA_B^{-1}b^*\right) +t^2c^{\varDelta }_BA_B^{-1}b^{\varDelta }. \end{aligned}$$

Using $f_0=c^*_BA_B^{-1}b^*$, we get

$$\begin{aligned} 0=\left( c^*_BA_B^{-1}b^{\varDelta }+c^{\varDelta }_BA_B^{-1}b^*\right) +tc^{\varDelta }_BA_B^{-1}b^{\varDelta }, \end{aligned}$$

from which

$$\begin{aligned} t^*=-\frac{c^*_BA_B^{-1}b^{\varDelta }+c^{\varDelta }_BA_B^{-1}b^*}{c^{\varDelta }_BA_B^{-1}b^{\varDelta }}. \end{aligned}$$

(10)

Thus, the only possible perturbation length is (10) provided such $t^*$ is admissible. Of course, in the degenerate case

$$\begin{aligned} 0=c^*_BA_B^{-1}b^{\varDelta }+c^{\varDelta }_BA_B^{-1}b^* =tc^{\varDelta }_BA_B^{-1}b^{\varDelta } \end{aligned}$$

the optimal value condition holds for any t, so we easily determine the maximal admissible t from the linear conditions (a)–(c).

Remark 3

Both cases are illustrated in Fig. 4: the degenerate case can be illustrated by the straight segments of contour lines, while the non-degenerate case, when only the step of length (10) can be performed, corresponds to the nonlinear segments of contour lines.

Remark 4

Note that this analysis holds only in the B-class $\varTheta ^*_B$ of $\varTheta ^*$. Currently we do not know how to find a point of basis switch, which would allow us to inspect not only $\varTheta ^*_B$, but the entire optimal parameter set $\varTheta ^*$. This is a tempting research question.

5 Conclusion

First, we stated ten general questions about the optimal parameter set of the general inverse optimization problem and its associated optimal value function. Then main question is: how does the set $\varTheta ^*$ of all solutions look? Then we inspected the case of inverse linear programming with interval coefficients. We proved a general negative complexity-theoretic result. This is a justification for analysis of particular cases which are easier-to-handle. We studied the case of (a) interval right-hand sides, (b) interval objective function and (c) the case then both the right-had sides and the objective function contains intervals. We proved that in case (a) and (b), the set $\varTheta ^*$ is a union of polytopes corresponding to optimal bases, giving an insight into the structure of $\varTheta ^*$. Based on this description, we proposed a technique, derived from parametric programming, allowing us to inspect the solution set $\varTheta ^*$ in a pre-selected direction.