Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes Lizhen Shaoa, b∗ and Matthias Ehrgott aSchool of Au...

0 downloads 1 Views 197KB Size

Loading...

Optimization

20150317

To appear in Optimization Vol. 00, No. 00, Month 20XX, 1–17

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes Lizhen Shaoa,b∗ and Matthias Ehrgottb a

School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China; b Department of Management Science, Lancaster University Management School, Bailrigg, Lancaster LA1 4YX, United Kingdom; (Received 00 Month 20XX; accepted 00 Month 20XX) Multiplicative programming problems (MPPs) are global optimisation problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programming (MOLP) problems to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLP problems, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our MOLP based algorithms to a recent global optimisation algorithm for linear MPPs from the literature as well as two general global solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus we demonstrate that the use of multi-objective optimisation techniques can be beneficial to solve difficult single objective global optimisation problems. Keywords: linear multiplicative programming; multi-objective optimisation; approximation algorithm; nondominated point.

1.

Introduction

Consider the linear multiplicative programming problem (MPP), (PX )

min φ(x) =

p Q

i=1

(cTi x + di )

s.t. x ∈ X = {x ∈ Rn : Ax ≧ b}. X is the feasible set in decision (or variable) space Rn . We assume that X is nonempty, cTi x+ di > 0, i = 1, . . . , p for all x ∈ X and the minimal value of cTi x+ di over X exists. Let P (x) = Cx + d = (cT1 x + d1 , . . . , cTp x + dp )T . Y = {P (x) : x ∈ X } is called the feasible set in objective (or outcome) space Rp . Let x ¯ be an optimal solution of (PX ) and φ(¯ x) the corresponding optimal value. Let ǫ > 0 and let x∗ be a feasible solution of (PX ), x∗ ∈ X . Then x∗ is called ǫ-optimal solution of (PX ) if φ(x∗ ) ≦ φ(¯ x)(1 + ǫ). Problem (PX ) is a nonconvex global optimisation problem. It is known that problem (PX ) may possess several local minima and is an NP-hard problem, even ∗ Corresponding

author. Email: [email protected]

1

March 18, 2015

Optimization

20150317

when p = 2 [1]. Problem (PX ) has attracted considerable attention in the literature because of practical applications in various fields of study, including economic analysis [2], bond portfolio optimisation [3], VLSI chip design [4], multi-objective optimisation [5] and so on. A traditional way to solve multiplicative programming problems is to consider the problem in objective space Rp and most existing algorithms work in objective space. Benson and Boger [6] use a cutting plane method to solve linear MPPs, whereas Kuno [7] and Gao et al. [8] use branch and bound methods. Ryoo and Sahinidis [9] develop algorithms for linear multiplicative and generalized linear multiplicative programs based upon a lower bounding procedure and greedy branching schemes. Kim et al. [10] propose an outcome-space outer approximation algorithm for linear multiplicative programming. Depetrini and Locatelli [11] propose an algorithm for minimizing the product of two affine functions over a polyhedral set. Correspondences between multi-objective programming (MOP) problems and multiplicative programming problems were first pointed out by Benson and Boger [12]. They have shown that an optimal solution of an MPP problem is an efficient solution of a corresponding multi-objective optimisation problem. Thus algorithms for solving MOP problems can be adapted to solve MPP problems. In earlier work, we have modified the approximation algorithm of [13] for solving convex MOP problems into an objective space cut and bound algorithm to solve convex MPPs. In this paper we pursue this relationship further for the special case of linear MPPs of the form (PX ) and multi-objective linear programmes (MOLPs) (P), (P) minP (x) = (cT1 x + d1 , . . . , cTp x + dp )T s.t. x ∈ X = {x ∈ Rn : Ax ≧ b}, where X ⊆ Rn and Y = {P (x) : x ∈ X } ⊆ Rp are, as before, the feasible set in variable space and objective space, respectively. We understand the minimisation here as finding the weakly nondominated points of P (X ). The relationship between linear MPPs and MOLPs imply that the nonconvex global optimisation problem (PX ) can be solved by solving multi-objective linear programme (P) in objective space (see Section 2). Hence, the question arises whether a multi-objective linear programming approach to solve (PX ) can be competitive with single objective nonconvex global optimisation approaches. We show that this is the case. The main contributions of the paper are: (1) we exploit the linearity of the objective functions to improve the objective space cut and bound algorithm of [14] by only solving one linear programme (LP) in each iteration rather than two as the previous original version requires; (2) we turn the dual variant of Benson’s multi-objective linear programming algorithm [15] into a (new) sandwich algorithm for MOLP problems; and (3) based on the sandwich version of the dual Benson MOLP algorithm, we propose a dual objective space algorithm to solve linear MPP problems. The paper is organised as follows. In Section 2 we first introduce some notation, then we review the relationships between linear MPPs and multi-objective linear programming problems. The proposed primal and dual algorithms for MPPs as well as an illustrative example are presented in Section 3. Numerical results are presented in Section 4. Here, we compare the performance of the primal and dual MOLP based algorithms proposed in Section 3 with a recent global optimisation algorithm for linear MPPs from the literature as well as two global solvers. These numerical results demonstrate the superiority of the new MOLP based algorithms

2

March 18, 2015

Optimization

20150317

over general global optimisation approaches for linear MPPs. Finally, we draw some conclusions in Section 5.

2.

Multiplicative programming problems and multi-objective optimisation

In this paper we use the notation y 1 ≤ y 2 to indicate y 1 ≦ y 2 but y 1 6= y 2 for y 1 , y 2 ∈ Rp whereas y 1 < y 2 means yk1 < yk2 for all k = 1, . . . , p. The k-th unit vector in Rp is denoted by ek and a vector of all ones is denoted by e. Given a mapping P : Rn → Rp and a subset X ⊆ Rn we write P (X ) := {P (x) : x ∈ X }. Let A ⊆ Rp . We denote the interior and the boundary of A by int A and bd A. Furthermore, suppose A is a polyhedral convex set, then a convex subset F ⊆ A is called a face of A if for all y 1 , y 2 ∈ A and α ∈ (0, 1) such that αy 1 + (1 − α)y 2 ∈ F it holds that y 1 , y 2 ∈ F. A face F of A is called proper if ∅ = 6 F = 6 A. A point y ∈ A is called an extreme point of A if {y} is a face of A. Extreme points are also called vertices. The set of all vertices of a polyhedral convex set A is denoted by vert A. We consider two ordering cones, namely K := R≧ ep = {y ∈ Rp : y1 = · · · = yp−1 = 0, yp ≧ 0} and

Rp≧ = {x ∈ Rp : xk ≧ 0, k = 1, . . . , p}. The set of K-maximal elements of A is given by maxK A := {y ∈ A : ({y} + K \ {0}) ∩ A = ∅} . The set of (weakly) Rp≧ -minimal elements of A (also called the set of (weakly) nondominated points of A) is given by n o wminRp≧ A := y ∈ A : ({y} − int Rp≧ ) ∩ A = ∅ , n o minRp A := y ∈ A : ({y} − Rp≧ ) \ {0} ∩ A = ∅ . ≧

We also use the notation AW N = wminRp A and AN = minRp A to denote the set ≧

≧

of (weakly) Rp≧ -minimal or (weakly) nondominated points of A. For MOLP (P), i.e., wminRp P (X ), feasible solutions x ∈ X such that P (x) is ≧

a (weakly) nondominated element of P (X ) are frequently called (weakly) efficient solutions in the literature. It is well known that the image Y of a nonempty polyhedron X under a linear map P is also a nonempty polyhedron of dimension dim Y ≦ p. Most methods to solve multiplicative programming problem (PX ) consider a formulation of the problem in objective space Rp and solve it in objective space. p Q For a point y ∈ Rp , let T (y) = yi . A direct objective space formulation of (PX ) i=1

3

March 18, 2015

Optimization

20150317

is (PY )

min T (y) subject to y ∈ Y.

It has been proved that any global optimal solution to problem (PY ) must belong to the nondominated set YN (see, e.g., Proposition 2.1 of [14]). Therefore, an optimal solution of (PY ) is the same for any objective space formulation ¯ as long as YN = Y¯N is guaranteed. min{T (y) : y ∈ Y} We introduce the following polyhedral convex set P. Let P = {y ∈ Rp : P (x) ≦ y for some x ∈ X }, i.e., P = Y + Rp≧ which we call the extended feasible set in objective space. Theorem 2.1 ([13]) The following statements hold. (1) (2) (3) (4)

P ⊆ Rp is a nonempty set of dimension p and P is Rp≧ -bounded from below. YN = PN . vert P ⊆ PN . PW N = bd P.

According to Theorem 2.1, P and Y have the same nondominated set. Therefore as in [14] we use the following equivalent objective space formulation

(PP )

min T (y) =

p Y

yi subject to y ∈ P,

i=1

and we also have the following result according to [14]. Theorem 2.2 Problem (PP ) has a global optimal solution in vert P. Because of the properties in Theorem 2.1, e.g., P always contains an interior point and all the boundary points of P are weakly nondominated, it is easier to work with P instead of Y. Thus Benson’s outer approximation algorithm [16] and the dual variant of Benson’s outer approximation algorithm [15] for solving MOLP (P) try to work with P to find YN . Since our proposed primal and dual algorithms for linear MPPs (PX ) are based on Benson’s algorithm and its dual variant, respectively, we work with P as well. According to Theorem 2.3 we can easily obtain the optimal solution of (PX ) once we have the optimal solution of (PP ). Theorem 2.3 ([14]) If x∗ ∈ X is an efficient solution of problem MOLP (P), y ∗ = P (x∗ ) ∈ Y is its corresponding nondominated point, and y ∗ is also a global optimal solution of problem (PP ), then x∗ is a global optimal solution of problem (PX ). Conversely, if x∗ is a global optimal solution of problem (PX ), then x∗ is also an efficient solution of problem MOLP (P), and y ∗ = P (x∗ ) is a global optimal solution of problem (PP ). As can be seen from Theorems 2.1 and 2.2, (PP ) always has a global optimal solution at a vertex of P and any global optimal solution must belong to YN . Therefore, multi-objective optimisation algorithms for finding YN can be used to solve multiplicative programming problems.

4

March 18, 2015

Optimization

20150317

We use the trivial observation of Proposition 2.4 for determining lower bounds and upper bounds of (PP ) in our proposed primal and dual algorithms. Proposition 2.4 If O ⊇ P ⊇ I, then the minimum value of T (y) over O is a lower bound and the minimum value of T (y) over I is an upper bound for T over P. The algorithms for MPPs developed in Section 3 explicitly or implicitly construct polyhedra O and I with O ⊇ P ⊇ I. Thus the minimum values of T (y) over O and I are always achieved at one of the vertices of O and I and are upper and lower bounds, respectively, for (PP ).

3.

Primal and dual objective space algorithms for linear MPPs

Geometric duality [17] defines a dual MOLP (D) for (P). (D) maxK D(u, λ) = (λ1 , ..., λp−1 , bT u + dT λ)T s.t. (u, λ) ∈ U = (u, λ) ∈ Rm × Rp : (u, λ) ≧ 0, AT u = C T λ, eT λ = 1 .

The primal problem (P) consists in finding the weakly nondominated points of P (X ), the dual problem consists in finding the K-maximal elements of D(U ). Let D := D(U )−K be the extended polyhedral objective set of problem (D). Geometric duality provides a relationship between the facial structure of the extended primal and dual feasible sets, i.e., P and D. Benson [16] proposed an outer approximation algorithm to solve MOLP (P) in objective space. Extensions of Benson’s algorithm can be found in [15] and [18]. Based on geometric duality theory, Ehrgott et al. [15] developed a dual variant of Benson’s outer approximation algorithm to solve the dual problem (D) in objective space. In fact, both the primal and dual variant Benson algorithms obtains all the facets and extreme points of P. Thus they can be directly used to solve linear MPPs by evaluating the minimum value of T (y) over vert P when the algorithms stop. However, to speed up the calculation and avoid the computation of all vertices of P, we use Proposition 2.4 to compute upper and lower bounds for T (y) and propose the following primal and dual objective space algorithms for linear MPPs. We show the advantages of our proposed algorithms in Section 4. 3.1.

Primal algorithm for solving linear MPPs

In our previous work, we have extended Benson’s outer approximation algorithm for MOLPs to solve convex multi-objective programming problems [13] and further the algorithm has been adapted to be an objective space cut and bound algorithm to solve convex multiplicative programmes [14]. We call the cut and bound algorithm “the primal algorithm”. The algorithm constructs a sequence of polyhedra S 0 ⊇ S 1 ⊇ . . . ⊇ S k ⊇ P approximating P from the outside. In iteration k we will evaluate T (y) at all vertices of S k . The smallest of these values is a lower bound on the optimal value of T (y) over P. Moreover, at each iteration a boundary point P (xk ) ∈ P is computed which provides an upper bound T (P (xk )) on the optimal value of (PP ). Combining the lower bound and the upper bound information, the idea of our primal algorithm for MPPs can be described as follows. Assume that individual minima of the functions Pi (x) = cTi x + di over X are attained at x0i for i = 1, 2, . . . , p. Let y 0i = P (x0i ) and let y I = (P1 (x01 ), P2 (x02 ),

5

March 18, 2015

Optimization

20150317

. . ., Pp (x0p ))T be the ideal point. Our primal algorithm starts with a polyhedron S 0 := y I + Rp≧ ⊇ P. The lower bound is initialised with LB := T (y I ). FurtherQ more the upper bound U B is set to be the minimum of pi=1 y 0i , i = 1, . . . , p. An approximation error ǫ ≧ 0 needs to be specified. In each iteration, we choose ¯ 1 (sk )) (see a vertex s ∈ vert S k with the minimal value T (s) as sk , compute (P k k below) and get the optimal solution (x , z ), with the boundary point P (xk ) of P. If T (P (xk )) < U B, then we update U B with T (P (xk )). If the relative difference between the upper bound and the lower bound is less than or equal to the approximation error ǫ, then the algorithm terminates. Otherwise, a hyperplane (cut) separating the vertex sk from P is added to the description of S k . We update the vertex set vert S k and calculate T (s) for each vertex s ∈ vert S and find the minimal value of T (s) among all the vertices of S k . If this is greater than the current lower bound, then we update the lower bound with T (s). If the relative difference between the upper bound and the lower bound is less than or equal to the approximation error ǫ, then the algorithm terminates. Otherwise the procedure is repeated. According to [18] and [19], the primal algorithm can be improved when solving linear MPP problems (PX ). Actually only one linear programme (LP) needs to be solved for finding the cut at each iteration step instead of two as the previous cut and bound algorithm indicates. The cut is based on the consideration of the following pair of dual linear programming problems and Theorem 3.1. ¯ 1 (y)) (P

¯ 1 (y)) (D

min

(x,z)∈S(y)

z,

S(y) := {(x, z) ∈ Rn × R : Ax ≧ b, Cx + d − ez ≦ y} ,

max (bT u−(y−d)T λ),

(u,λ)∈U

U = (u, λ) ∈ Rm × Rp : (u, λ) ≧ 0, AT u = C T λ, eT λ = 1 .

Theorem 3.1 ([13]) Let y k ∈ / P. Let (xk , z k ) be an optimal solution of linear k ∗ ¯ programme (P1 (y )), and (u , λ∗ ) be the corresponding dual optimal solution of ¯ 1 (y)). Let H = {y ∈ Rp : y T λ∗ = P (xk )T λ∗ }. Then H is a supporting hyperplane (D of P at P (xk ). Algorithm 3.2 summarises the steps of the algorithm.

6

March 18, 2015

Optimization

20150317

Algorithm 3.2 (Primal algorithm for linear MPPs) Initialisation. (i1) Compute an optimal solution x0i of min{Pi (x) : x ∈ X } for i = 1, . . . , p. Let y I = (P1 (x01 ), . . . , Pp (x0p ))T . Set S 0 := y I + Rp≧ , vert S 0 = {y I }. (i2) Set U B0 = min{T (P (x0i )), i = 1, . . . , p} and LB0 := T (y I ). (i3) Choose ǫ ≧ 0 and set k := 0. Iteration steps. (k1) Choose s ∈ vert S k with the minimal value T (s) as sk . Solve ¯ 1 (sk )), let (xk , z k ) be its optimal solution and (uk , λk ) be LP (P the corresponding dual optimal solution. (k2) If T (P (xk )) < U Bk , set U Bk := T (P (xk )), y u := P (xk ), xu := xk . (k3) If U Bk ≦ LBk (1 + ǫ), STOP. Otherwise, go to (k4). (k4) Set S k+1 := S k ∩ {y ∈ Rp : y T λk ≧ P (xk )T λk }. (k5) Determine vert S k+1 and set LBk := min{T (s) : s ∈ vert S k+1 }. If U Bk ≦ LBk (1 + ǫ), STOP. Otherwise, set k := k + 1, U Bk := U Bk−1 , LBk := LBk−1 and go to (k1). Result. (r1) If ǫ = 0 (ǫ > 0), then xu is a global optimal (ǫ-optimal) solution of problem (PX ), and y u is a global optimal (ǫ-optimal) solution of problem (PP ). Theorem 3.3 Algorithm 3.2 terminates after a finite number of iterations. If ǫ = 0 (ǫ > 0), then we have an optimal ( ǫ-optimal) solution of problem (PX ) at termination. Proof. The finiteness of Algorithm 3.2 is obvious because Benson’s algorithm is finite (see, e.g., [15], [16]). When the algorithm terminates, we have xu = xk , ¯ 1 (sk )). Then xk where (xk , z k ) is an optimal solution of the linear programme (P is a weakly efficient solution of MOLP (P) and the corresponding weakly nondominated point is P (xk ). Since T (P (xk )) is an upper bound value and the relative difference between the upper bound and the lower bound is less than or equal to the approximation error ǫ, if ǫ = 0 (ǫ > 0), then P (xk ) is also an optimal (ǫ-optimal) solution of (PP ). Thus, xu is an optimal (ǫ-optimal) solution of (PX ). Remark 3.4 Algorithm 3.2 explicitly constructs a sequence of polyhedra S k with S 1 ⊇ . . . ⊇ S k ⊇ P approximating P from the outside. Therefore according to Proposition 2.4, LBk = min{T (s) : s ∈ vert S k } is a sequence of increasing lower bounds on (PP ). Since we know vert S k , LBk is easy to compute. Remark 3.5 Let conv(P (xk )) be the convex hull of vertices P (xi ), i = 01 , . . . , 0p , 1, . . . , k. Let I k = conv(P (xk ))+ Rp≧ . Algorithm 3.2 implicitly constructs a sequence of polyhedra I k with I 1 ⊆ . . . ⊆ I k ⊆ P approximating P from the inside. Therefore according to Proposition 2.4, U Bk = min{T (s) : s ∈ vert I k } is a sequence of decreasing upper bounds on (PP ). Since we know vert I k , U Bk is easy to compute. Remark 3.6 In Algorithm 3.2, the vertices of S k are saved in vertex set array vert S k and they are updated at Step (k5) after the cut at each iteration. At Step (k1), actually any vertex s of S k with T (s) < U Bk can be picked as sk .

7

March 18, 2015

Optimization

20150317

For example, one can pick the first vertex s with T (s) < U Bk in the vertex set array vert S k as sk . However, in our algorithm we always use s ∈ vert S k with the minimal value T (s) as sk . Thus, the vertex s with the smallest T (s) among all the vertices of S is always being cut off. p Q T ci x : Ax ≧ b , where Example 3.7 Consider the linear MPP min i=1

21 8 1 1 6 10 ,b = 8. 1 2 C= ,A = 01 1 0 1 01 1 We solve it with the primal objective space algorithm. Figure 1 shows P and the changing of the outer approximation S. In the figure, we use empty triangles to represent upper bound points and filled squares to represent lower bound points at each iteration. As can be seen from the figure, after three cuts, we have S 3 = P and the two upper bound points (1,4) and (4,1)coincide with the two lower bound points. The total number of LPs solved is 5 (3 for the cuts and 2 for the ideal point). y2 8

y2 8

y2 8

y2 8

7

7

7

7

ut

6

ut

6

5

5

4

2

3

ut

r

0

1

2

3

4

5

6

7

8

y1

4

P

3

bc

ut r

0

1

2

3

4

5

6

7

0 8 0

y1

S3 = P

3 2

S 2ut

1

0

ut r

5 b

2

1

0

6 bc

4

P b

2

S0

1

5

S1 r

4

P

3

ut

6

1

r

1

2

3

4

5

6

7

0 8 0

y1

bc

1

2

3

4

ut b

r

5

6

7

Figure 1. P and the shrinking of S k with iteration k.

3.2.

Dual algorithm for solving linear MPPs

The idea for solving linear MPPs is to use lower bounds and upper bounds to limit the optimal objective value of (PP ). For that purpose outer and inner approximations of P need to be constructed. In the original dual Benson algorithm, a sequence of outer approximations of the extended feasible set in dual objective space is constructed. These outer approximations can be used to construct a sequence of inner approximations of P according to duality theory [20]. However, no outer approximations of P can be constructed from the original dual Benson algorithm. Therefore, we develop a sandwich version of the dual Benson algorithm, and then further adapt it to solve linear MPPs. 3.2.1.

Sandwich version of the dual Benson’s algorithm

Geometric duality theory [17] states that there is an inclusion reversing one-to-one map Ψ between the set of all proper K-maximal faces of D and the set of all proper

8

8

y1

March 18, 2015

Optimization

20150317

Rp≧ -minimal faces of P. The map Ψ is based on the two set-valued maps, H : Rp ⇉ Rp , H(v) := {y ∈ Rp : ϕ(y, v) = 0} , H∗ : Rp ⇉ Rp , H∗ (y) := {v ∈ Rp : ϕ(y, v) = 0} . where ϕ(y, v) =

p−1 X

y i vi + y p 1 −

p−1 X i=1

i=1

vi

!

− vp .

Based on geometric duality theory, Ehrgott et al. proposed a dual variant of Benson’s outer approximation algorithm to solve MOLP (D) and obtain all the facets and extreme points of P and D, respectively. For details of geometric duality theory and the original dual variant of Benson’s algorithm, the reader is referred to [17] and [15], respectively. Here we propose a sandwich version of the dual variant of Benson’s algorithm. Our algorithm not only gives a convex polyhedral outer approximation but also a convex polyhedral inner approximation of D during the iteration steps. By using the function ϕ(y, v), a polyhedral outer approximation and a polyhedral inner approximation of P can then be easily obtained. In the course of the algorithm, supporting hyperplanes of D are constructed. The following linear programming problem plays a key role in constructing hyperplanes. ¯ 2 (v)) (P

minλ(v)T P (x), x∈X

X := {x ∈ Rn : Ax ≧ b} ,

T P . where λ(v) := v1 , . . . , vp−1 , 1 − p−1 v i=1 i Proposition 3.8 is critical for finding supporting hyperplanes and it is also the basis for improving the original dual variant of Benson’s algorithm with only one LP to be solved at each iteration step. ¯ 2 (¯ Proposition 3.8 Let v¯ ∈ Rp satisfy λ(¯ v ) ≧ 0. There exists a solution to (P v )) ∗ ¯ 2 (¯ and for every solution x ¯ to ( P v )), H (P (¯ x )) is a supporting hyperplane of D I containing v b = v¯T p−1 , λ(¯ v )T P (¯ x) of D. 0 Proof. If v¯ ∈ maxK D, then the proof can be found in [19] and [15]. Since ¯ 2 (¯ ¯ 2 (v b )) have the same optimal solutions, we just need to show (P v )) and (P b ¯ 2 (¯ v ∈ maxK D. Suppose (P v )) has an optimal solution denoted by x ¯, and let u ¯ T Cx be the correspondingdual optimal solution. Strong duality implies λ(¯ v ) ¯ = Ip−1 Ip−1 T b T T T T b u ¯. Thus, v = v¯ , λ(¯ v ) P (¯ x)) = (¯ v , λ(¯ v ) (C x ¯ + d) = 0 0 I v¯T p−1 , λ(¯ v )T d + bT u ¯ ∈ maxK D holds. 0 Our sandwich version of the dual variant of Benson’s algorithm is shown in Algorithm 3.9.

9

March 18, 2015

Optimization

20150317

Algorithm 3.9 (Sandwich version of the dual variant of Benson’s algorithm for MOLPs) Initialisation. Compute an optimal solution x0i of min{Pi (x) : x ∈ X } for i = 1, . . . , p. Let y I = (P1 (x01 ), . . . , Pp (x0p ))T . Set O0 = {v ∈ Rp : λ(v) ≧ 0, ϕ(P (x0i ), v) ≧ 0} and compute vert O0 . Set I 0 = {v ∈ Rp : λ(v) ≧ 0, ϕ(y I , v) ≧ 0} and compute vert I 0 . Set k = 0. Iteration steps. (k1) If, for each v ∈ vert Ok , v ∈ I k is satisfied, then stop. Otherwise choose a vertex v k ∈ Ok \I k . k kb ¯ k (k2) Compute anoptimal solution x of (P2 (v )) and let v = T Ip−1 vk , λ(v k )T P (xk ) . 0 S kb (k3) Set vert I k+1 = vert I k {v }, update the inequality representation of I k+1 . If λ(v k )T P (xk ) < vpk , set Ok+1 := Ok ∩ {v ∈ Rp : ϕ(P (xk ), v) ≧ 0} else set Ok+1 := Ok . Update vert Ok+1 . (k4) Set k := k + 1 and go to (k1). At each iteration k, the hyperplane given by H∗ (P (xk )) = {v ∈ Rp : ϕ(P (xk ), v) = 0} is constructed so that it cuts off a portion of Ok containing v k and at the same time, point v kb is added to vert I k , thus O0 ⊇ O1 ⊇ O2 ⊇ . . . ⊇ Ok−2 ⊇ Ok−1 = D and I 0 ⊆ I 1 ⊆ I 2 ⊆ . . . ⊆ I k−2 ⊆ I k−1 = D. When the algorithm terminates, we have the following results. Proposition 3.10 (1) The set of K-maximal vertices of D is vert Ok−1 . ([15])p k−1 (2) The set y ∈ R : ϕ(y, v) ≧ 0 for all v ∈ vert O is a nondegenerate inequality representation of P. (3) All Rp≧ -minimal (nondominated) vertices of P are contained in the set W := {P (x01 ), . . ., P (x0p ), P (x1 ), . . . , P (xk−1 )}. (4) The set {v ∈ Rp : λ(v) ≧ 0, ϕ(y, v) ≧ 0 for all y ∈ W} is a (possibly degenerate) inequality representation of D. Proposition 3.10 suggests that we obtain both P and D when the algorithm terminates. Moreover, at each iteration using the function ϕ, vert O and vert I, an inner approximation and an outer approximation of P can be obtained. For that purpose, Property 3.11, Definition 3.12, Propositions 3.13 and 3.14 are needed. Property 3.11 ([20]) Let us consider special convex polyhedral sets S ⊆ Rp with the property that S = S −P K and the projection to its first p − 1 components is the polytope {t ∈ Rp−1 , t ≧ 0, p−1 i=1 ti ≦ 1}.

Definition 3.12 ([20]) For a polyhedral convex set S ⊆ Rp with Property 3.11, we define D(S) = {y ∈ Rp: ϕ(y, v) ≧ 0, for all v ∈ vert S}, where ϕ(y, v) = Pp−1 Pp−1 i=1 vi − vp . i=1 yi vi + yp 1 −

Proposition 3.13 ([20]) Let S ⊆ Rp with Property 3.11. Then D(S) = D(S) + Rp≧ .

10

March 18, 2015

Optimization

20150317

Proposition 3.14 ([20]) Let S 1 and S 0 be polyhedral convex sets with Property 3.11 and S 1 ⊆ S 0 , then D(S 1 ) ⊇ D(S 0 ). For the dual variant of Benson’s algorithm, Proposition 3.14 indicates that D(Ok ) enlarges and D(I k ) shrinks with the iteration count. When the algorithm terminates at iteration k, D(Ok−1 ) = D(I k−1 ) = D(D) = P. We give an example to illustrate the sandwich version of the dual variant of Benson’s algorithm and we show how Ok , I k , D(Ok ) and D(I k ) change with iteration k. Example 3.15 Consider the MOLP min{Cx : Ax ≧ b}, where C, A, b are the same as in Example 3.7. P and D are shown in Figure 2. The 5 vertices of D are (0, 1), ( 31 , 38 ), ( 12 , 3), ( 32 , 38 ), (1, 1). Their corresponding facets (supporting hyperplanes) of P are y2 = 1, y1 + 2y2 = 8, y1 + y2 = 6, 2y1 + y2 = 8, y1 = 1. The four vertices of P, (1, 6), (2, 4), (4, 2) and (6, 1) correspond to the facets (supporting hyperplanes) of D, 5v1 + v2 = 6,2v1 + v2 = 4, −2v1 + v2 = 1 and −5v1 + v2 = 1, respectively.

y28 3

7

b

b

6

b

b

v2

5

2

4

D

P b

3 1b

2

b

b

1 b

0 0

1

2

3

4

5

6

7

0

y81

0

1

v1

Figure 2. P and D for Example 3.15.

Figure 3 shows the change of Ok and I k with each iteration k. As can be seen, with iteration k, Ok becomes smaller and smaller, I k becomes bigger and bigger, until at termination both of them are the same as D. The vertices of O0 are (0, 1), ( 23 , 27 ) and (1, 1). The first hyperplane cuts off vertex ( 32 , 72 ), the vertices of O1 are (1, 1), (0, 1), ( 52 , 3), and ( 35 , 3). The second hyperplane cuts off vertex ( 35 , 3), thus the vertices of O2 are (0, 1), ( 25 , 3),( 12 , 3), ( 32 , 83 ) and (1, 1). The third hyperplane cuts off vertex ( 52 , 3), thus the vertices of O3 are (0, 1), ( 13 , 83 ), ( 21 , 3), ( 32 , 83 ) and (1, 1). After the third cut, we have O3 = D and the vertices of I 3 are (0, 1), 1 3 14 2 8 ( 25 , 14 5 ),( 2 , 3),( 5 , 5 ) and (1, 1). At the fourth iteration, vertex ( 3 , 3 ) is added to 1 8 5 4 vert I and at the fifth iteration vertex ( 3 , 3 ) is added to vert I . Therefore, after five iterations, we have O5 = I 5 = D. The change of D(Ok ) and D(I k ) after each iteration k can be seen in Figure 4. The calculation of D(S k ) (S k = Ok or I k ) is according to the definition D(S k ) = {y ∈ Rp : ϕ(y, v) ≧ 0 for all v ∈ vert S k }. For example, D(O0 ) = {y ∈ Rp : T ϕ(y, v) ≧ 0 for v = (0, 1), (1, 1)}, i.e., D(O0 ) = {y1 ≧ 1} {y2 ≧ 1}. In contrast to the shrinking of Ok and the enlargement of I k , D(Ok ) enlarges and D(I k ) shrinks with iteration k. When the sandwich version of the dual Benson algorithm terminates, O5 = I 5 = D and D(O5 ) = D(I 5 ) = D(D) = P.

11

March 18, 2015

Optimization

20150317

b

v2

v2

3

v2

3 b

bc

O0 2

bc

bc

b

1 b

bc

b

2

bc

bc

O2

b

2

1b b

bc

b

I2

bc

bc

b

b bc

2

I3

bc

bc

3

b bc

O3

1b

bbc

bc

v2

3

b

bc

b

I1

bc

v2

3

bbc

O1

2

1b

v2

3

b

bc

b bc

2

I5

1b

bbc bc

O5 bc

b bc

I4

1b b

b bc

O4

bbc bc

I0 0

0 0

v1

1

0 0

1

v1

0 0

Figure 3. The shrinking of

y2 8

7

6

6 b

5

0

1

v1

and the enlargement of

y2 8

7

0 0

D(O0 )

3

Ik

1 1

2

3

4

D(O1 )

4

6

7

8

D(I 1 )

6 5

1

2

3

4

5

6

7

8

y1

D(O3 ) b

3

0 1

2

3

4

5

6

7

8

y1

6

7

7

8

8

y1

b

D(I 5 )

2

D(I 4 ) b

1 0

5

b

1 b

b

0

0

0 0

1

2

3

4

5

D(O5 ) b

3

b

2 b

4

b

4

D(O4 ) b

3

b

1

3

5

4

D(I 3 )

2

2

y2 8 6

b

5

b

1

0

7

6

4

b

0

7 b

D(I 2 )

1

y2 8

7

b

2 b

0

y1

D(O2 ) b

3

b

1

5

b

5

0 0

v1

with iteration k.

6

2

0

1

y2 8

b

3

b

0

7

4

D(I 0 )

2

v1

1

5

4

y2 8

Ok

0

v1

1

6

7

1

2

3

4

5

6

8

y1

y1

Figure 4. The enlargement of D(O k ) and the shrinking of D(I k ) with iteration k.

Theorem 3.16 The sandwich version of the dual variant of Benson’s algorithm is finite. Proof. The point v kb ∈ D computed in iteration k belongs to Ok . If v kb ∈ int Ok , then we have Ok+1 := Ok ∩ {v ∈ Rp : ϕ(P (xk ), v) ≧ 0} and, by Proposition 3.8, we know that F := {v ∈ D : ϕ(P (xk ), v) = 0} is a face of D with v kb ∈ F, where F ⊆ bd Ok . If v kb ∈ bd Ok , then v kb ∈ bd D. Since D is polyhedral, it has a finite number of faces, hence the algorithm is finite. 3.2.2.

Dual algorithm for linear MPPs

Now we explain how to adapt the sandwich version of the dual Benson algorithm to solve linear multiplicative programmes (PX ). The idea of the dual algorithm for MPPs can be described as follows. The algorithm constructs a sequence of polyhedra Ok and I k sandwiching D. Therefore, D(Ok ) and D(I k ) are the inner approximation and outer approximation of P, respectively. In iteration k we evaluate T (y) at all vertices of D(Ok ) and D(I k ). The smallest of D(Ok ) is the upper bound, and the smallest of D(I k ) is the lower bound. The algorithm improves the lower bound and upper bound by iteratively constructing a cutting plane that cuts off some vertex of Ok not in D.

12

March 18, 2015

Optimization

20150317

Algorithm 3.17 (Dual algorithm for linear MPPs) Initialisation. (i1) Compute an optimal solution x0i of min{Pi (x) : x ∈ X } for i = 1, . . . , p. Let y I = (P1 (x01 ), . . . , Pp (x0p ))T . Set O0 = {v ∈ Rp : λ(v) ≧ 0, ϕ(P (x0i ), v) ≧ 0} and compute vert O0 . Set I 0 = {v ∈ Rp : λ(v) ≧ 0, ϕ(y I , v) ≧ 0} and compute vert I 0 . (i2) Let xu = arg min{T (P (x0i )), i = 1, . . . , p}. Set U B0 = T (P (xu )), y u = P (xu ). Set LB0 := T (y I ), y l = y I . (i3) Choose ǫ ≧ 0 and set k := 0. Iteration steps. (k1) Choose a vertex v k of Ok with v k ∈ / {v ∈ Rp : ϕ(y l , v) ≧ 0}. ¯ 2 (v k )), let xk be the optimal solution. Set vert I k+1 = Solve (P S Ip−1 k T vert I {(vk , λ(v k )T P (xk ))}, update the inequality 0 representation of I k+1 . (k2) If T (P (xk )) < U Bk , set U Bk := T (P (xk )), y u := P (xk ), xu := xk . (k3) If U Bk ≦ (1 + ǫ)LBk , STOP. Otherwise, go to (k4). (k4) Set Ok+1 := Ok ∩ {v ∈ Rp : ϕ(P (xk ), v) ≧ 0}, update vert Ok+1 . (k5) Compute vert D(I k+1 ). Let sk be the optimal solution of min{T (s) : s ∈ vert D(I k+1 )}. Set LBk := T (sk ), y l = sk . If U Bk ≦ (1 + ǫ)LBk , STOP. Otherwise, set k := k + 1, U Bk = U Bk−1 , LBk = LBk−1 and go to (k1). Result. (r1) If ǫ = 0 (ǫ > 0), then xu is a global optimal (ǫ-optimal) solution of problem (PX ), and y u is a global optimal (ǫ-optimal) solution of problem (PP ).

Theorem 3.18 Algorithm 3.17 terminates after a finite number of iterations. When ǫ = 0 (ǫ > 0), we have an optimal (ǫ-optimal) solution to problem (PX ) at termination. Proof. The algorithm is finite due to the finiteness of the sandwich version of the dual variant of Benson’s algorithm. When the algorithm terminates, we have ¯ 2 (v k )). xk xu = xk , where xk is an optimal solution of the linear programme (P k is a weakly efficient point of P and the corresponding point P (x ) ∈ PW N . Since T (P (xk )) is an upper bound value and the relative difference between the upper bound and the lower bound is less than or equal to the approximation error ǫ, if ǫ = 0 (ǫ > 0), then T (P (xk )) is an optimal (ǫ-optimal) solution of (PP ). Thus, xu is an optimal (ǫ-optimal) solution of (PX ). Remark 3.19 Algorithm 3.17 constructs a sequence of polyhedra I k with I 0 ⊇ . . . I k ⊇ D approximating D from the inside. Furthermore it explicitly constructs D(I k ) with D(I 0 ) ⊇ . . . ⊇ D(I k ) ⊇ P approximating P from the outside. Therefore according to Proposition 2.4, LBk = min{T (s) : s ∈ vert D(I k )} is a sequence of increasing lower bounds on (PP ). Since the vertices of I k are known, it is easy to obtain the facets of D(I k ) using the function ϕ. However to calculate LBk , extra vertex enumeration is needed to find vert D(I k ).

13

March 18, 2015

Optimization

20150317

Table 1. vert O k , vert I k , vert D(O k ), vert D(I k ), LBk , U Bk . k Set Vertices Set 0 vert O k (0,1),(1,1),( 12 , 27 ) vert I k vert D(O k ) (1, 6), (6, 1) vert D(I k ) vert I k 1 vert O k (0,1),(1,1),( 25 ,3),( 53 ,3) vert D(O k ) (1, 6), (3, 3), (6, 1) vert D(I k ) 2 vert O k (0,1),(1,1)( 25 ,3)( 12 ,3),( 23 , 83 ) vert I k vert D(O k ) (1,6),(2,4),(3,3),(6,1) vert D(I k ) 3 vert O k (0,1)( 13 , 38 ),( 21 ,3),( 23 , 38 ),(1,1) vert I k vert D(O k ) (1,6),(2,4),(4,2),(6,1) vert D(I k ) vert I k 4 vert O k (0,1)( 13 , 38 ),( 21 ,3),( 23 , 38 ),(1,1) vert D(O k ) (1,6),(2,4),,(4,2),(6,1) vert D(I k ) vert I k 5 vert O k (0,1)( 13 , 38 ),( 21 ,3),( 23 , 38 ),(1,1) vert D(O k ) (1,6),(2,4),(4,2),(6,1) vert D(I k )

Vertices (0,1),(1,1) (1, 1) (0,1),(1,1),( 12 ,3) (1, 5), (5, 1) (0,1),( 12 ,3),( 35 , 14 ),(1,1) 5 (1, 11 ),(2,4),(5,1) 2 (0,1),( 25 , 14 ),( 21 ,3),( 53 , 14 ),(1,1) 5 5 11 (1, 11 ),(2,4),(4,2),( ,1) 2 2 (0,1),( 25 , 14 ),( 21 ,3),( 32 , 83 ),(1,1) 5 ,1) (1,6),(2,4),(4,2),( 11 2 (0,1),( 13 , 83 ),( 12 ,3),( 32 , 38 ),(1,1) (1,6),(2,4),(4,2),(6,1)

LBk 1

U Bk 6

5

6

5

6

11 2

6

11 2

6

6

6

Remark 3.20 Let conv(P (xk )) be the convex hull of vertices P (xi ), i = 01 , . . . , 0p , 1, . . . , k. Let D(Ok ) = conv(P (xk )) + Rp≧ . Algorithm 3.17 constructs a sequence of polyhedra Ok with O0 ⊇ . . . Ok ⊇ D approximating D from the outside. It also implicitly constructs a sequence of polyhedra D(Ok ) with D(O0 ) ⊆ . . . ⊆ D(Ok ) ⊆ P approximating P from the inside. Therefore according to Proposition 2.4, U Bk = min{T (s) : s ∈ vert D(Ok )} is a sequence of decreasing upper bounds on (PP ). Since we know vert D(Ok ), U Bk is easy to compute. Remark 3.21 In Algorithm 3.17, the vertices of Ok are saved in vertex set array vert Ok and they are updated at Step (k4) after the cut at each iteration. At Step (k1), actually any vertex v of Ok with v ∈ / I k can be picked as v k . For example, one can pick the first vertex v in the vertex set array vert Ok with v ∈ / I k . However, in k k k our algorithm, we always pick a vertex v of O with v ∈ / {v ∈ Rp : ϕ(y l , v) ≧ 0}. l k Since y is one of the vertices of D(I ) with the smallest T (y), we actually try to improve the lower bound at every iteration. Next, we use Example 3.7 to illustrate Algorithm 3.17. The initialisation and the iteration steps are the same as in Example 3.15. We list the vertex set of Ok , I k , D(Ok ), D(I k ) and the lower bound and upper bound at each iteration in Table 1. The total number of LPs solved is 7.

4.

Numerical results

In Section 1 we have briefly outlined the literature on algorithms to solve multiplicative programming problems. In this section we compare our primal and dual algorithms presented in Section 3 with our original primal algorithm [14], a recent algorithm for linear MPP, i.e., Gao et al. [8], and two general purpose global optimisation solvers SCIP [21] and BARON [22, 23]. Of course, as we explained on page 5 both the primal and dual variant Benson algorithms for MOLPs can be used to solve linear MPPs directly. We carried out preliminary tests comparing Algorithms 3.2 and 3.17 to the application of the primal and dual variants of Benson’s algorithms to solve linear MPPs. Since in all but the smallest instances, Algorithms 3.2 and 3.17 were much faster, we do not report results on the primal and dual variants of Benson’s algorithm. We have implemented the first four algorithms in Matlab 7.3 using MOSEK (http://www.mosek.com) as linear programming and nonlinear programming solver. Tests are run on a PC with 2.5GHz and 4.0 GB RAM and the codes including Matlab and MOSEK are run in a single thread mode. At Step (k5) of

14

March 18, 2015

Optimization

20150317

Table 2. Results for (T), “-” means the problems cannot be solved within 20 minutes. p (m,n) Primal Dual Original Primal Gao et al. SCIP BARON 2 (20,30) 0.10 0.11 0.15 0.13 0.18 0.07 2 (50,30) 0.14 0.11 0.19 0.15 0.26 0.07 2 (100,60) 0.20 0.15 0.34 0.20 0.49 0.16 3 (50,30) 0.34 0.29 0.52 0.42 0.54 0.63 3 (60,40) 0.35 0.32 0.58 0.53 0.57 4.89 3 (100,60) 0.68 0.58 0.96 1.25 1.10 17.69 4 (60,40) 2.09 2.26 3.54 5.37 34.00 4 (100,60) 7.98 7.94 13.06 14.45 5 (100,60) 24.17 29.38 49.65 67.98 6 (100,60) 243.34 259.46 391.31 595.45 -

the primal algorithm and Step (k4) of the dual algorithm, the method of [24] for on-line vertex enumeration by adjacency lists was used to calculate a vertex representation from the inequality representation of S k+1 or Ok+1 . For all four algorithms, we use the same approximation error to make the results comparable. Moreover, we solve the test instances with SCIP and BARON. For SCIP, we have downloaded the binaries of SCIP-3.1.0 from http://scip.zib.de/, and run the tests on the same PC as the first four algorithms while for BARON the tests are run on NEOS Server (http://www.neos-server.org/neos). We apply the four algorithms and SCIP and BARON solvers to randomly generated examples of multiplicative programming problems. The following subclass of (PX ) is considered.

min

p Q

T

ci x

i=1

s.t. Ax ≧ b, u ≧ x ≧ l, where A ∈ Rm×n , b ∈ Rm and ci ∈ Rn are constant matrices with entries pseudorandomly generated in the interval [0,10]. Moreover, we set 0 = l ∈ Rn and (100, . . . , 100) = u ∈ Rn to make the instances bounded. Ten examples for selected combinations of m (number of constraints), n (number of variables) and p (number of objectives) were solved. For the first four algorithms, the approximation error was fixed at ǫ = 0.01. Average values of the CPU time in seconds are listed in Table 2. It can be seen from Table 2, that our primal and dual algorithms behave similarly. Our primal algorithm is always superior to the original primal algorithm because it solves only one LP at each iteration instead of two using the idea of [18]. When p is equal to two, the difference between our proposed primal and dual algorithms and Gao et al.’s algorithm is quite small and all three algorithms behave well. Because Gao et al.’s algorithm [8] needs to solve a nonlinear programming problem instead of a linear programming problem at each iteration, it requires more computation time compared to our algorithms. Therefore, if p is greater than or equal to three, our algorithms clearly outperform Gao et al.’s algorithm [8]. Compared to SCIP and BARON, when p is equal to two, BARON is faster than our algorithms. However as p increases, the computational performance of both SCIP and BARON becomes worse. Especially when p is equal to 4, BARON cannot solve any of the problems within 20 minutes. For m = 60 and n = 40 SCIP needs 34 seconds while our algorithms only use less than 3 seconds; for m = 100 and n = 60 SCIP cannot solve any of the problems within 20 minutes while our algorithms only use less than 8 seconds. For p equal to 5 and 6, both SCIP and BARON cannot solve any of the problems within 20 minutes, while our proposed

15

March 18, 2015

Optimization

20150317

primal and dual algorithms can solve each of the problems within 5 minutes. Table 2 suggests that the most critical factor influencing computation time is the number p of functions that make up the product φ(x). As p increases the computation time increases and more dramatically so for higher values of p than smaller ones. For example, for the problems with (m, n) = (100, 60) shown in Table 2, as p increases from 5 to 6, the computation times for our primal and dual algorithms increase tenfold.

5.

Conclusion

In this paper, we have proposed primal and dual objective space algorithms derived from objective space algorithms for multi-objective linear programming to solve linear multiplicative programming problems. The numerical results suggest that our algorithms are superior to recent global optimisation algorithms for linear MPPs as well as general global optimisation solvers. Therefore we have demonstrated the viability of a multi-objective linear programming approach to linear MPPs compared to single objective nonconvex global optimisation approaches. This may inspire researchers to investigate the use of multi-objective methods for other hard single objective optimisation methods. Moreover, our algorithms are easy to implement. Further research is needed to investigate the trade-off between solution quality and computational effort, in particular concerning the growth of computation time as p increases.

References [1] Matsui T. NP-hardness of linear multiplicative programming and related problems. Journal of Global Optimization. 1996;9:113–119. [2] Henderson JM, Quandt RE. Microeconomic Theory. McGraw-Hill, New York; 1971. [3] Konno H, Kuno T. Generalized linear multiplicative and fractional programming. Annals of Operations Research. 1990;25:147–162. [4] Maling K, Mueller SH, Heller WR. On finding most optimal optional rectangular package plans. In: Proceedings of the 19th Design Automation Conference; 1982. p. 663–670. [5] Geoffrion A. Solving bicriterion mathematical programs. Operations Research. 1967; 15:39–54. [6] Benson H, Boger GM. Outcome-space cutting-plane algorithm for linear multiplicative programming. Journal of Optimization Theory and Applications. 2000;104:301–322. [7] Kuno T. A finite branch-and-bound algorithm for linear multiplicative programming. Computational Optimization and Applications. 2001;20:119–135. [8] Gao Y, Xu C, Yang Y. An outcome-space finite algorithm for solving linear multiplicative programming. Applied Mathematics and Computation. 2006;179:494–505. [9] Ryoo HS, Sahindis NV. Global optimization of multiplicative programs. Journal of Global Optimization. 2003;26:387–418. [10] Kim NTB, Trang NTL, Yen TTH. Outcome-space outer approximation algorithm for linear multiplicative programming. East West Journal of Mathematics. 2007;9:81–98. [11] Depetrini D, Locatelli M. A FPTAS for a class of linear multiplicative problems. Computational Optimization and Applications. 2009;44:275–288. [12] Benson H, Boger GM. Multiplicative programming problems: analysis and efficient point search heuristic. Journal of Optimization Theory and Applications. 1997;94:487– 510. [13] Ehrgott M, Shao L, Sch¨ obel A. An approximation algorithm for convex multi-objective programming problems. Journal of Global Optimization. 2011;50:397–416.

16

March 18, 2015

Optimization

20150317

[14] Shao L, Ehrgott M. An objective space cut and bound algorithm for convex multiplicative programmes. Journal of Global Optimization. 2014;58:711–728; dOI:10.1007/s10898-013-0102-x. [15] Ehrgott M, L¨ ohne A, Shao L. A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming. Journal of Global Optimization. 2012;52:757–778. [16] Benson H. An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. Journal of Global Optimization. 1998;13:1–24. [17] Heyde F, L¨ ohne A. Geometric duality in multi-objective linear programming. SIAM J Optim. 2008;19(2):836–845. [18] Hamel AH, L¨ ohne A, Rudloff B. Benson type algorithms for linear vector optimization and applications. Journal of Global Optimization. 2014;59:811–836. [19] L¨ ohne A. Vector optimization with infimum and supremum. Springer; 2011. [20] Shao L, Ehrgott M. Approximating the nondominated set of an MOLP by approximately solving its dual problem. Mathematical Methods of Operations Research. 2008; 68:469–492. [21] Achterberg T. SCIP: Solving constraint integer programs. Mathematical Programming Computation. 2009;1(1):1–41; http://mpc.zib.de/index.php/MPC/article/view/4. [22] Sahinidis NV. BARON 12.1.0: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual. 2013. [23] Tawarmalani M, Sahinidis NV. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming. 2005;103:225–249. [24] Chen PC, Hansen P, Jaumard B. On-line and off-line vertex enumeration by adjacency lists. Operations Research Letters. 1991;10:403–409.

17