On the simplex,interior-point and objective space approaches to multiobjective linear programming

Abstract

Most Multiple Objective Linear Programming (MOLP) algorithms working in the decision variable space, are based on the simplex algorithm or interior-point method of Linear Programming. However, objective space based methods are becoming more and more prominent. This paper investigates three algorithms namely the Extended Multiobjective Simplex Algorithm (EMSA), Arbel’s Affine Scaling Interior-point (ASIMOLP) algorithm and Benson’s objective space Outer Approximation (BOA) algorithm. An extensive review of these algorithms is also included. Numerical results on non-trivial MOLP problems show that EMSA and BOA are at par and superior in terms of the quality of a most preferred nondominated point to ASIMOLP. However, ASIMOLP more than holds its own in terms of computing efficiency.

Keywords

Multiple objective linear programming multiobjective simplex algorithm affine scaling interior MOLP algorithm outer-approximation algorithm most preferred nondominated point

Introduction

MOLP is a branch of Multiple Criteria Decision Making (MCDM) that seeks to optimize two or more linear objective functions subject to a set of linear constraints. MOLP has been an active area of research since the 1960s because of its relevance in practice. Indeed, many decision making problems that arise in the real world involve more than one objective function. Consequently, it has been widely applied in many fields and has become a useful tool in decision making. Formally, it can be written as

\begin{array}{l} min c_{1}^{T} x = f_{1} \\ ⋮ \\ c_{q}^{T} x = f_{q} \\ subject to x \in X = {x \in ℝ^{n} : A x = b, b \in ℝ^{m}, x \geq 0} \end{array}

(1)

where

c_{1}, \dots, c_{q}

are n-vectors containing the coefficients of the multiple objective functions, A is an m × n constraint matrix and b is the right hand side vector.

In practice, MOLP is typically solved by the Decision Maker (DM) with the support of the analyst looking for a most preferred (best) solution in the feasible region X. This is because optimizing all the objective functions simultaneously is not possible due to their conflicting nature. Consequently, the concept of optimality is replaced with that of efficiency. The purpose of MOLP is to obtain either all the efficient or nondominated extreme points or a subset of either, or a most preferred point depending on the purpose for which it is needed.

In the last few decades a number of algorithms have been suggested for MOLP. Most are based on the simplex and interior-point algorithms for Linear Programming which work in the decision space. However, Benson¹ argued that since the number of objectives in an MOLP is often much smaller than the number of decision variables and typically many efficient extreme points in the decision space map to a single point in the objective space, generating the set of nondominated points in the objective space would require less computation. He then suggested an outer-approximation algorithm for computing all the nondominated points in the objective space of the problem.

In this paper, we will extend the Multi-objective Simplex Algorithm (MSA) of Evans and Steuer² and compare it with the primal variant of BOA¹ as well as with a variant of the Interior-Point Method (IPM) developed by Arbel³ known as ASIMOLP. These algorithms will be compared comprehensively on a series of existing test problems and the results will be reported and discussed.

This comparison may sound not possible given that the three algorithms are based on three different philosophies and compute different things: MSA works in the decision space and finds the set of all efficient extreme points; ASIMOLP also works in the decision space but finds a most preferred efficient point and also returns the corresponding most preferred nondominated point; BOA, on the other hand, works in the objective space to find the set of all nondominated points of the problem.

To achieve this comparison, we will extend the MSA of Evans and Steuer² whose explicit form is given in Ehrgott⁴ and which computes all efficient extreme points, to also generate the set of all nondominated points of the problem. It has been shown that, in practice, the DM prefers basing his or her choice of a most preferred (best) solution in the nondominated points, Benson.¹ We shall then act as the DM and choose a Most Preferred Nondominated Point (MPNP) whose components are as close as possible to an unattainable ideal objective point from the nondominated set returned by the extended MSA and BOA to compare with a MPNP returned by ASIMOLP.

To the best of our knowledge, no comparison of the computing efficiency and the quality of MPNP chosen from the nondominated set returned by BOA and EMSA with that returned by ASIMOLP has been carried out before. We intend to fill this gap here.

This paper is organized as follows. The next section introduces MOLP and basic notation. The literature review section is a brief review of the relevant literature. We present MSA, its extended version EMSA, ASIMOLP and BOA in the Multiobjective simplex algorithm, The extended multiobjective simplex algorithm, The affine scaling interior point algorithm and Benson’s outer approximation algorithm sections, respectively. The Selection of the most preferred nondominated point section discusses the selection of a MPNP and the Experimental results section presents numerical results obtained with the different algorithms. Finally, a conclusion is presented in the last section.

Notation and definitions

An alternative and compact formulation of (1) is as follows

\begin{array}{l} min C x \\ subject to A x = b \\ x \geq 0 \end{array}

(2)

where C is a q × n criterion matrix consisting of the rows

c_{k}^{T}, k = 1, 2, \dots, q

, A and b are as described earlier. The feasible set in the decision space is

X = {x \in ℝ^{n} : A x = b, x \geq 0}

and in the objective space it is

Y = {C x : x \in X} .

The set Y is also referred to as the image of X.

A nondominated point in the objective space is the image of an efficient solution in the decision space; nondominated points form the nondominated set.

An efficient solution of an MOLP problem is a solution that cannot improve any of the objective functions without deteriorating at least one of the other objectives. A weakly efficient solution is one that cannot improve all the objective functions simultaneously. Mathematically, let $\hat{x} \in X$ be a feasible solution of (2) and let $\hat{y} = C \hat{x}$ :

$\hat{x}$ is called efficient if there is no $x \in X$ such that $C x \leq C \hat{x}$ and $C x \neq C \hat{x}$ ; correspondingly, $\hat{y} = C \hat{x}$ is called nondominated.

$\hat{x}$ is called weakly efficient if there is no $x \in X$ such that $C x < C \hat{x}$ ; and $\hat{y} = C \hat{x}$ is called weakly nondominated, Ehrgott.⁴

The set of all efficient solutions and the set of all weakly efficient solutions of (2) are denoted by X_E and X_WE respectively, Benson.⁵ $Y_{N} = {C x : x \in X_{E}}$ and $Y_{W N} = {C x : x \in X_{W E}}$ are the nondominated and weakly nondominated sets in the objective space of (2), respectively.

The nondominated faces in the objective space of a given problem constitutes the nondominated frontier and the efficient faces in the decision space of the problem constitutes the efficient frontier.

The ideal objective point $y^{*}$ is the minimum criterion values over the efficient set X_E. The ideal objective values are easy to obtain by simply minimizing each objective function individually over the feasible region X, Alves and Costa.⁶

Illustration

We consider the following MOLP adapted from Junior and Lins.⁷

\begin{array}{l} min f_{1} = - x_{1} \\ min f_{2} = - x_{2} \\ Subject to \\ 6 x_{1} + 10 x_{2} \leq 60 \\ x_{1} \leq 7 \\ x_{2} \leq 5 \\ x_{1}, x_{2} \geq 0 \end{array}

(3)

The feasible region in the decision space is shown in Figure 1, where $x^{1} = {(7.0, 1.8)}^{T},$ $x^{2} = {(1.6, 5.0)}^{T} \in X_{E}$ .

Figure 1.

Edge connecting the two efficient points in the decision space.

The nondominated points in the objective space are shown in Figure 2, where $f^{1} = {(- 1.6, - 5.0)}^{T}$ , and $f^{2} = {(- 7.0, - 1.8)}^{T} \in Y_{N}$ .

Figure 2.

The edge joining the two nondominated points in the objective space.

Literature review

Decision space methods

As stated earlier, a number of approaches have been suggested for generating either the entire efficient decision set X_E or the nondominated set Y_N or a subset thereof, or a most preferred solution to the problem.

Eiselt and Sandblom⁸ note that, Evans and Steuer,² Philip⁹ and Zeleny¹⁰ derived generalized versions of the simplex method known as MSA. That of Philip⁹ first determines if an extreme point is efficient and subsequently checks if it is the only one that exists. If not, the algorithm finds them all. This MSA approach, however, may fail at a degenerate vertex. In Philip,¹¹ it was modified to overcome this difficulty.

The MSA of Evans and Steuer² also generates all the efficient extreme points and unbounded efficient edges of MOLPs; see also Algorithm 7.1, on page 178 of Ehrgott.⁴ The algorithm first establishes that the problem is feasible and has efficient solutions. Thereafter, it generates them all. An LP test problem is solved to determine the pivots that lead to efficient vertices. The algorithm is implemented as a software called ADBASE in Steuer.¹²

The MSA variant of Zeleny¹⁰ also uses an LP test problem to determine the efficiency of extreme points. But, here, vertices are tested for efficiency after they have been obtained unlike in Evans and Steuer² where the test problem determines pivots leading to efficient vertices.

Yu and Zeleny^13,14 used the approach in Zeleny¹⁰ to generate the set of all efficient solutions and presented a formal procedure for testing the efficiency of extreme points. The efficient extreme points are derived from the efficient faces, in a top-to-down search strategy. Numerical illustrations with three objectives were used to demonstrate the effectiveness of the method. In a similar paper, Yu and Zeleny¹⁵ applied their approach expanded in Yu and Zeleny¹⁴ to parametric linear programming. Two basic forms of the problem and two computational procedures for computing the efficient set were presented: the direct decomposition of the parametric space into subspaces associated with extreme points and the indirect algebraic method. From a numerical experience point of view, the indirect algebraic method outperforms the direct decomposition.

Isermann¹⁶ proposed a variant of the MSA of Evans and Steuer² that solves fewer LPs when determining the entering variables. The algorithm first establishes whether an efficient solution for the problem exists, and solves a test problem to determine pivots leading to efficient vertices. It was implemented as a software called EFFACET in Isermann and Naujoks.¹⁷

The MSA of Gal¹⁸ generates the set of all efficient vertices and higher-dimensional faces. This approach is meant to address the problem of determining efficient faces and higher dimensional faces not resolved in Evans and Steuer² and Philip.⁹ Here, efficient extreme points are generated using a test problem. The algorithm also determines higher-dimensional efficient faces for degenerate problems which were only discussed in Isermann¹⁶ and Zeleny¹⁰ but not solved. The efficient faces are generated in a bottom-to-top search strategy unlike what was suggested in Yu and Zeleny.^13,14

Steuer¹⁹ applied the MSA of Evans and Steuer² to parametric and non-parametric MOLP. Different methods for obtaining an initial efficient extreme point as well as different LP test problems were also presented. Efficient extreme points are generated through the decomposition of the weight space into finite subsets that provide optimal weights corresponding to extreme point solutions.

Ehrgott⁴ applied the MSA of Evans and Steuer² to solve MOLP problem instances with two and three objective functions. Ecker and Kouada²⁰ also proposed a variation on the MSA of Evans and Steuer.² They noted that algorithms usually started from an initial efficient extreme point and moved to an adjacent one following the solution of an LP problem. The proposed method does not require the solution of any LP problem to test for the efficiency of extreme points and the feasible region needs not be bounded. The algorithm enumerates all efficient extreme points and appears to have computational advantage over other methods.

In a different paper, Ecker, Hegner and Kouada²¹ presented yet another variant of MSA. The algorithm first determines the maximal efficient faces incident to a given efficient vertex (i.e. containing the efficient vertex) and ensures that previously generated efficient faces are not regenerated. This is done following a bottom-to-top search strategy as in Gal,¹⁸ which dramatically improves computation time. The proposed approach was illustrated with a degenerate example given in Yu and Zeleny,¹⁴ to demonstrate its applicability. It was computationally more efficient than the method in Yu and Zeleny.¹⁴

The MSA of Arman and Malivert²² determines the set of efficient extreme points even for degenerate MOLPs. The approach follows a bottom-to-top search strategy and utilizes a lexicographic selection rule to choose the leaving variables which proves effective when solving degenerate problems. It was tested successfully on a number of degenerate problems. A numerical example with five objectives and eight constraints which was solved in Yu and Zeleny¹⁴ was also used to demonstrate its effectiveness. The proposed MSA was superior to that in Yu and Zeleny.¹⁴

Rudloff, Ulus and Vanderbei²³ suggested a parametric MSA which works for bounded and unbounded problems, but does not find all the efficient solutions unlike the algorithm of Evans and Steuer.² Instead, it finds a subset of efficient solutions based on the idea of Löhne.²⁴ That is, a subset of efficient extreme points and directions that allows to generate the whole efficient frontier. The algorithm performs pivoting for only one leaving variable among the set of all possible leaving variables. It was compared with that in Benson¹ which is an objective space based algorithm, and that of Evans and Steuer.² Numerical experiments show that the proposed algorithm outperforms Benson’s algorithm for non-degenerate problems. However, Benson’s algorithm is better for highly degenerate ones. The parametric MSA was also found to be computationally more efficient than that of Evans and Steuer.² Of all these variants, it was noted in Schechter and Evans²⁵ that, the algorithm of Evans and Steuer² is the most popular and successful for computing all efficient extreme points of the problem.

MSA and its variants make explicit use of the vertices of the feasible region. Interior-point approaches, however, generate iterates in the interior of the feasible region. Various such approaches have been suggested. The difference between them depends on the methodology employed to assess the suitability of points used to derive a combined search direction along which one heads towards the next iterate.

The first to adapt a variant of Karmarkar²⁶ interior-point algorithm, to solve MOLP appears to be Abhyankar, Morin and Trafalis.²⁷ It relies on the method of centers. It uses a parameterization of ellipsoids in the n-dimensional space to approximate the efficient frontier of the problem in polynomial time.

Arbel²⁸ also modified and adapted a variant of Karmarkar²⁶ algorithm resulting in the so called Affine Scaling Interior MOLP (ASIMOLP) algorithm. He used the convex combination of individual directions to derive a combined direction along which to step toward the next iterate. Specifically, the algorithm generates step direction vectors based on the objectives of the problem. The relative preference of these directions is then assessed using a utility (or preference) function to obtain the points used in combining them into a single direction vector that moves the current iterate to a new one. The process is repeated until the algorithm converges to a most preferred efficient solution after meeting some termination conditions.

Arbel³ proposed another ASIMOLP algorithm. This approach offers another means of assessing preference information to establish a combined search direction rather than using the DM’s utility function. The Analytic Hierarchy Process (AHP) developed in Saaty²⁹ was applied to obtain the relative preference of points used to derive a combined direction along which the next step is taken. It is based on the assessed preferences to weigh the step direction vectors for each of the objectives in order to derive a combined step direction vector. This process continues to generate search directions and new feasible points at each iteration, until the algorithm converges to a most preferred point on the efficient frontier.

In Arbel,³⁰ another ASIMOLP algorithm based on the AHP has been suggested. The derived preference information is applied to the projected gradients in order to obtain anchoring points and cones used in searching for a most preferred solution. The boundaries of the constraints polytope are constantly probed to make more directions available, which enables one to arrive at a most preferred solution.

Wen and Weng³¹ modified the ASIMOLP algorithm in Arbel²⁸ to resolve zigzagging issues. The modified algorithm, however, may not yield a most preferred efficient solution.

Lin, Chen and Chen³² also proposed a modification of the ASIMOLP of Arbel.²⁸ They adopted the utility function trade-off method to weigh the objective functions involved and compared the modified algorithm with that in Wen and Weng³¹ and the simplex method. Numerical experiments show that their algorithm is superior. On computing efficiency, the interior point based algorithms outperform the simplex-based ones on large scale problems.

Weng and Wen³³ presented an ASIMOLP based algorithm. It computes a weighted sum of the different search directions involved using a utility function. These search directions are then normalized with the weights to obtain a combined direction that moves the current solution to an anchor point. Computational experiments show that the proposed algorithm is suitable for solving large scale instances.

Objective space methods

Due to the various difficulties arising from solving MOLP problems in the decision space (such as having different efficient solutions that map onto the same point in the objective space), efforts were made to look at the possibility of solving them in the objective space.

Benson,¹ who presented a detailed account of decision space approaches, proposed an algorithm for generating the set of all nondominated points in the objective space. This is the so called BOA. According to him, this algorithm is the first of its kind. Computational results suggest that the objective space based approach is better than the decision space based one. A further analysis of the objective space based algorithm for the problem was presented in Benson.³⁴ This outer approximation algorithm also generates the set of all weakly nondominated points, thereby enhancing the usefulness of the algorithm as a decision aid.

Another of Bensonen⁵ suggestions is a hybrid approach for solving the problem in the objective space. The approach partitions the objective space into simplices that lie in each face so as to generate the set of nondominated points. This idea was earlier presented in Ban.³⁵ The algorithm is quite similar to that in Benson.¹ The difference between them is in the manner in which the nondominated vertices are found. While a vertex enumeration procedure is employed in Benson,¹ a simplicial partitioning technique is used in the latter.

In Shao and Ehrgott³⁶ a modification of the algorithm of Benson¹ was presented. While in Benson,¹ a bisection method that requires the solution of many LPs in one step is required, here, solving one LP achieves the desired effect and in the process improves computation time. In Shao and Ehrgott³⁷ was proposed an approximate dual variant of the algorithm of Benson¹ for obtaining approximate nondominated points to the problem. The proposed algorithm was applied to the beam intensity optimization problem of radio therapy treatment planning for which approximate nondominated points were obtained. Numerical testing shows that the approach is faster than solving the primal directly.

The explicit form of the algorithm of Benson¹ as modified by Shao and Ehrgott³⁶ is presented in Löhne.²⁴ This version solves two LPs in each iteration during the process of obtaining the nondominated extreme points. Löhne³⁸ presented a Matlab implementation of this algorithm called BENSOLVE-1.2, for computing all the nondominated points and directions (unbounded nondominated edges) of the problem.

Csirmaz³⁹ presented an improved version of the algorithm in Benson¹ that solves one LP and a vertex enumeration problem in each iteration. While in Benson,¹ solving two LPs to determine a unique boundary point and a supporting hyperplane of the image is required in two steps, here, the two steps are merged and solving only one LP does both tasks and improves computation time. The algorithm was used to generate all the nondominated vertices of the polytope defined by a set of Shannon inequalities on four random variables so as to map their entropy region. Numerical testing shows the applicability of the approach to medium and large instances.

Hamel and Löhne⁴⁰ introduced new versions and extensions of the algorithm in Benson.¹ The primal and dual variants of the algorithm solve only one LP problem in each iteration. Tests reveal a reduction in computation time.

Similarly, Löhne, Rudloff and Ulus⁴¹ extended the primal and dual variants of the algorithm in Benson¹ to approximately solve convex vector optimization problems in the objective space.

Based on our extensive review of the topic, it was observed that no comparison of the computing efficiency and quality of a MPNP chosen from the nondominated set returned by BOA and extended MSA with the MPNP returned by ASIMOLP has been carried out. We intend to fill this gap here.

Multiobjective simplex algorithm

A typical multiple objective simplex algorithm is that of Evans and Steuer.² The version described here can be found in Ehrgott,⁴ page 178. We consider this algorithm because of its popularity (see Schechter and Steuer²⁵) and because most of the MSA algorithms discussed earlier are either based on or are variants of it. It works in the decision space and finds the set of all efficient extreme points.

The algorithm is initialized by solving two auxiliary LPs to determine whether the problem is feasible and to verify that it has efficient solutions. If the feasible region X is not empty and the set of efficient extreme points X_E exists, a weighted sum LP is solved to determine an initial efficient basis B. Its implementation stores a list of efficient bases L₁ to be processed, a list L₂ of efficient bases for output, and a list of efficient nonbasic variables N_E. An LP test problem is solved to determine pivots that lead to efficient bases. The algorithm pivots from an initial efficient basis to an adjacent efficient basis until the list L₁ to be processed is empty. The algorithm stops and returns list L₂ from where all efficient extreme points are computed. Before we describe MSA in pseudo-code form, we first explain the used notation.

Notation: A, b, C form the problem data; L₁ and L₂ as above; $e^{T} = (1, \dots, 1) \in ℝ^{q}$ ; I is the identity matrix of proper order; X is the feasible set; X_E, the set of efficient solutions; B, the efficient basis; N_E, a list of efficient nonbasic variables; N, the set of nonbasic variables; $B^{'}$ , the new basis; $\bar{A}$ , and $\bar{b}$ are updated constraint matrix and RHS vector; R is the nonbasic part of the reduced cost matrix and r^j is a column of R corresponding to a nonbasic variable being tested for efficiency.

Illustration of MSA

Consider MOLP (3) of the Illustration section. We solve this problem using a Matlab implementation of Algorithm 1 provided by Rudloff, Ulus and Vanderbei.²³ The efficient extreme points found are $x^{1} = {(7.0, 1.8)}^{T},$ $x^{2} = {(1.6, 5.0)}^{T}, x^{3} = {(1.6, 5.0)}^{T}, x^{4} = {(7.0, 1.8)}^{T}$ . Where $x^{1} = {(x_{1}^{1}, x_{2}^{1})}^{T}$ , her $x^{4} = {(x_{1}^{4}, x_{2}^{4})}^{T} \in X_{E}$ . The algorithm is prone to generating more efficient extreme points due to the way it operates and due to the fact that it may find the same efficient extreme point in more than one iteration, as in this case; $x^{1} = x^{4}$ and $x^{2} = x^{3}$ are repetitive of what has already been found. The feasible region in the decision space is the same as in Figure 1.

The extended multiobjective simplex algorithm

As part of the initialization step (line 1 of Algorithn 2), we have included the set of efficient extreme points X_E and that of nondominated points Y_N. In the second phase, as the algorithm finds an initial efficient basis B by solving a weighted sum LP, the algorithm also finds a corresponding efficient basic feasible solution and appends it to the set of efficient extreme points ( $X_{E} \leftarrow {\bar{x}}$ ). The first nondominated point is also computed from $C^{T} \bar{x}$ and appended to the nondominated set ( $Y_{N} \leftarrow {C^{T} \bar{x}}$ ).

As the algorithm iterates, a new efficient basis $B^{'}$ is obtained after each pivot and the corresponding efficient basic feasible solution ${\bar{x}}^{'}$ (line 11 of Algorithm 2) is found and added to the set of efficient extreme points X_E (line 13). Likewise, the corresponding nondominated points are also found at each iteration and added to the nondominated set Y_N (line 14). This continues until the set of efficient bases L₁ to be processed is empty. The algorithm returns the set of all efficient extreme points and the corresponding nondominated points (line 20).

Before we present Algorithm 2 as the extended MSA in pseudo-code form, we first state here that the structure of the algorithm and the used notation remain the same as that in Algorithm 1. The additional components are $\bar{x}, {\bar{x}}^{'}$ , X_E and Y_N which stand for the efficient basic feasible solution, the new efficient basic feasible solution, the set of efficient extreme points and the corresponding set of nondominated points for output.

Illustration of the extended MSA

We modified and extended the Matlab implementation of Algorithm 1 provided by Rudloff, Ulus and Vanderbei²³ and used it to solve problem (3) of the Illustration section. The efficient extreme points found are $x^{1} = {(7.0, 1.8)}^{T},$ $x^{2} = {(1.6, 5.0)}^{T}$ , and the corresponding nondominated points are $f^{1} = {(- 7.0, - 1.8)}^{T}$ and $f^{2} = {(- 1.6, - 5.0)}^{T}$ respectively. Where $x^{1} = {(x_{1}^{1}, x_{2}^{1})}^{T}, x^{2} = {(x_{1}^{2}, x_{2}^{2})}^{T} \in X_{E}$ and $f^{1} = {(f_{1}^{1}, f_{2}^{1})}^{T}, f^{2} = {(f_{1}^{2}, f_{2}^{2})}^{T} \in Y_{N}$ . Notice here that, the efficient extreme points x¹, x² and the corresponding nondominated points f¹ and f² returned are devoid of redundant points. The algorithm is designed to avoid returning redundant efficient and nondominated points unlike the original version. The feasible region in the decision space is also the same as in Figure 1.

The affine scaling interior point algorithm

ASIMOLP whose general form can be found in Arbel,³ works in the decision space and returns only one efficient extreme point of the problem, or at most, an efficient face of the feasible region. It also returns the corresponding nondominated point. The algorithm is initialized with a feasible and interior starting solution vector x⁰ and generates q interior step direction vectors dx_i ( $1 \leq i \leq q$ ). AHP is then used to derive the relative priority or preference vector p for these directions by filling a pairwise comparison matrix, which is then normalized and the rows are averaged to obtain the priority vector. The components of the derived priority vector p are then used as coefficients of a convex combination of the q interior step directions that yields a combined step direction vector dx that moves toward a new feasible point. This process continues until the algorithm converges to a most preferred efficient extreme point after meeting some termination conditions. Before we present the pseudo-code form of ASIMOLP, the used notation is described.

Notation: A, b, C form the problem data; x⁰ is the initial interior feasible solution vector; α_i is the step size ( $1 \leq i \leq q$ ); σ is a stopping tolerance; ρ is the step size factor; D is the diagonal and scaling matrix; y_i is an estimate of the dual vector ( $1 \leq i \leq q$ ); dx_i is the ith interior step direction vector ( $1 \leq i \leq q$ ); p_i is the derived priority vector ( $1 \leq i \leq q$ ); x_new is the new feasible point; f_new is a vector containing the new objective values; x_end is the most preferred efficient extreme point at the boundary of the feasible region at termination and f_end is a vector containing the corresponding objective values at termination.

Algorithm 3: Affine Scaling Interior MOLP Algorithm

0: Input: $A, b, C : Problem data$

1: Initialize: $Choose x^{0} > 0$ , $Stopping tolerance σ (0 < σ < 1)$ , $Step size factor ρ (0 < ρ < 1)$ ,

Converged = 0, $k \leftarrow 0$ ;

2: while $Converged \neq 1$ do

3: $k \leftarrow k + 1$

4: $D \leftarrow diag (x_{0})$

5: $y_{i} (k) \leftarrow {(A D^{2} A^{T})}^{- 1} A D^{2} c_{i}, 1 \leq i \leq q$

6: $d x_{i} (k) \leftarrow D^{2} (c_{i}^{T} - A^{T} y_{i} (k)), 1 \leq i \leq q$

7: if $d x_{i} (k) \geq 0, 1 \leq i \leq q$ , stop

8: else

9: $α_{i} \leftarrow \min [\frac{- x_{i}}{d x_{i} (k)}, \forall d x_{i} (k) < 0], 1 \leq i \leq q$

10: $x_{i} (k + 1) \leftarrow x (k) + ρ α_{i} d x_{i} (k), 1 \leq i \leq q$

11: $d x \leftarrow \sum_{i = 1}^{q} p_{i} α_{i} d x_{i}$

12: $x (k + 1) \leftarrow x (k) + ρ d x (k)$

13: $x_{new} \leftarrow x (k) + d x (k)$

14: $f_{new} \leftarrow C^{T} x_{new}$

15: $d x_{end} \leftarrow x_{end} - x (k)$

16: if k > 1, do

17: $d x \leftarrow \sum_{i = 1}^{q} p_{i} α_{i} d x_{i} + p_{end} d x_{end}$

18: $x_{new} \leftarrow x (k) + ρ d x (k)$

19: $f_{new} \leftarrow C^{T} x_{new}$

20: $x_{end} \leftarrow x (k) + d x (k)$

21: $f_{end} \leftarrow C^{T} x_{end}$

22: $d x_{end} \leftarrow x_{end} - x_{new}$

23: else

24: if $| | d x_{end} | | \leq σ$ , stop

25: else

26: $x^{0} \leftarrow x_{new}$

27: $G o t o step 4$

28: endif

29: endif

30: endif

31: endwhile

32 Output: $x_{end} : Most preferred efficient extreme point$

$f_{end} : Values o f the objective functions$

Illustration of ASIMOLP

We developed the pseudo-code of this algorithm, implemented it in Matlab and used it to solve Problem (3) of the Illustration section. The most preferred efficient extreme point found using our Matlab implementation is $x^{1} = {(3.6418, 3.7913)}^{T}$ , and the values of the objective functions are $f^{1} = {(- 3.6418, - 3.7913)}^{T}$ . The search path as generated by Algorithm 3 is shown in Figure 3.

Figure 3.

ASIMOLP search path showing convergence to the efficient frontier.

Determination of the priority vector used in ASIMOLP

From Arbel,²⁸ one can either use a utility function if it is available (as was done in Arbel⁴²) to assess preference information needed to establish a combined step direction instead of interacting with the DM or use the AHP methodology, but in most cases, the utility function is not known, as stated in Arbel.³ In this paper, we have used AHP as was done in Arbel^3,30 to derive the relative preference or priority vector p whose components are used as coefficients of a convex combination of the q interior step directions that yields a combined step direction that moves the current iterate to a new one.

The procedure involves a pairwise comparison of the q interior step directions and construction of a q × q comparison matrix for comparing the interior step directions. A complete pairwise comparison matrix A can be expressed as

A = \begin{array}{l} d_{1} \\ d_{2} \\ ⋮ \\ d_{q} \end{array} \begin{array}{l} d_{1} d_{2} \dots d_{q} \\ (\begin{array}{l} \frac{w_{1}}{w_{1}} & \frac{w_{1}}{w_{2}} & \dots & \frac{w_{1}}{w_{q}} \\ \frac{w_{2}}{w_{1}} & \frac{w_{2}}{w_{2}} & \dots & \frac{w_{2}}{w_{q}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \frac{w_{q}}{w_{1}} & \frac{w_{q}}{w_{2}} & \dots & \frac{w_{q}}{w_{q}} \end{array}) = (\begin{matrix} 1 & a_{12} & \dots & a_{1 q} \\ a_{21} & 1 & \dots & a_{2 q} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{q 1} & a_{q 2} & \dots & 1 \end{matrix}) \end{array}

where the entry a_ij indicates the strength of the step direction d_i when compared with the step direction d_j. These entries are obtained from the well-established comparison scale used by AHP in Saaty,²⁹ Saaty and Vargas.⁴³ Such a scale is shown in Table 1.

Table 1.

Graduation scale for comparing alternatives.

Numerical value	Interpretation
1	requirement i and j are of equal value
3	requirement i has a slightly higher value than j
5	requirement i has a strongly higher value than j
7	requirement i has a very strongly higher value than j
9	requirement i has a an absolutely higher value than j
2,4,6,8	intermediate values bewteen two adjacent judgments

We note that the above comparison matrix is a reciprocal matrix, where $a_{i j} = 1 / a_{i j}$ , a_ij > 0 and a_ij = 1 for i = j. After filling out and obtaining the comparison matrix, the matrix is then normalized. The normalized principal eigen-vector herein referred to as the preference or priority vector, p, is obtained by averaging across the rows of the matrix. The components of the priority vector are then used as coefficients of a convex combination of the q interior directions that yields a combined direction that enables one to move from the current iterate to the next, (more details can be seen in Saaty,²⁹ Saaty and Vargas.⁴³

Benson’s outer approximation algorithm

We present here the version of BOA due to Shao and Ehrgott.³⁶ This version can be found in Löhne.²⁴ It works in the objective space of the problem and returns the set of all nondominated points and extreme directions. The algorithm can be regarded as a primal-dual method because it also solves the dual problem. But here, we are only concerned with the solution of the primal. The algorithm first constructs an initial surrounding polytope Y₀ containing the image Y in the objective space and an interior point $\hat{p}$ of the image is determined. At each iteration, a bounding polytope Y_k is maintained and its vertices as well as inequality representation (facets) are stored. Then for each vertex v of the polytope, the algorithm checks if the vertex is on the boundary of Y. If all the vertices are on the boundary of Y, the problem is solved. The external vertices of Y are among the vertices of Y_k. Otherwise, for any vertex v of Y_k that is not on the boundary of Y, the algorithm connects this vertex to the interior point $\hat{p}$ and finds the intersection y of this line with the boundary of Y by solving LP $P_{2} (v)$ . Then a supporting hyperplane adjacent to y is constructed by solving LP $D_{2} (y)$ . This hyperplane is added to Y_k to provide a smaller polytope. The algorithm is repeated in the same way until the vertices of Y_k coincide with the boundary of Y. The algorithm returns the set of vertices on the boundary of Y as the nondominated set $\bar{Y}$ and directions $\bar{Y^{h}}$ of the problem. Consider the notation used in the pseudo-code of Bensony untter Approximation Algorithm.

Notation: A, b, C are the problem data; P^h is the homogeneous problem; $D^{* h}$ is the homogeneous dual problem; ${\bar{T}}^{h}$ is the solution of the homogeneous dual problem; $\hat{p}$ is an interior point; $\bar{T}$ is a set of solutions of the dual problem; $Y_{k}^{d}$ is the inequality representation of the current polytope; k is the iteration counter; $Y_{k}^{p}$ is the representation by vertices; $(\hat{y}, z)$ is an optimal solution to $P_{2} (v)$ ; $δ (0 < δ < 1)$ is a unique value that determines the intersection or boundary point y; R(v) is the LP that finds the unique value δ; the command $solve ()$ solves an LP; $vert ()$ returns the vertices of a polytope Y; $\bar{Y}$ is the set of nondominated vertices; $({\bar{Y}}^{h})$ is the set of extreme directions.

Algorithm 4: Benson’s Outer Approximation Algorithm, Löhne²⁴

0: Input: $A, b, C : Problem data$ $a solution ({0}, {\bar{Y}}^{h}) t o P^{h}$ ;

$a solution {\bar{T}}^{h} t o D^{* h}$ ;

1: Initialize: $\hat{p} \leftarrow P (solve (P_{1} (0))) + e$ ;

2: $\bar{T} \leftarrow {(solve (D_{1} (w)), w) | (u, w) \in {\bar{T}}^{h}}$ ;

3: $while z = 0$ do

4: $Y_{k}^{d} \leftarrow {D^{*} (u, w) | (u, w) \in \bar{T}}$ ;

5: $Y_{k}^{p} \leftarrow vert (Y^{d})$ ;

6: $\bar{Y} \leftarrow \emptyset$ ;

7: $for i = 1 t o | Y^{p} |$ do

8: $v \leftarrow Y_{k}^{p} [i]$ ;

9: $(\hat{y}, z) \leftarrow solve (P_{2} (v))$ ;

10: $\bar{Y} \leftarrow \bar{Y} \cup {\hat{y}}$ ;

11: $if z \neq 0$ then

12: $(x, δ) \leftarrow solve (R (v)), (0 < δ < 1)$ ;

13: $y \leftarrow δ v + (1 - δ) \hat{p}$ ;

14: $(u, w) \leftarrow solve (D_{2} (y))$ ;

15: $\bar{T} \leftarrow \bar{T} \cup {(u, w)}$ ;

16: endif;

17: endfor;

18: endwhile

19 Output: $(\bar{Y}, \bar{Y^{h}}) : Nondominated set and directions$ ;

$\bar{T} : a solution t o dual .$

Illustration of BOA

For continuity, we consider again problem (3) of the Illustration section. The nondominated points found using an existing Matlab implementation of Algorithm 4, namely Bensolve-1.2 of Löhne,³⁸ are $f^{1} = {(- 7.0, - 1.8)}^{T}$ and $f^{2} = {(- 1.6, - 5.0)}^{T}$ where f¹ and $f^{2} \in Y_{N}$ . These nondominated points are as shown in Figure 2.

Selection of the most preferred nondominated point

To determine the Most Preferred Nondominated Point (MPNP), we employ the technique of compromise programming and compute the ideal objective point which would serve as a reference point in each case. Compromise programming is a mathematical programming method that is based on the notion of distance of a most preferred solution from the ideal point $y^{*}$ , Zeleny.⁴⁴ Ehrgott⁴⁵ note that the ideal point is an essential component of compromise programming, and the idea is to find a nondominated point which is as close as possible to it. This is a point in the objective space whose components are the optimal values of the objective functions when they are individually optimized Alves, Antunes and Climaco.⁴⁶ It was also noted in Zeleny⁴⁴ that the ideal point serves as a rationale directing and facilitating human choice and decision making. To find the ideal point, we simply solve q single objective problems

\begin{array}{l} min c_{k}^{T} x, k = 1, 2, \dots, q \\ subject to x \in X . \end{array}

(4)

We note here that, the ideal point itself is not an element of the nondominated set $(y^{*} \notin Y_{N})$ . Otherwise, this would mean that the objective functions are not conflicting, but it always exists in the objective space. Its corresponding point in the decision space may not exist Alves, Antunes and Climaco.⁴⁶

For our numerical illustration above (problem 3 of the Illustration section), solving each of the objective function individually over the feasible region X yields the ideal objective point $y^{*} = {(- 7.0, - 5.0)}^{T}$ . Clearly $y^{*} \notin Y_{N}$ where $Y_{N} = {{(- 7.0, - 1.8)}^{T}, {(- 1.6, - 5.0)}^{T}}$ .

Having computed the ideal objective point $y^{*}$ , we now determine the minimum distance of each nondominated point $\hat{y}$ from it by finding

\begin{array}{l} min {| | {\hat{y}}_{1} - y^{*} | |, | | {\hat{y}}_{2} - y^{*} | |, \dots, | | {\hat{y}}_{n} - y^{*} | |} \end{array}

where

{\hat{y}}_{i} \in Y_{N}

has already been found either by BOA or EMSA,

| | . | |

is the Euclidean norm on

ℝ^{q}

and

y^{*}

is the ideal objective point.Using the nondominated points f¹ and f² returned by BOA and EMSA for problem (3) yields

\begin{array}{l} | | f^{1} - y^{*} | | = 3.2 and | | f^{2} - y^{*} | | = 5. 4. \end{array}

Since, the relative distance of f¹ from the ideal point $y^{*}$ is 3.2 which is the smallest of the two, it therefore means that $f^{1} = {(- 7.0, - 1.80)}^{T}$ is the closest of the two nondominated points to the ideal point $y^{*} = {(- 7.0, - 5.0)}^{T}$ . Hence, f¹is selected as the DM’s most preferred nondominated point.

Next, we measure the distance of the nondominated point $f^{1} = {(- 3.6418 - 3.7913)}^{T}$ returned by ASIMOLP in the Illustration of ASIMOLP section for the same numerical illustration (Problem 3 of the Illustration section) from the ideal point $y^{*} = {(- 7.0, - 5.0)}^{T}$ , as was done with those returned by BOA and EMSA for the same example. It turned out that, the distance

\begin{array}{l} | | f^{1} - y^{*} | | = 3.5691 \end{array}

is bigger than 3.2 which was the closest when measuring the points returned by BOA and EMSA, thereby making the nondominated points returned by BOA and EMSA closer to the ideal point and of higher quality.

The following more substantial illustrative MOLP adapted from Zeleny⁴⁴ with three objectives makes the point.

\begin{array}{l} min f_{1} = - x_{1} - 2 x_{2} + x_{3} - 3 x_{4} - 2 x_{5} - x_{7} \\ min f_{2} = - x_{2} - x_{3} - 2 x_{4} - 3 x_{5} - x_{6} \\ min f_{3} = - x_{1} - x_{3} + x_{4} + x_{6} + x_{7} \\ Subject to \\ x_{1} + 2 x_{2} + x_{3} + x_{4} + 2 x_{5} + x_{6} + 2 x_{7} \leq 16 \\ - 2 x_{1} - x_{2} + x_{4} + 2 x_{5} + x_{7} \leq 16 \\ - x_{1} + x_{3} + 2 x_{5} - 2 x_{7} \leq 16 \\ x_{2} + 2 x_{3} - x_{4} + x_{5} - 2 x_{6} - x_{7} \leq 16 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7} \geq 0. \end{array}

(5)

Again, optimizing each of the objective functions individually over the feasible region yields the ideal objective point $y^{*} = {(- 48.0, - 32.0, - 16.0)}^{T}$ . Solving (5) with BOA and EMSA, the set of nondominated points found is $Y_{N} = {{(- 48.0, - 32.0, 16.0)}^{T}, \\ {(- 16.0, 0.0, - 16.0)}^{T}, {(0.0, - 8.0, - 16.0)}^{T}, {(- 5.33, - 21.33, - 5.33)}^{T}, {(- 16.0, - 24.0, 0.0)}^{T}}$ with $y^{*} \notin Y_{N}$ . By determining the minimum distance of each of these nondominated points from the ideal point $y^{*}$ , it was found that the point ${(- 48.0, - 32.0, 16.0)}^{T}$ is the closest. Its distance from it is 32. It is selected as the DMoi MPNP.

For problem (5), the MPNP returned by ASIMOLP is $f^{1} = {(- 7.65 - 13.80 - 7.75)}^{T}$ as shown in Table 2, Problem 10. Again, we measure its distance from the ideal point $y^{*} = {(- 48.0, - 32.0, - 16.0)}^{T}$ . It was found that the distance of the point ${(- 7.65 - 13.80 - 7.75)}^{T}$ from $y^{*} = {(- 48.0, - 32.0, - 16.0)}^{T}$ is 45.0269, which is also larger than the corresponding values of BOA and EMSA, thereby making the MPNPs returned by BOA and EMSA to be of higher quality.

Table 2.

Comparative results for individual problem.

Algorithm					EMSA		ASIMOLP		BOA
Prob.	Origin	n	m	q	MPNP	CPU (s)	MPNP	CPU (s)	MPNP	CPU (s)
1	Ehrgott	3	3	3	f1 = –2.00	0.169	f1 = –1.74	0.036	f1 = –2.00	0.038
	2006				f2 = 10.00		f2 = 5.56		f2 = 10.00
					f3 = –5.00		f3 = –2.75		f3 = –5.00
2	Zeleny	2	2	2	f1 = –25000.00	0.027	f1 = –30626.00	0.111	f1 = –25000.00	0.021
	1982				f2 = –66667.00		f2 = –64132.00		f2 = –66667.00
3	”	2	4	2	f1 = –9.00	0.072	f1 = 4.00	0.031	f1 = –9.00	0.026
					f2 = –15.00		f2 = –18.42		f2 = –15.00
4	”	2	4	3	f1 = –3.00	0.182	f1 = –3.50	0.027	f1 = –3.00	0.161
					f2 = –7.50		f2 = –2.74		f2 = –7.50
					f3 = 4.00		f3 = 4.89		f3 = 4.00
5	”	2	6	2	f1 = –24.00	0.399	f1 = –21.29	0.032	f1 = –24.00	0.212
					f2 = –16.00		f2 = –17.29		f2 = –16.00
6	”	3	3	3	f1 = 3.00	0.075	f1 = 1.33	0.028	f1 = 3.00	0.046
					f2 = –6.00		f2 = –6.20		f2 = –6.00
					f3 = –12.00		f3 = –9.68		f3 = –12.00
7	”	5	3	3	f1 = 0.00	0.041	f1 = –1.38	0.034	f1 = 0.00	0.043
					f2 = –4.00		f2 = –2.77		f2 = –4.00
					f3 = –24.00		f3 = –10.04		f3 = –24.00
8	”	5	2	2	f1 = –52.0	0.055	f1 = –4.11	0.019	f1 = –52.0	0.016
					f2 = –52.0		f2 = –29.30		f2 = –52.0
9	”	6	4	2	f1 = 0.00	0.229	f1 = –0.02	0.043	f1 = 0.00	0.017
					f2 = 0.00		f2 = –0.00		f2 = 0.00
10	”0	7	4	3	f1 = –48.00	0.317	f1 = –7.65	0.035	f1 = –48.00	0.163
					f2 = –32.00		f2 = –13.80		f2 = –32.00
					f3 = 16.00		f3 = –7.75		f3 = 16.00
11	iMOLPe	2	3	2	f1 = –21.00	0.052	f1 = –11.87	0.032	f1 = –21.00	0.047
					f2 = –7.00		f2 = –10.22		f2 = –7.00
12	”2	3	3	4	f1 = –10.00	0.074	f1 = –5.59	0.037	f1 = –10.00	0.033
					f2 = –20.00		f2 = –18.62		f2 = –20.00
					f3 = –100.00		f3 = –34.83		f3 = –100.00
					f4 = –10.00		f4 = –42.23		f4 = –10.00
13	”3	3	5	3	f1 = –25.00	0.551	f1 = –10.48	0.035	f1 = –25.00	0.042
					f2 = 0.00		f2 = –3.62		f2 = 0.00
					f3 = –5.00		f3 = –2.14		f3 = –5.00
14	”4	3	3	3	f1 = –2.66	0.089	f1 = –1.10	0.041	f1 = –2.66	0.035
					f2 = –2.00		f2 = –1.22		f2 = –2.00
					f3 = –0.33		f3 = –1.57		f3 = –0.33
15	”5	4	3	3	f1 = –48.50	0.097	f1 = –35.80	0.051	f1 = –48.50	0.038
					f2 = –19.50		f2 = –43.97		f2 = –19.50
					f3 = –37.00		f3 = –29.82		f3 = –37.00
16	”6	4	2	3	f1 = –20.00	0.041	f1 = –31.71	0.046	f1 = –20.00	0.036
					f2 = –80.00		f2 = –49.12		f2 = –80.00
					f3 = –40.00		f3 = –38.69		f3 = –40.00
17	”	4	4	3	f1 = –40.00	0.243	f1 = –32.22	0.041	f1 = –40.00	0.186
					f2 = –50.00		f2 = 32.50		f2 = –50.00
					f3 = –10.00		f3 = –36.27		f3 = –10.00
18	”8	3	3	3	f1 = 0.00	0.178	f1 = –1.12	0.042	f1 = 0.00	0.033
					f2 = –2.00		f2 = –2.14		f2 = –2.00
					f3 = –4.00		f3 = 2.63		f3 = –4.00
19	”9	15	10	2	f1 = –363.82	1.581	f1 = –137.09	0.142	f1 = –363.82	0.195
					f2 =–33.70		f2 =–198.96		f2 =–33.70
20	”0	15	10	3	f1 = –363.82	4.852	f1 = –107.15	0.223	f1 = –363.82	0.476
					f2 = –33.70		f2 = –169.94		f2 = –33.70
					f3 = –136.71		f3 = –16.26		f3 = –136.71
21	Steuer	5	5	2	f1 = –10.00	0.197	f1 = –6.30	0.033	f1 = –10.00	0.036
	1986				f2 = –3.00		f2 = –6.90		f2 = –3.00
22	”2	4	4	3	f1 = 3.42	0.065	f1 = –3.79	0.035	f1 = 3.42	0.015
					f2 = –10.28		f2 = 11.38		f2 = –10.28
					f3 = –3.42		f3 = –2.96		f3 = –3.42
23	”3	5	5	4	f1 = 1.02	1.432	f1 = 2.28	0.037	f1 = 1.02	0.098
					f2 = –25.46		f2 = –22.58		f2 = –25.46
					f3 = 24.44		f3 = 25.30		f3 = 24.44
					f4 = –28.32		f4 = –25.47		f4 = –28.32
24	”4	10	8	4	f1 = 106.29	125.406	f1 = 80.00	0.048	f1 = 106.29	1.973
					f2 = –462.13		f2 = –54.36		f2 = –462.13
					f3 = 175.57		f3 = –163.73		f3 = 175.57
					f4 = –33.41		f4 = –23.82		f4 = –33.41
25	”5	5	4	3	f1 = –52.07	0.196	f1 = –4.44	0.041	f1 = –52.07	0.054
					f2 = 31.50		f2 = –13.17		f2 = 31.50
					f3 = –17.35		f3 = –14.37		f3 = –17.35
26	”6	6	8	4	f1 = –6.94	14.846	f1 = –6.69	0.045	f1 = –6.94	0.065
					f2 = –5.38		f2 = –2.25		f2 = –5.38
					f3 = 6.83		f3 = 6.77		f3 = 6.83
					f4 = –9.16		f4 = –8.83		f4 = –9.16
27	”7	7	6	4	f1 = –31.53	0.451	f1 = –25.90	0.032	f1 = –31.53	0.286
					f2 = –26.48		f2 = –23.94		f2 = –26.48
					f3 = –26.57		f3 = –19.06		f3 = –26.57
					f4 = –0.34		f4 = –8.62		f4 = –0.34
28	”8	7	6	4	f1 = 26.80	1.601	f1 = 4.03	0.033	f1 = 26.80	0.192
					f2 = –37.73		f2 = –29.03		f2 = –37.73
					f3 = –24.33		f3 = –18.07		f3 = –24.33
					f4 = –59.60		f4 = –28.17		f4 = –59.60
29	”9	8	8	6	f1 = –74.00	36.125	f1 = –15.46	0.084	f1 = –74.00	73.963
					f2 = –107.50		f2 = –38.73		f2 = –107.50
					f3 = –41.25		f3 = –43.30		f3 = –41.25
					f4 = –27.25		f4 = –30.95		f4 = –27.25
					f5 = –9.00		f5 = –8.30		f5 = –9.00
					f6 = –30.75		f6 = –26.72		f6 = –30.75
30	”0	8	8	3	f1 = –36.57	2.726	f1 = –32.03	0.036	f1 = –36.57	0.168
					f2 = –22.28		f2 = –20.03		f2 = –22.28
					f3 = –14.00		f3 = –17.73		f3 = –14.00
31	”1	8	8	3	f1 = –14.03	0.706	f1 = –8.77	0.036	f1 = –14.03	0.135
					f2 = –18.00		f2 = –10.56		f2 = –18.00
					f3 = –4.93		f3 = –5.13		f3 = –4.93
32	”2	5	5	4	f1 = –21.50	0.618	f1 = –20.83	0.049	f1 = –21.50	0.277
					f2 = –39.25		f2 = –21.78		f2 = –39.25
					f3 = –16.25		f3 = –16.05		f3 = –16.25
					f4 = 27.00		f4 = 14.45		f4 = 27.00
33	”3	6	6	3	f1 = –12.65	3.907	f1 = 12.69	0.046	f1 = –12.65	0.212
					f2 = 0.00		f2 = –3.21		f2 = 0.00
					f3 = –30.15		f3 = –28.39		f3 = –30.15
34	”4	5	5	4	f1 = –14.66	2.016	f1 = –6.33	0.033	f1 = –14.66	0.183
					f2 = –21.06		f2 = –14.44		f2 = –21.06
					f3 = 35.73		f3 = 20.77		f3 = 35.73
					f4 = –16.00		f4 = –14.63		f4 = –16.00
35	”5	10	10	4	f1 = 46.50	325.555	f1 = 50.69	0.057	f1 = 46.50	0.333
					f2 = 19.21		f2 = 18.98		f2 = 19.21
					f3 = –27.07		f3 = –23.38		f3 = –27.07
					f4 = –27.07		f4 = –23.85		f4 = –27.07
36	”6	8	8	3	f1 = –14.48	13.251	f1 = –2.46	0.042	f1 = –14.48	0.217
					f2 = –4.74		f2 = –3.22		f2 = –4.74
					f3 = 6.93		f3 = –1.93		f3 = 6.93
37	”7	6	7	4	f1 = –2.61	6.051	f1 = –1.80	0.039	f1 = –2.61	0.386
					f2 = –12.63		f2 = –4.00		f2 = –12.63
					f3 = 9.70		f3 = 2.78		f3 = 9.70
					f4 = –2.37		f4 = –2.07		f4 = –2.37
38	”8	12	16	4	Aborted	–	f1 = –5.09	0.062	f1 = –5.25	31.034
					after		f2 = –9.83		f2 = –14.25
					3 days*		f3 = –9.53		f3 = –8.25
							f4 = –6.18		f4 = –1.00
39	”9	10	14	5	*	–	f1 = –1.07	0.051	f1 = –5.16	102.952
							f2 = –3.83		f2 = –2.79
							f3 = –5.53		f3 = –4.38
							f4 = –16.87		f4 = –18.70
							f5 = –8.42		f5 = –9.69
40	”0	7	6	3	f1 = –29.40	0.447	f1 = –10.74	0.044	f1 = –29.40	0.165
					f2 = –65.30		f2 = –32.20		f2 = –65.30
					f3 = –39.30		f3 = –24.39		f3 = –39.30
41	”1	7	7	3	f1 = –62.18	0.583	f1 = –47.39	0.039	f1 = –62.18	0.036
					f2 = –93.50		f2 = –86.99		f2 = –93.50
					f3 = –52.00		f3 = –54.78		f3 = –52.00
42	”2	6	6	4	f1 = –37.50	1.311	f1 = –10.40	0.032	f1 = –37.50	0.158
					f2 = –11.25		f2 = –6.52		f2 = –11.25
					f3 = –7.50		f3 = –5.91		f3 = –7.50
					f4 = –20.25		f4 = –0.34		f4 = –20.25
43	”3	6	6	4	f1 = 34.50	1.856	f1 = 28.39	0.029	f1 = 34.50	0.211
					f2 = –7.50		f2 = –6.38		f2 = –7.50
					f3 = –56.00		f3 = –45.43		f3 = –56.00
					f4 = –31.50		f4 = –25.83		f4 = –31.50
44	”4	10	14	5	*	–	f1 = 3.35	0.043	f1 = 1.03	307.611
							f2 = –3.18		f2 = –2.19
							f3 = –2.48		f3 = 2.01
							f4 = –2.50		f4 = –8.13
							f5 = 2.10		f5 = –7.22
45	”5	10	14	5	*	–	f1 = 2.35	0.057	f1 = –4.95	105.344
							f2 = 0.73		f2 = –3.42
							f3 = –11.72		f3 = –4.38
							f4 = –1.90		f4 = –18.91
							f5 = –10.33		f5 = –9.27
46	”6	7	7	3	f1 = –3.83	0.601	f1 = –6.82	0.038	f1 = –3.83	0.045
					f2 = –76.46		f2 = –68.93		f2 = –76.46
					f3 = –49.57		f3 = –25.08		f3 = –49.57
47	Bensolve	100	101	2	*	–	f1 = –4.89	0.037	f1 = –8.42	0.503
	1.2						f2 = –106.50		f2 = –116.65
48		5	31	5		–	f1 = 0.00	0.021	f1 = 0.00	2.877
					*		f2 = 0.00		f2 = –1.00
	Bensolve						f3 = 0.00		f3 = 0.00
	2.0						f4 = 0.00		f4 = 0.00
							f5 = 0.01		f5 = –2.00
49	Script of	36	36	2	f1 = –5.00	1.921	f1 = –8.41	0.018	f1 = –5.00	0.211
	Prob. 52				f2 = –26.00		f2 = –20.12		f2 = –26.00
50	”0	64	64	2	f1 = –63.00	14.455	f1 = –52.24	0.028	f1 = –63.00	0.403
					f2 = –7.00		f2 = –10.56		f2 = –7.00
51	”1	100	100	2	f1 = –124.00	119.821	f1 = –119.51	0.031	f1 = –124.00	0.621
					f2 = –9.00		f2 = –11.72		f2 = –9.00
52		343	343	3	Out of	–	f1 = –35.32	0.651	f1 = –42.00	55.302
	Bensolve				memory^x		f2 = –101.41		f2 = –294.00
	2.0						f3 = –9.63		f3 = –6.00
53	MOPLIB	30	21	12	f1 = 5.05X10-12, f2 = 5.02X10-12	7.235	No initial	–	f1 = 5.05X10-12, f2 = 5.02X10-12	0.598
					f3 = 5.03X10-12, f4 = 5.05X10-12		starting solution		f3 = 5.03X10-12, f4 = 5.05X10-12
					f5 = 5.05X10-12, f6 = 5.05X10-12				f5 = 5.05X10-12, f6 = 5.05X10-12
					f7 = 5.05X10-12, f8 = 5.04X10-12				f7 = 5.05X10-12, f8 = 5.04X10-12
					f9 = 5.06X10-12, f10 = 5.04X10-12				f9 = 5.06X10-12, f10 = 5.04X10-12
					f11 = 5.04X10-12, f12 = -5.54X10-11				f11 = 5.04X10-12, f12 = -5.54X10-11
54	”4	4492	1003	4	x	–	f1 = 42.70	18.281	x	–
							f2 = 83.10
							f3 = 0.00
							f4 = –725.90
55	”5	100	20	3	f1 = –168.00	5.281	f1 = –61.18	0.011	f1 = –168.00	4.291
					f2 = –124.00		f2 = –73.93		f2 = –124.00
					f3 = –143.00		f3 = –96.38		f3 = –143.00
56	”6	53	221	3	*	–	f1 = –19.23	0.725	f1 = 0.00	1663.803
							f2 = –54.56		f2 = –2.00
							f3 = 0.00		f3 = –13959.00
57	”7	53	226	3	f1 = –188.00	28.116	f1 = –50.22	–	f1 = –188.00	6.551
					f2 = –123.00		f2 = –47.01		f2 = –123.00
					f3 = 16842.00		f3 = 0.00		f3 = 16842.00
58	”8	900	60	4	*	–	f1 = –283.50	0.262	*	–
							f2 = –352.74
							f3 = –268.85
							f4 = –372.16
59	”9	1143	1211	3	x	–	f1 = 2.11	0.725	x	–
							f2 = 51.82
							f3 = 0.61
60	”0	218	28	27	*	–	f1 = 0.52, f2 = 0.01, f3 = 6.95	0.481	*	–
							f4 = 2.41, f5 = 4.94, f6 = –5.53
							f7 = –9.71, f8 = 2.23, f9 = –0.31
							f10 = 2.67, f11 = –3.19, f12 = –5.55
							f13 = –5.42, f14 = –4.46, f15 = –4.35
							f16 = 6.01, f17 = –3.36, f18 = 1.71
							f19 = –8.01, f20 = 8.90, f21 = 8.01
							f22 = –5.35, f23 = 5.35, f24 = 5.35
							f25 = 5.35, f26 = –5.37, f27 = –4.35

*Aborted after 3 days of running time.

^xOut of memory.

We have used this method to choose the MPNP from the nondominated sets returned by BOA and EMSA for comparison. There is no selection of a MPNP in ASIMOLP as the algorithm computes a most preferred efficient solution and also returns the corresponding most preferred nondominated point.

To determine the quality of the MPNP returned by ASIMOLP, we simply measure its distance from the ideal point in each case and compare with the distances of those returned by BOA and EMSA in order to determine that which is the closest to the ideal point and of higher quality. The way the preference or priority vector p needed in AHP is derived, is explained in the Determination of the priority vector used in ASIMOLP section.

Experimental results

In this section, we provide numerical results to compare the quality of a Most Preferred Nondominated Point (MPNP) and the efficiency of Algorithms 2, 3 and 4. Table 2 shows the numerical results for a collection of 60 existing problems ranging from small to medium and realistic MOLP instances. Problem 1 is taken from Ehrgott,⁴ and Problems 2 to 10 are from Zeleny.⁴⁴ Problems 11 to 20 are test problems from the interactive MOLP explorer (iMOLPe) of Alves, Antunes and Climaco.⁴⁶ Problems 21 to 46 are taken from Steuer.¹⁹ Problem 47 is a test problem in Bensolve-1.2 of Löhne,³⁸ while problems 48 and 52 are test problems in Bensolve-2.0 of Löhne and Weißing.⁴⁷ Problems 49 to 51 are obtained using a script in Bensolve-2.0 of Löhne and Weißing⁴⁷ that was also used to generate problem 52 with the same number of variables and constraints. Finally, problems 53 to 60 are from MOPLIB which stands for Multi-Objective Problem Library and is maintained by Löhne and Schenker.⁴⁸

Problem 47 is such that the constraint matrix is sparse while the criterion matrix is dense. The RHS vector is such that all the components are ones except for 200 at the end as the largest entry. Problem 48 has a dense constraint matrix with an identity matrix of order n as its criterion matrix where n is the number of variables in the problem. The RHS vector is such that all the components are zeros except for a one (1) at the begining as the only none zero element. Problems 49 to 52 have dense criterion matrices with identity matrices of order n as their constraint matrices where n is also the number of variables in the respective problem. All the elements in the RHS vectors are ones. Problem 53 is highly degenerate, its structure is such that, the constraint and criterion matrices are sparse while all the components of the RHS vector are zeros except for a one (1) as the only non-zero entry. Problem 54 has dense RHS vector while the constraint and criterion matrices are sparse. In Problems 55 and 58, the constraint matrices are sparse, the criterion matrices are dense and all the elements in the RHS vectors are ones. Problems 56 and 57 have sparse constraints and criterion matrices with dense RHS vectors. Problem 59 has dense RHS vector while the constraint and criterion matrices are sparse. Finally, Problem 60 is such that the constraint and criterion matrices are sparse while the components of the RHS vector are all zeros except for a ninety (90) at the end as the only non-zero entry.

We modified and extended Algorithm 1 of Evans and Steuer² into Algorithm 2 or EMSA the Extended Multiobjective Simplex Algorithm. We have implemented it in Matlab in the same way as in Rudloff, Ulus and Vanderbei²³ and experimented with it on a set of MOLP in Matlab in the same wain tAlgorithm 3 in Matlab and used an existing Matlab implementation of Algorithm 4, known as Bensolve-1.2 of Löhne.³⁸ The current version, Bensolve-2.0 of Löhne and Weißing⁴⁷ is implemented in the C programming language. We employed Bensolve-1.2 of Löhne³⁸ which is implemented in Matlab to test the algorithms with the same tools and for more meaningful comparisons. In all tests, m is the number of constraints, n the number of variables and q the number of objectives. Algorithm 3 is ASIMOLP of Arbel³ and Algorithm 4 is BOA of Benson¹ as presented in Shao and Ehrgott.³⁶ All algorithms were executed on an Intel Core i5-2500 CPU at 3.30 GHz with 16.0GB RAM.

We recorded the CPU times (in seconds) for each problem and acted as the DM by choosing a most preferred (best) nondominated point (whose components are as close as possible to the ideal objective point as explained in the Selection of the most preferred nondominated point section) from the nondominated set $Y_{N} = {C x : x \in X_{E}}$ returned by BOA to compare with the MPNP returned by EMSA and with that returned by ASIMOLP.

As can be seen from Table 2, the CPU times for all algorithms increase as the problem sizes increase. It was observed that ASIMOLP returns a CPU time of less than a second for most of the test problems it solves, thereby making it computationally more efficient than BOA and EMSA. However, BOA was found to be computationally more efficient than EMSA for all the test problems considered. We noticed that ASIMOLP did not solve problems 53 as there exists no initial and strictly positive starting solution ( $x^{0} > 0$ such that $A x^{0} = b$ ) due to singularity issues which indicates that either the initial solution does not exist or it is not unique. We suspect that the difficulty this problem pose to ASIMOLP is due to its matrix structure and the way Interior Point methods work. A diagonal matrix whose diagonal elements are the elements of an initial positive starting solution is required. Once the diagonal elements are not strictly positive ( $x^{0} > 0$ ), ASIMOLP exhibits this difficulty. We even employed a decomposition approach which did not yield the required initial positive starting solution.

In terms of the quality of a MPNP returned by the algorithms, it was observed that EMSA and BOA return the same MPNPs for all test problems considered. This makes these two algorithm comparable and the nondominated points they returned are of higher quality than those returned by ASIMOLP in all cases. We also observed in Table 2 that EMSA and BOA could not produce results for some of the test problems considered despite the long running time allowed (3 days); they were aborted. The fact that some problems were aborted after 3 days of running time does not necessarily mean that the algorithms cannot solve these problems; if allowed to run further they would potentially return a huge number of nondominated points or run out of memory which would indicate that the total number of nondominated points has exceeded the Matlab solution capacity of the machine used. We note here that, some of these problems most especially from problem 47 to 60 are numerically ill-posed and highly challenging MOLP instances with difficult structures.

Conclusion

We have reviewed the extensive literature on three iconic algorithms namely MSA, ASIMOLP and BOA. We have extended MSA to find the set of nondominated points and presented the algorithms as well as illustrated them on small MOLP instances. We then proceeded to investigate their computational efficiency and compare the quality of a most preferred nondominated point they returned on a collection of 60 existing problems ranging from small to moderate and large MOLP instances. It was observed that Benson’s BOA and EMSA, introduced here, are superior to ASIMOLP in terms of the quality of the most preferred nondominated point they returned. The measure of quality used is the distance to the ideal point as explained in the Selection of the most preferred nondominated point section. ASIMOLP, however, outperforms them in terms of computing efficiency. Moreover, on the test problems considered, BOA was also found to be computationally superior to EMSA.

Supplemental Material

sj-pdf-1-act-10.1177_17483026211008414 - Supplemental material for On the simplex, interior-point and objective space approaches to multiobjective linear programming

Supplemental material, sj-pdf-1-act-10.1177_17483026211008414 for On the simplex, interior-point and objective space approaches to multiobjective linear programming by Paschal B Nyiam and Abdellah Salhi in Journal of Algorithms and Computational Technology

Footnotes

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: We are grateful to ESRC, Grant ES/L011859/1, for partially funding this research.

ORCID iD

Paschal B Nyiam

References

Benson

HP.

An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J Glob Optim 1998; 13: 1–24.

Evans

and Steuer

A revised simplex method for linear multiple objective programs. Math Program 1973; 5: 54–72.

Arbel

A weighted-gradient approach to multi-objective linear programming problems using the analytic hierarchy process. Math Comput Modell 1993; 17: 27–39.

Ehrgott

Multicriteria optimization. Berlin: Springer Science & Business Media, 2006.

Benson

HP.

Hybrid approach for solving multiple-objective linear programs in outcome space. J Optim Theory Appl 1998; 98: 17–35.

Alves

and Costa

JP.

An exact method for computing the nadir values in multiple objective linear programming. Eur J Oper Res 2009; 198: 637–646.

Junior

and Lins

MPE.

A WIN-WIN approach to multiple objective linear programming problems. J Oper Res Soc 2009; 60: 728–733.

Eiselt

and Sandblom

CL.

Linear programming and its applications. Berlin: Springer Science & Business Media, 2007.

Philip

Algorithms for the vector maximization problem. Math Program 1972; 2: 207–229.

10.

Zeleny

Linear multiobjective programming. vol. 95. Berlin: Springer-Verlag, 1974.

11.

Philip

Vector maximization at a degenerate vertex. Math Program 1977; 13: 357–359.

12.

Steuer

RE.

ADBASE: a multiple objective linear programming solver for all efficient extreme points and all unbounded efficient edges. Athens: Terry College of Business, University of Georgia, 2003.

13.

and Zeleny

The techniques of linear multiobjective programming. Rairo Recherche Opérationnelle 1974; 8: 51–71.

14.

and Zeleny

The set of all nondominated solutions in linear cases and a multicriteria simplex method. J Math Anal Appl 1975; 49: 430–468.

15.

and Zeleny

Linear multiparametric programming by multicriteria simplex method. Manage Sci 1976; 23: 159–170.

16.

Isermann

The enumeration of the set of all efficient solutions for a linear multiple objective program. J Oper Res Soc 1977; 28: 711–725.

17.

Isermann

and Naujoks

Operating manual for the EFFACET multiple objective linear programming package. Bielefeld, Germany: Fakultaet fuer Wirtschaftswissenschaften, University of Bielefeld, 1984.

18.

Gal

A general method for determining the set of all efficient solutions to a linear vectormaximum problem. Eur J Oper Res 1977; 1: 307–322.

19.

Steuer

RE.

Multiple criteria optimization: theory, computation, and applications. Hoboken: Wiley; 1986.

20.

Ecker

and Kouada

Finding all efficient extreme points for multiple objective linear programs. Math Program 1978; 14: 249–261.

21.

Ecker

Hegner

and Kouada

Generating all maximal efficient faces for multiple objective linear programs. J Optim Theory Appl 1980; 30: 353–381.

22.

Armand

and Malivert

Determination of the efficient set in multiobjective linear programming. J Optim Theory Appl 1991; 70: 467–489.

23.

Rudloff

Ulus

and Vanderbei

A parametric simplex algorithm for linear vector optimization problems. Math Program 2017; 163: 213–230.

24.

Löhne

Vector optimization with infimum and supremum. Berlin: Springer Science & Business Media, 2011.

25.

Schechter

and Steuer

RE.

A correction to the connectedness of the Evans-Steuer algorithm of multiple objective linear programming. Found Comput Decis Sci 2005; 30: 351–360.

26.

Karmarkar

A new polynomial-time algorithm for linear programming. In: Proceedings of the sixteenth annual ACM symposium on theory of computing, 1984, pp.3024ompu New York: ACM.

27.

Abhyankar

Morin

and Trafalis

Efficient faces of polytopes: interior point algorithms, parametrization of algebraic varieties, and multiple objective optimization. Contemp Math 1990; 114: 319–341.

28.

Arbel

An interior multiobjective linear programming algorithm. Comput Oper Res 1993; 20: 723–735.

29.

Saaty

TL.

The analytic hierarchy process: planning, priority setting, resources allocation. New York: McGraw, 1980.

30.

Arbel

Anchoring points and cones of opportunities in interior multiobjective linear programming. J Oper Res Soc 1994; 45: 83–96.

31.

Wen

UP and

Weng

WT.

An interior algorithm for solving multiobjective linear programming problem. In: Institute for operations research and the management sciences international meeting, Tel Aviv, Israel, 1998.

32.

Lin

Chen

and Chen

On the modified interior point algorithm for solving multi-objective linear programming problems. Int J Inform Manag Sci 2006; 17: 107.

33.

Weng

and Wen

UP.

An interior point algorithm for solving linear optimization over the efficient set problems. J Chin Inst Ind Eng 2001; 18: 21–30.

34.

Benson

HP.

Further analysis of an outcome set-based algorithm for multiple objective linear programming. J Optim Theory Appl 1998; 97: 1–10.

35.

Ban

VT.

A finite algorithm for minimizing a concave function under linear constraints and its applications. In: Proceedings of IFIP working conference on recent advances in system modelling and optimization, 1983.

36.

Shao

and Ehrgott

Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning. Math Meth Oper Res 2008; 68: 257–276.

37.

Shao

and Ehrgott

Approximating the nondominated set of an MOLP by approximately solving its dual problem. Math Methods Oper Res 2008; 68: 469–492.

38.

Löhne

Bensolve: VLP solver, version 1.2, www.bensolve.org (2012, accessed 14 May 2021).

39.

Csirmaz

Using multiobjective optimization to map the entropy region. Comput Optim Appl 2016; 63: 45–67.

40.

Hamel

Löhne

and Rudloff

Benson type algorithms for linear vector optimization and applications. J Glob Optim 2014; 59: 811–836.

41.

Löhne

Rudloff

and Ulus

Primal and dual approximation algorithms for convex vector optimization problems. J Glob Optim 2014; 60: 713–736.

42.

Arbel

Using efficient anchoring points for generating search directions in interior multiobjective linear programming. J Oper Res Soc 1994; 45: 330–344.

43.

Saaty

and Vargas

LG.

The logic of priorities: application in business, energy, health, and transportation. Boston: Nijhoff, 1982.

44.

Zeleny

Multiple criteria decision making. New York: McGraw-Hill, 1982.

45.

Ehrgott

and Tenfelde-Podehl

Computation of ideal and nadir values and implications for their use in MCDM methods. Eur J Oper Res 2003; 151: 119–139.

46.

Alves

Antunes

and Clímaco

Interactive MOLP explorer: a graphical-based computational tool for teaching and decision support in multi-objective linear programming models. Comput Appl Eng Educ 2015; 23: 314–326.

47.

Löhne

and Weißing

Bensolve: VLP solver, version 2.0.x, www.bensolve.org (2015, accessed 14 May 2021).

48.

Löhne

and Schenker

S. MOPLIB

: multi-objective problem library, http://moplib.uni-jena.de (2015, accessed 13 March 2017).

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.49 MB