. Author manuscript; available in PMC: 2022 Jun 8.

Published in final edited form as: Optim Lett. 2019;13(2):281–294. doi: 10.1007/s11590-019-01394-0

Inverse optimization for multi-objective linear programming

Mostafa Naghavi ¹, Ali Asghar Foroughi ², Masoud Zarepisheh ³

PMCID: PMC9175571 NIHMSID: NIHMS1784924 PMID: 35685276

Abstract

This paper generalizes inverse optimization for multi-objective linear programming where we are looking for the least problem modifications to make a given feasible solution a weak efficient solution. This is a natural extension of inverse optimization for single-objective linear programming with regular “optimality” replaced by the “Pareto optimality”. This extension, however, leads to a non-convex optimization problem. We prove some special characteristics of the problem, allowing us to solve the non-convex problem by solving a series of convex problems.

Keywords: Multi-objective linear programming, Linear programming, Inverse optimization, Efficiency

1. Introduction

Multi-objective linear programming (MOLP) deals with multi-objective optimization problems where all the objectives and constraints are linear. These problems arise in many fields, including engineering, finance, and medicine [3, 12, 21]. When it comes to multi-objective optimization, a typical optimality concept used in single-objective optimization is replaced with the Pareto optimality. A feasible solution is Pareto optimal if it is impossible to improve some objective functions without compromising others.

Inverse optimization (IO), studied by Burton and Toint [6] in 1992, is a new field of optimization dealing with problems in which some of the parameters may not be precisely known, only estimates of these parameters may be known. Instead, it is possible that some information about the problem, such as some solutions or some values for objective function, are given from experience or from some experiments. Thus, the aim is to determine values of the parameters by using this information. In the past years, several types of IOs have been studied by the researchers [7, 13, 16, 23].

This paper deals with an important type of IO in which we are looking for the least problem modifications in order to make a given feasible solution of the problem an optimal solution. In another words, if $\hat{x}$ is a feasible solution of the problem, how can we modify the problem, for example by changing the cost function, as least as possible according to some metrics so that $\hat{x}$ becomes an optimal solution. This problem has been well studied for different types of single-objective optimization problems including linear programming [1, 2, 22, 23], combinatorial optimization [13], conic programming [14], integer programming [19], and countably infinite linear programming [11]. Roland et al. [18] studied inverse optimization for a special class of multi-objective combinatorial optimization problems where the least modification of the criteria matrix is sought to turn a set of feasible points to a set of Pareto optimal points. They demonstrated that the inverse multi-objective combinatorial optimization under some norms can be solved by algorithms based on mixed integer programming. This paper deals with inverse multi-objective linear programming (IMOLP) where the least criteria matrix modification is sought to turn a given feasible solution into a Pareto optimal solution.

For IO problems studied in this paper, and all the aforementioned papers, while a feasible point $\hat{x}$ could be in principle an interior point of feasible region, this would turn the IO problem into an evident problem where the cost function is modified to zero so that all feasible solutions, including $\hat{x}$ , would become weakly efficient. There is a new type of IO, inspired by noisy data appear in some applications, that has been recently studied by Chan et al. [9] where $\hat{x}$ could be an interior point of the feasible region. For this type of IO, both cost vector and $\hat{x}$ are modified to achieve the optimality. Chan et al. [7,8] have also studied a very special multi-objective version of their IO, inspired by application in radiotherapy cancer treatment, where the criteria matrix is remained unchanged and the objective weights are sought to turn a given point $\hat{x}$ , that could be an interior point or even infeasible point, into a near-optimal solution. This paper deals with the natural extension of a classical IO problem, introduced earlier, for multi-objective programs where the least perturbations in criteria matrix is sought to turn a feasible solution into a Pareto optimal solution.

The paper is organized as follows. Section 2 includes some preliminaries. Section 3 reviews inverse linear programming (ILP), and Section 4 generalizes ILP to inverse multi-objective linear programming (IMOLP) and discusses the non-convexity of the problem. Afterwards, some special characteristics of IMOLP are proved, providing necessary tools to develop an efficient convex-optimization-based algorithm. A simple numerical example and a geometrical interpretation are also provided in Section 4. And finally, Section 5 concludes the paper.

2. Preliminaries

In this paper, the row and column vectors are distinguishable from each other by text. Let $ℝ^{n}$ and $ℝ^{m \times n}$ denote the set of all real n-vectors and m × n matrices respectively, and a_i denotes the i-th row of the matrix A. For $x \in ℝ^{n}$ , ‖x‖_p denotes the ℓ_p-norm of the vector x. Consider the following two problems:

m i n {c x ∣ x \in S},

(LP(c))

m i n {C x = (c_{1} x, \dots, c_{k} x) ∣ x \in S},

(MOLP(C))

where $A \in ℝ^{m \times n}$ , $C \in ℝ^{k \times n}$ , $c \in ℝ^{n}$ , $b \in ℝ^{m}$ , and $S = {x \in ℝ^{n} ∣ A x \geq b}$ is the feasible region. A feasible point $\hat{x} \in S$ is called weak efficient or weak Pareto optimal of MOLP(C) if there exists no x ∈ S such that $C x < C \hat{x}$ . All the ordering in this paper are component-wise. The set of all weak efficient points of MOLP(C) is denoted by S_we(C). The set of all optimal solutions of LP(c) is denoted by S_o(c).

For a set $y = {y_{1}, \dots, y_{l}} \subseteq ℝ^{n}$ , cone(y) and conv(y) denote the conic and convex hull of y defined as:

c o n e (y) = {x \in ℝ^{n} ∣ x = \sum_{i = 1}^{l} β_{i} y_{i}, β_{i} \geq 0},

c o n v (y) = {x \in ℝ^{n} ∣ x = \sum_{i = 1}^{l} β_{i} y_{i}, \sum_{i = 1}^{l} β_{i} = 1, β_{i} \geq 0} .

For a feasible point $\hat{x} \in S$ , let $I (\hat{x}) = {i ∣ a_{i} \hat{x} = b_{i}}$ be the set of all active constraints indices at $\hat{x}$ . The conic hull of the set ${a_{i} ∣ i \in I (\hat{x})}$ is:

\hat{K} = c o n e ({a_{i} ∣ i \in I (\hat{x})}) = {x \in ℝ^{n} ∣ x = \sum_{i \in I (\hat{x})} β_{i} a_{i}, β_{i} \geq 0} .

As we would see in the next sections, $\hat{K}$ plays an important role in the optimality of $\hat{x}$ for LP(c) and MOLP(C).

Definition 1

The distance between two non-empty sets $A, B \subseteq ℝ^{n}$ is defined as:

d (A, B) = i n f {‖ x - y ‖_{p} ∣ x \in A, y \in B} .

It is well-known that for a compact set A and a closed set B, we have [5]:

d(A,B)= min{‖x−y‖_p |x ∈ A,y ∈ B}.
A∩B = ∅ if and only if d(A,B) > 0.

3. Inverse single-objective linear programming

This section reviews an inverse single-objective linear programming (ILP) problem under ℓ_p-norm with the cost vector modification. This problem has been initially studied by Zhang and Liu [22, 23] under ℓ₁-norm and ℓ_∞-norm, and later been extended to the weighted norms by Ahuja and Orlin [1].

An ILP problem under ℓ_p-norm for LP(C) looks for the minimal modification in the cost vector in order to make a given feasible point $\hat{x}$ an optimal solution. This can be formulated as follows:

\begin{array}{l} m i n ‖ c - \hat{c} ‖_{p} \\ s . t . \hat{x} \in S_{o} (\hat{c}), \\ \hat{c} \in ℝ^{n} . \end{array}

ILP(c,^𝑥)

Using the Karush-Kuhn-Tucker (KKT) optimality conditions of LP [4], ILP(c,^𝑥) can be re-written as:

\begin{array}{l} m i n ‖ c - \hat{c} ‖_{p} \\ s . t . y (A \hat{x} - b) = 0, (complementary slackness), \\ y A = \hat{c}, (dual feasibility), \\ y \geq 0, (dual feasibility), \\ \hat{c} \in ℝ^{n} . \end{array}

(1)

Problem (1) is a convex non-linear optimization problem which could be transferred into LP for p = 1, and ∞ [1,22,23]. The problem is always feasible with an optimal solution, and (y∗,c) is an optimal solution if and only if $\hat{x} \in S_{o} (c)$ .

Yet another equivalent formulation of ILP(c,^𝑥) can be obtained, based on the conic hull concept introduced in the last section, by employing the following Lemma.

Lemma 1

[4, 17] Let $\hat{x} \in S$ be a feasible point of LP( $\hat{c}$ ). Then, $\hat{x} \in S_{o} (\hat{c})$ if and only if $\hat{c} \in \hat{K}$ .

Using Lemma 1, we can replace the constraint $\hat{x} \in S_{o} (\hat{c})$ in ILP(c,^𝑥) with $\hat{c} \in \hat{K}$ , which would result into the following equivalent problem:

\begin{array}{l} m i n ‖ c - \hat{c} ‖_{p} \\ s . t . \hat{c} \in \hat{K}, \\ \hat{c} \in ℝ^{n} . \end{array}

(2)

4. Inverse multi-objective linear programming

This section provides a natural extension of inverse single-objective linear programming provided in the previous section for multi-objective programs. In the following subsections, we first introduce the inverse MOLP (IMOLP) and then prove two special characteristics of IMOLPs. Afterwards, we introduce the new algorithm followed by a numerical example and a geometric interpretation.

4.1. Problem formulation and characteristics

Given that optimality for LP is replaced by Pareto optimality in MOLP and the cost vector is replaced by the criteria matrix, it then makes sense to define the inverse MOLP as a minimal modifications in the criteria matrix in order to make a given feasible solution $\hat{x}$ a weak efficient solution. This leads to the following problem:

\begin{array}{l} m i n ‖ C - \hat{C} ‖ \\ s . t . \hat{x} \in S_{w e} (\hat{C}), \\ \hat{C} \in ℝ^{k \times n}, \end{array}

IMOLP(C,^𝑥)

where $S_{w e} (\hat{C})$ is a set of all weak efficient points of MOLP( $\hat{C}$ ), and ‖.‖ denotes a matrix norm on $ℝ^{k \times n}$ , gauging the modifications between two matrices C and $\hat{C}$ . It is worth mentioning that IMOLP(C,^𝑥) is simply reduced to ILP(c,^𝑥) if there is only one objective function.

Now we take advantage of the following weighted-sum theorem to make connection between ILPs and IMOLPs.

Theorem 1

[10, 15, 20] $\hat{x} \in S$ is a weak efficient solution of MOLP( $\hat{C}$ ) if and only if there exists a vector $w \in W = {w \in ℝ^{k} ∣ \sum_{i = 1}^{κ} w_{i} = 1, w_{i} \geq 0}$ such that $\hat{x}$ is an optimal solution of the weighted-sum LP $m i n {w \hat{C} x ∣ x \in S}$ .

Let conv(C) denotes the convex hull of the rows of the matrix C. The following lemma can be immediately obtained from Lemma 1 and Theorem 1.

Lemma 2

The following statements are equivalent.

$\hat{x} \in S_{w e} (\hat{C})$ .
There exists w ∈ W such that $w \hat{C} \in \hat{K}$ .
(iii) $d (c o n v (\hat{C}), \hat{K}) = 0$ .

By the second part of Lemma 2, IMOLP(C,^𝑥) is equivalent to:

\begin{array}{l} m i n ‖ C - \hat{C} ‖ \\ s . t . w \hat{C} \in \hat{K}, \\ w \in W, \\ \hat{C} \in ℝ^{k \times n} . \end{array}

(3)

Problem (3) provides an interpretation for IMOLPs. If $\hat{x}$ is not a weak efficient solution, then IMOLP looks for the least modification of the criteria matrix C such that a convex combination of its rows belongs to $\hat{K}$ which is the convex cone created by the active constraints at $\hat{x}$ . We study Problem (3) under the matrix norm $‖ C - \hat{C} ‖ = \sum_{i = 1}^{k} {‖ c_{i} - {\hat{c}}_{i} ‖}_{p} 1 \leq p \leq \infty$ , although one may study other norms (e.g., Forbenius, maximum absolute row sum,...).

Now, by simply injecting the definition of the conic hull $\hat{K}$ into (3), we obtain:

\begin{array}{l} \min ρ = \sum_{i = 1}^{k} {‖ c_{i} - {\hat{c}}_{i} ‖}_{p} \\ s . t . \sum_{i = 1}^{k} w_{i} {\hat{c}}_{i} - \sum_{r \in I (\hat{x})} β_{r} a_{r} = 0, \\ \sum_{i = 1}^{k} w_{i} = 1, \\ w_{i} \geq 0, i = 1, \dots, k, \\ β_{r} \geq 0, r \in I (\hat{x}), \\ {\hat{c}}_{i} \in ℝ^{n}, i = 1, \dots, k . \end{array}

(4)

In analogy to ILP(c, $\hat{x}$ ) (1), IMOLP(C, $\hat{x}$ ) (4) is always feasible with an optimal solution. For instance, an obvious feasible point is ( $\hat{C} = 0$ , $w_{i} = \frac{1}{k}$ , for i = 1, . . . ,k,β = 0). Furthermore, by employing Lemma 2, the objective value of IMOLP(C, $\hat{x}$ ) (4) is zero if and only if $\hat{x} \in S_{w e} (C)$ . However, as opposed to ILP(c, $\hat{x}$ ) (1), IMOLP(C, $\hat{x}$ ) (4) is not convex due to the presence of the variable multiplication $w_{i} {\hat{c}}_{i}$ .

The following two theorems show that even though IMOLP(C, $\hat{x}$ ) (4) is a non-convex optimization problem, it can be solved using a series of convex optimization problems. The first part of Theorem 2 reveals that there always exists an optimal solution for which only one objective function has been modified, and the second part provides a lower bound for the optimal objective value of IMOLP(C, $\hat{x}$ ) (4) that can be later on employed in the algorithm design as a termination criterion.

Theorem 2

For IMOLP(C, $\hat{x}$ ) (4) if $d (c o n v (C), \hat{K}) > 0$ , then

IMOLP(C, $\hat{x}$ ) (4) has an optimal solution $\hat{C} *$ for which ${\hat{c}}_{i}^{*} = c_{i}$ for i ∈ {1, . . . ,k}, and i ≠ j.
$d (c o n v (C), \hat{K})$ provides a lower bound for the optimal value of IMOLP(C, $\hat{x}$ ) (4), i.e., $ρ * \geq d (c o n v (C), \hat{K})$ .

Proof

Let $ξ^{'} = ({\hat{C}}^{'}, w^{'}, β^{'})$ be an optimal solution of IMOLP(C, $\hat{x}$ ) (4) with the optimal objective value ρ′. We prove part (i) by constructing a new optimal solution $ξ * = (\hat{C} *, w^{'}, β^{'})$ for which $\hat{C} *$ only differs C in one row. And we prove part (ii), by showing $ρ^{'} \geq d (c o n v (C), \hat{K})$ .

i
⇒ Since ξ′ is a feasible solution of IMOLP(C, $\hat{x}$ ) (4), we have:

\sum_{i = 1}^{k} w_{i}^{'} {\hat{c}}_{i}^{'} - \sum_{r \in I (\hat{x})} β_{r}^{'} a_{r} = 0.

(5)

Now we define $\hat{C} *$ as follows:

{\hat{c}}_{i}^{*} = {\begin{array}{l} c_{i} & i \neq s \\ c_{s} + \sum_{i = 1}^{k} \frac{w_{i}^{'}}{w_{s}^{'}} v_{i} & i = s \end{array}

(6)

where $v_{i} = {\hat{c}}_{i}^{'} - c_{i}$ and $w_{s}^{'} = m a x {w_{i}^{'} ∣ i = 1, \dots, k} > 0$ . Now we have:

\sum_{i = 1}^{k} w_{i}^{'} {\hat{c}}_{i}^{*} = w_{s}^{'} {\hat{c}}_{s}^{*} + \sum_{\begin{matrix} i = 1 \\ i \neq s \end{matrix}}^{k} w_{i}^{'} {\hat{c}}_{i}^{*} = w_{s}^{'} (c_{s} + \sum_{i = 1}^{k} \frac{w_{i}^{'}}{w_{s}^{'}} ({\hat{c}}_{i}^{'} - c_{i})) + \sum_{\begin{matrix} i = 1 \\ i \neq s \end{matrix}}^{k} w_{i}^{'} c_{i} = w_{s}^{'} c_{s} + \sum_{i = 1}^{k} w_{i}^{'} ({\hat{c}}_{i}^{'} - c_{i}) + \sum_{\begin{matrix} i = 1 \\ i \neq s \end{matrix}}^{k} w_{i}^{'} c_{i} = \sum_{i = 1}^{k} w_{i}^{'} {\hat{c}}_{i}^{'} = \sum_{r \in I (\hat{x})} β_{r}^{'} a_{r} (according to (5))

So, ξ∗ is a feasible solution of IMOLP(C, $\hat{x}$ ) (4). Now we just need to show that ξ∗ is at least as good as ξ′ in terms of objective function:

‖ C - {\hat{C}}^{*} ‖ = \sum_{i = 1}^{k} {‖ c_{i} - {\hat{c}}_{i}^{*} ‖}_{p} = {‖ \sum_{i = 1}^{k} \frac{w_{i}^{'}}{w_{s}^{'}} v_{i} ‖}_{p} (according to (6)) \leq \sum_{i = 1}^{k} {‖ \frac{w_{i}^{'}}{w_{s}^{'}} v_{i} ‖}_{p} (according to triangle inequality in norms) = \sum_{i = 1}^{k} (\frac{w_{i}^{'}}{w_{s}^{'}}) {‖ v_{i} ‖}_{p} \leq \sum_{i = 1}^{k} {‖ v_{i} ‖}_{p} = ‖ C - {\hat{C}}^{'} ‖ . (since w_{s}^{'} \geq w_{i}^{'})

ii
⇒ Let us define h and $\hat{k}$ as follows:

h = \sum_{i = 1}^{k} w_{i}^{'} {\hat{c}}_{i}^{*} - w_{s}^{'} ({\hat{c}}_{s}^{*} - c_{s}),

\hat{k} = \sum_{r \in I (\hat{x})} β_{r}^{'} a_{r} .

Given the definition of $\hat{C} *$ in (6), we have

h = \sum_{i = 1}^{k} w_{i}^{'} {\hat{c}}_{i}^{*} - w_{s}^{'} ({\hat{c}}_{s}^{*} - c_{s}) = \sum_{\begin{matrix} i = 1 \\ i \neq s \end{matrix}}^{k} w_{i}^{'} {\hat{c}}_{i}^{*} + (w_{s}^{'} {\hat{c}}_{s}^{*} - w_{s}^{'} {\hat{c}}_{s}^{*}) + w_{s}^{'} c_{s} = \sum_{\begin{matrix} i = 1 \\ i \neq s \end{matrix}}^{k} w_{i}^{'} c_{i} + w_{s}^{'} c_{s} = \sum_{i = 1}^{k} w_{i}^{'} c_{i}

So, h ∈ conv(C). On the other hand, since ξ∗ is a feasible solution of IMOLP(C, $\hat{x}$ ) (4), $\sum_{i = 1}^{k} w_{i}^{'} {\hat{c}}_{i}^{*} = \sum_{r \in I (\hat{x})} β_{r}^{'} a_{r}$ and so:

\begin{array}{l} d (c o n v (C), \hat{K}) \leq ‖ h - \hat{k} ‖_{p} (according to Definition 1 in Section 2) \\ = w_{s}^{'} {‖ c_{s} - {\hat{c}}_{s}^{*} ‖}_{p} \\ \leq {‖ c_{s} - {\hat{c}}_{s}^{*} ‖}_{p} = ‖ C - \hat{C} * ‖ (since w_{s}^{'} \leq 1) \end{array}

which completes the proof. □

If we assume that only the j-th objective function in IMOLP(C, $\hat{x}$ ) (4) is modified and the rest are the same, then we reach the following optimization problem:

\begin{array}{l} \min {‖ c_{j} - {\hat{c}}_{j} ‖}_{p} \\ s . t . w_{j} {\hat{c}}_{j} + \sum_{\begin{matrix} i = 1 \\ i \neq j \end{matrix}}^{k} w_{i} c_{i} - \sum_{r \in I (\hat{x})} β_{r} a_{r} = 0, \\ \sum_{i = 1}^{k} w_{i} = 1, \\ w_{i} \geq 0, i = 1, \dots, k, \\ β_{r} \geq 0, r \in I (\hat{x}), \\ {\hat{c}}_{j} \in ℝ^{n} . \end{array}

(P_j)

According to the first part of Theorem 2, we just need to solve P_j for all j and then the problem with the smallest optimal objective value will provide the optimal solution of the IMOLP(C,^𝑥). There is only one problem. P_j is still a non-convex problem due to the presence of $w_{j} {\hat{c}}_{j}$ , although P_j is already much easier than Problem (4) which has $w_{i} {\hat{c}}_{i}$ for all i ∈ {1, . . . ,k}. The following theorem reveals that P_j can be transferred to the equivalent convex optimization problem. It is worth mentioning that w_j > 0 in P_j, otherwise the optimal objective value of P_j is zero meaning $\hat{x}$ is already a weak efficient solution.

Theorem 3

If $d (c o n v (C), \hat{K}) > 0$ , then P_j is equivalent to the following convex optimization problem, Q_j:

\begin{array}{l} ρ_{j}^{*} = \min {‖ c_{j} - {\hat{c}}_{j} ‖}_{p} \\ s . t . {\hat{c}}_{j} + \sum_{\begin{matrix} i = 1 \\ i \neq j \end{matrix}}^{k} λ_{i} c_{i} - \sum_{r \in I (\hat{x})} α_{r} a_{r} = 0, \\ λ_{i} \geq 0, i = 1, \dots, k, i \neq j, \\ α_{r} \geq 0, r \in I (\hat{x}), \\ {\hat{c}}_{j} \in ℝ^{n} . \end{array}

(Q_j)

Proof

We prove by showing that there is a one-to-one correspondence between the points in the feasible region of the problem P_j and Q_j. Let $ξ_{j} = ({\hat{c}}_{j}, w, β)$ be a feasible point of P_j. By defining $λ_{i} = \frac{w_{i}}{w_{j}}$ (i = 1, . . . ,k,i ≠ j), and $α_{r} = \frac{β_{r}}{w_{j}} (r \in I (\hat{x}))$ , $ζ_{j} = ({\hat{c}}_{j}, λ, α)$ is a feasible point of Q_j with the same objective function. □

Now let $ζ_{j} = ({\hat{c}}_{j}, λ, α)$ be a feasible point of Q_j. By defining $w_{j} = \frac{1}{τ}$ , $w_{i} = \frac{λ_{i}}{τ} (i = 1, \dots, k, i \neq j)$ , and $β_{r} = \frac{α_{r}}{τ} (r \in I (\hat{x}))$ where $τ = 1 + \sum_{\begin{matrix} i = 1 \\ i \neq j \end{matrix}}^{k} λ_{i}$ , we obtain $ξ_{j} = ({\hat{c}}_{j}, w, β)$ as a feasible point of P_j with the same objective function. □

Now we provide a geometric interpretation of Q_j. Let K_j be the conic hull of ${{a_{r}}_{r \in I (\hat{x})}, {- c_{i}}_{i = 1, \neq j}^{k}}$ . Then, Q_j can be equivalently re-written as

\begin{array}{l} d (c_{j}, K_{j}) = m i n {‖ c_{j} - {\hat{c}}_{j} ‖}_{p} \\ s . t . {\hat{c}}_{j} \in K_{j}, \\ {\hat{c}}_{j} \in ℝ^{n} . \end{array}

So, the optimal solution of Q_j is the ℓ_p-projection of c_j onto K_j. This will be demonstrated in the numerical example in the next section.

4.2. Algorithm and a numerical example

The algorithm consists of two phases. The first phase calculates $d (c o n v (C), \hat{K})$ which could be used to determine whether or not $\hat{x}$ is already a weak efficient solution. It can also be served as a termination criterion by employing the second part of Theorem 2. However, Phase I could be eliminated if one already knows that $\hat{x}$ is not weak efficient and looking for the exact optimal solution.

Phase I:

Solve the following convex optimization problem

d (c o n v (C), \hat{K}) = m i n {‖ x - y ‖_{p} ∣ x \in c o n v (C), y \in \hat{K}} .

(7)

Let $d * : = d (c o n v (C), \hat{K})$ be the optimal objective value of Problem (7). If d∗ = 0, it means $\hat{x} \in S_{w e} (C)$ and go to Step 4, otherwise let j = 1 and go to Step 1.

Phase II:

Step 1: Solve Problem (Q_j). If $| ρ_{j}^{*} - d^{*} | \leq ε$ , then let j∗ = j and go to Step 3, otherwise go to Step 2.

Step 2: If j = k, let $j * = \underset{j = 1, \dots, k}{a r g m i n} ρ_{j}^{*}$ , and go to Step 3, otherwise let j = j + 1 and go to Step 1.

Step 3: Let $ζ_{j^{*}} = ({\hat{c}}_{j^{*}}^{*}, λ^{*}, α^{*})$ be an optimal solution of $Q_{j^{*}}$ . Then, $ξ * = (\hat{C} *, w *, β *)$ is an optimal solution of IMOLP(C, $\hat{x}$ ) (4) where w∗ and β∗ defined as follow, and $\hat{C} *$ and C agree in all rows except the j∗-th one.

w_{i}^{*} = \frac{λ_{i}^{*}}{1 + \sum_{\begin{matrix} i = 1 \\ i \neq j^{*} \end{matrix}}^{k} λ_{i}^{*}}, i = 1, \dots, k, i \neq j^{*},

w_{j^{*}}^{*} = \frac{1}{1 + \sum_{\begin{matrix} i = 1 \\ i \neq j^{*} \end{matrix}}^{k} λ_{i}^{*}},

β_{r}^{*} = \frac{α_{r}^{*}}{1 + \sum_{\begin{matrix} i = 1 \\ i \neq j^{*} \end{matrix}}^{k} λ_{i}^{*}}, r \in I (\hat{x}) .

Step 4: End.

Example 1 Consider the MOLP problem min {C_x | A_x ≥ b} and its IMOLP(C, $\hat{x}$ ) counterpart with $\hat{x} = (8, 7)$ and the following data:

C = (\begin{matrix} - 6 & - 1.5 \\ - 3 & 0.5 \\ 2 & 1.5 \end{matrix}), A = (\begin{matrix} - 2 & - 1 \\ - 3 & - 4 \\ - 1 & 0 \\ 0 & - 1 \\ 1 & 0 \\ 0 & 1 \end{matrix}), and b = (\begin{matrix} - 23 \\ - 52 \\ - 10 \\ - 10 \\ 0 \\ 0 \end{matrix}) .

We have $I (\hat{x}) = {1, 2}$ and $\hat{K} = {x \in ℝ^{2} ∣ x = β_{1} a_{1} + β_{2} a_{2}, β_{1}, β_{2} \geq 0}$ , where a₁ = (−2, −1) and a₂ =(−3, −4).

It is obvious from Figure 1a that the distance between $\hat{K}$ —the hatched area—and conv(C)—the triangle area—is positive and so $\hat{x}$ is not weak efficient. The distance is depicted as $d * = ‖ h - \hat{k} ‖_{p}$ .

Fig. 1: — (a)-(d): Different steps of the algorithm for Example 1. (e): The final result of the algorithm. (f): Changing multiple objective functions could result in less modification if there are restrictions on the criteria matrix modifications.

IMOLP(C, $\hat{x}$ ) is:

\begin{array}{l} \min ρ = {‖ c_{1} - {\hat{c}}_{1} ‖}_{p} + {‖ c_{2} - {\hat{c}}_{2} ‖}_{p} + {‖ c_{3} - {\hat{c}}_{3} ‖}_{p} \\ s . t . w_{1} {\hat{c}}_{1} + w_{2} {\hat{c}}_{2} + w_{3} {\hat{c}}_{3} - β_{1} a_{1} - β_{2} a_{2} = 0, \\ w_{1} + w_{2} + w_{3} = 1, \\ w_{1}, w_{2}, w_{3}, β_{1}, β_{2} \geq 0, \\ {\hat{c}}_{1}, {\hat{c}}_{2}, {\hat{c}}_{3} \in ℝ^{2} . \end{array}

We apply the proposed algorithm for p = 2. We assume that we are looking for the exact solution with the threshold ε= 0.

Phase I:

Solving the convex problem (7) yields $d * = ‖ h - \hat{k} ‖_{2} = \frac{6}{\sqrt{73}}$ , where $h = (- \frac{18}{73}, \frac{48}{73})$ and $\hat{k} = (0, 0)$ (see Figure 1a). Since d∗ > 0, let j = 1 and go to Step 1.

Phase II:

Step 1: We solve Q₁ as follows:

\begin{array}{l} \min ρ_{1} = {‖ c_{1} - {\hat{c}}_{1} ‖}_{2} \\ s . t . {\hat{c}}_{1} + λ_{2} c_{2} + λ_{3} c_{3} - α_{1} a_{1} - α_{2} a_{2} = 0, \\ λ_{2}, λ_{3}, α_{1}, α_{2} \geq 0, \\ {\hat{c}}_{1} \in ℝ^{2} . \end{array}

Figure 1b illustrates the geometric interpretation of Q₁. This problem finds the minimum distance between c₁ and $K_{1} = c o n e ({a_{1}, a_{2}, - c_{2}, - c_{3}}) = c o n e ({a_{1}, - c_{2}})$ . The optimal objective value is $ρ_{1}^{*} = \frac{3}{\sqrt{5}}$ and since $ρ_{1}^{*} - d * > 0$ , we solve Q₂:

\begin{array}{l} \min ρ_{2} = {‖ c_{2} - {\hat{c}}_{2} ‖}_{2} \\ s . t . {\hat{c}}_{2} + λ_{1} c_{1} + λ_{3} c_{3} - α_{1} a_{1} - α_{2} a_{2} = 0, \\ λ_{1}, λ_{3}, α_{1}, α_{2} \geq 0, \\ {\hat{c}}_{2} \in ℝ^{2} . \end{array}

Figure 1c corresponds to Q₂ and the optimal solution here is the minimum distance between c₂ and $K_{2} = c o n e ({a_{1}, a_{2}, - c_{1}, - c_{3}}) = c o n e ({a_{1}, - c_{1}})$ . The optimal objective value is $ρ_{2}^{*} = \frac{4}{\sqrt{5}} > d *$ , so we need to solve Q₃.

\begin{array}{l} \min ρ_{3} = {‖ c_{3} - {\hat{c}}_{3} ‖}_{2} \\ s . t . {\hat{c}}_{3} + λ_{1} c_{1} + λ_{2} c_{2} - α_{1} a_{1} - α_{2} a_{2} = 0, \\ λ_{1}, λ_{2}, α_{1}, α_{2} \geq 0, \\ {\hat{c}}_{3} \in ℝ^{2} . \end{array}

Figure 1d corresponds to Q₃, and the optimal objective value is $ρ_{3}^{*} = \frac{4}{\sqrt{17}}$ . Since Q₃ has the smallest objective value among all the problems, j∗= 3. The optimal solution of Q₃ is $ζ_{3}^{*} = ({\hat{c}}_{3}^{*}, λ_{1}^{*}, λ_{2}^{*}, α_{1}^{*}, α_{2}^{*}) = ((\frac{38}{17}, \frac{19}{34}), \frac{19}{51}, 0, 0, 0)$ . Therefore, the optimal solution of IMOLP(C, $\hat{x}$ ) is $ξ * = ({\hat{c}}_{1}^{*}, {\hat{c}}_{2}^{*}, {\hat{c}}_{3}^{*}, w_{1}^{*}, w_{2}^{*}, w_{3}^{*}, β_{1}^{*}, β_{2}^{*}) = (c_{1}, c_{2}, {\hat{c}}_{3}^{*}, \frac{19}{70}, 0, \frac{51}{70}, 0, 0)$ .

Figure 1e illustrates the new criteria matrix $\hat{C} *$ , obtained by moving c₃ to ${\hat{c}}_{3}^{*}$ . It is seen that $c o n v (\hat{C} *)$ intersects $\hat{K}$ , which according to Lemma 2 means that $\hat{x}$ is weakly efficient for the new criteria matrix. Before we close this session, we would like to show that, through a simple example, that the results presented in this paper do not necessarily hold true if there are some constraints on how much the criteria matrix can be changed. In the above example, let us assume that c₃ cannot be modified more than 0.95, according to the ℓ₂-norm (i.e., ${‖ c_{3} - {\hat{c}}_{3} ‖}_{2} \leq 0.95$ ). This is less than what c₃ needs to move $(\frac{4}{\sqrt{17}} \approx 0.97)$ in order for $c o n v (\hat{C})$ to intersect $\hat{K}$ . Now, we show that moving c₁ and c₃ simultaneously leads to less modification than moving c₁ or c₂ individually. If c₁ moves to ${\hat{c}}_{1} = (- \frac{2610}{449}, - \frac{1827}{898})$ and c₃ moves to ${\hat{c}}_{3} = (\frac{1010}{449}, \frac{707}{898})$ , then as it can be seen in Figure 1f, $c o n v (\hat{C})$ intersects $\hat{K}$ , meaning $\hat{x}$ is a weakly efficient point. Therefore, moving c₁ and c₃ at the same time, results in ${‖ c_{1} - {\hat{c}}_{1} ‖}_{2} + {‖ c_{3} - {\hat{c}}_{3} ‖}_{2} \approx 1.32$ modification in the criteria matrix which is less than the modification required by moving only $c_{1} (ρ_{1}^{*} = \frac{3}{\sqrt{5}} \approx 1.34)$ or only $c_{2} (ρ_{2}^{*} = \frac{4}{\sqrt{5}} \approx 1.78)$ . Since moving c₃ alone is not an option due to the imposed restriction on the criteria matrix, individual modification of neither of the objective functions results in the least required modification in the criteria matrix to turn $\hat{x}$ into a weakly efficient point.

5. Conclusion

We generalized the existing inverse linear programming to inverse multi-objective linear programming. The generalized version specializes to the existing one if there is only one objective function. We discussed the non-convexity challenge of the resulting problem, and explained how it could be circumvented by exploiting some very special characteristics of the problem and taking advantage of the fact that there is always an optimal solution for which only one objective function is modified. The results only hold true if there is no constraints on how much the criteria matrix could be modified.

Footnotes

Publisher's Disclaimer: This Author Accepted Manuscript is a PDF file of an unedited peer-reviewed manuscript that has been accepted for publication but has not been copyedited or corrected. The official version of record that is published in the journal is kept up to date and so may therefore differ from this version.

Contributor Information

Mostafa Naghavi, Department of Mathematics, University of Qom, Qom, Iran.

Ali Asghar Foroughi, Department of Mathematics, University of Qom, Qom, Iran.

Masoud Zarepisheh, Department of Medical Physics, Memorial Sloan Kettering Cancer Center, New York, NY, USA.

References

1.Ahuja RK, Orlin JB: Inverse optimization. Operations Research 49(5), 771–783 (2001). DOI 10.1287/opre.49.5.771.10607. URL 10.1287/opre.49.5.771.10607 [DOI] [Google Scholar]
2.Akbari Z, Peyghami MR: An interior-point algorithm for solving inverse linear optimization problem. Optimization 61(4), 373–386 (2012). DOI 10.1080/02331934.2011.637111. URL 10.1080/02331934.2011.637111 [DOI] [Google Scholar]
3.Annetts JE, Audsley E: Multiple objective linear programming for environmental farm planning. Journal of the Operational Research Society 53(9), 933–943 (2002). DOI 10.1057/palgrave.jors.2601404. URL 10.1057/palgrave.jors.2601404 [DOI] [Google Scholar]
4.Bazaraa MS, Jarvis JJ, Sherali HD: Linear programming and network flows. John Wiley & Sons; (2011) [Google Scholar]
5.Boyd S, Vandenberghe L: Convex optimization. Cambridge university press; (2004) [Google Scholar]
6.Burton D, Toint PL: On an instance of the inverse shortest paths problem. Mathematical Programming 53(1), 45–61 (1992). DOI 10.1007/BF01585693. URL 10.1007/BF01585693 [DOI] [Google Scholar]
7.Chan TCY, Craig T, Lee T, Sharpe MB: Generalized inverse multiobjective optimization with application to cancer therapy. Operations Research 62(3), 680–695 (2014). DOI 10.1287/opre.2014.1267. URL 10.1287/opre.2014.1267 [DOI] [Google Scholar]
8.Chan TCY, Lee T: Trade-off preservation in inverse multi-objective convex optimization. European Journal of Operational Research 270(1), 25–39 (2018). DOI 10.1016/j.ejor.2018.02.045. URL http://sienediret.om/siene/artile/pii/S0377221718301784 [DOI] [Google Scholar]
9.Chan TCY, Lee T, Terekhov D: Inverse optimization: Closed-form solutions, geometry, and goodness of fit. Management Science pp. 1–21 (2018). DOI 10.1287/mnsc.2017.2992. URL [DOI] [Google Scholar]
10.Ehrgott M: Multicriteria optimization. Springer Science & Business Media; (2006) [Google Scholar]
11.Ghate A: Inverse optimization in countably infinite linear programs. Operations Research Letters 43(3), 231–235 (2015). DOI 10.1016/j.orl.2015.02.004. URL http://sienediret.om/siene/artile/pii/S0167637715000231 [DOI] [Google Scholar]
12.Hamacher HW, Küfer KH: Inverse radiation therapy planning — a multiple objective optimization approach. Discrete Applied Mathematics 118(1), 145–161 (2002). DOI 10.1016/S0166-218X(01)00261-X. URL http://sciencedirect.com/science/article/pii/S0166218X0100261X [DOI] [Google Scholar]
13.Heuberger C: Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of Combinatorial Optimization 8(3), 329–361 (2004). DOI 10.1023/B:JOCO.0000038914.26975.9b. URL 10.1023/B:JOCO.0000038914.26975.9b [DOI] [Google Scholar]
14.Iyengar G, Kang W: Inverse conic programming with applications. Operations Research Letters 33(3), 319–330 (2005). DOI 10.1016/j.orl.2004.04.007. URL http://sienediret.om/siene/artile/pii/S016763770400063X [DOI] [Google Scholar]
15.Luc DT: Multiobjective Linear Programming. Springer International Publishing; (2016) [Google Scholar]
16.Mostafaee A, Hladík M, Čern M: Inverse linear programming with interval coefficients. Journal of Computational and Applied Mathematics 292, 591–608 (2016). DOI 10.1016/j.cam.2015.07.034. URL http://sienediret.om/siene/artile/pii/S0377042715004069 [DOI] [Google Scholar]
17.Murty KG: Linear Programming. John Wiley & Sons; (1983) [Google Scholar]
18.Roland J, Smet YD, Figueira JR: Inverse multi-objective combinatorial optimization. Discrete Applied Mathematics 161(16), 2764–2771 (2013). DOI 10.1016/j.dam.2013.04.024. URL http://sienediret.om/siene/artile/pii/S0166218X13002266 [DOI] [Google Scholar]
19.Schaefer AJ: Inverse integer programming. Optimization Letters 3(4), 483–489 (2009). DOI 10.1007/s11590-009-0131-z. URL 10.1007/s11590-009-0131-z [DOI] [Google Scholar]
20.Steuer RE: Multiple criteria optimization: theory, computation, and applications. Wiley; (1986) [Google Scholar]
21.Steuer RE, Na P: Multiple criteria decision making combined with finance: A categorized bibliographic study. European Journal of Operational Research 150(3), 496–515 (2003). DOI 10.1016/S0377-2217(02)00774-9. URL http://sciencedirect.com/science/article/pii/S0377221702007749 [DOI] [Google Scholar]
22.Zhang J, Liu Z: Calculating some inverse linear programming problems. Journal of Computational and Applied Mathematics 72(2), 261–273 (1996). DOI 10.1016/0377-0427(95)00277-4. URL http://sienediret.om/siene/artile/pii/0377042795002774 [DOI] [Google Scholar]
23.Zhang J, Liu Z: A further study on inverse linear programming problems. Journal of Computational and Applied Mathematics 106(2), 345–359 (1999). DOI 10.1016/S0377-0427(99)00080-1. URL http://sciencedirect.com/science/article/pii/S0377042799000801 [DOI] [Google Scholar]

PERMALINK

Inverse optimization for multi-objective linear programming

Mostafa Naghavi

Ali Asghar Foroughi

Masoud Zarepisheh

Abstract

1. Introduction

2. Preliminaries

Definition 1

3. Inverse single-objective linear programming

Lemma 1

4. Inverse multi-objective linear programming

4.1. Problem formulation and characteristics

Theorem 1

Lemma 2

Theorem 2

Proof

Theorem 3

Proof

4.2. Algorithm and a numerical example

Phase I:

Phase II:

Fig. 1:

Phase I:

Phase II:

5. Conclusion

Footnotes

Contributor Information

References

ACTIONS

PERMALINK

RESOURCES

Cite

Add to Collections

PERMALINK

Inverse optimization for multi-objective linear programming

Mostafa Naghavi

Ali Asghar Foroughi

Masoud Zarepisheh

Abstract

1. Introduction

2. Preliminaries

Definition 1

3. Inverse single-objective linear programming

Lemma 1

4. Inverse multi-objective linear programming

4.1. Problem formulation and characteristics

Theorem 1

Lemma 2

Theorem 2

Proof

Theorem 3

Proof

4.2. Algorithm and a numerical example

Phase I:

Phase II:

Fig. 1:

Phase I:

Phase II:

5. Conclusion

Footnotes

Contributor Information

References

ACTIONS

PERMALINK

RESOURCES

Similar articles

Cited by other articles

Links to NCBI Databases