Outer space branch and bound algorithm for solving linear multiplicative programming problems
- PDF / 469,967 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 188 Views
Outer space branch and bound algorithm for solving linear multiplicative programming problems Peiping Shen1,2
· Kaimin Wang2 · Ting Lu2
Received: 27 March 2019 / Accepted: 3 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we consider a linear multiplicative programming problem (LMP) that is known to be NP-hard even with one product term. We first introduce the auxiliary variables to obtain an equivalent problem of problem LMP. An outer space branch and bound algorithm is then designed, which integrates some basic operations such as the linear relaxation technique, branching rule and region reduction technique. The global convergence of the proposed algorithm is established by means of the subsequent solutions of a series of linear programming problems, and its computational complexity is estimated on the basis of the branching rule. Also, we discuss the relationship between the proposed linear relaxation and existing relaxations for LMP. Finally, preliminary numerical results demonstrate the proposed algorithm can efficiently find the globally optimal solutions for test instances. Keywords Linear multiplicative programming · Global optimization · Linear relaxation · Branch and bound Mathematics Subject Classification 90C30 · 90C33 · 90C15
1 Introduction Consider the following linear multiplicative problem: ⎧ p n n ⎪ ⎨ ci j x j + γi di j x j + θi max φ(x) = (LMP): i=1 j=1 j=1 ⎪ ⎩ s.t. x ∈ D = {x ∈ R n | Ax ≤ b, x ≥ 0}, where ci j , di j , γi , θi ∈ R, A ∈ R m×n , b ∈ R m , and D is bounded. Problem (LMP) is worth studying because some important special optimization problems that have been considered in literature fall into the category of (LMP), such as general
B
Peiping Shen [email protected]
1
School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, China
2
College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China
123
Journal of Global Optimization
quadratic programming [1,2], bilinear programming [3] and linear 0–1 programming [4], which can be converted to the problem (LMP) by utilizing some conversion techniques. Thus the applications of problem (LMP) include all of the applications of these problems, such as plant layout design [5], bond portfolio construction [6–8], engineering and financial optimization [9–13], decision tree optimization [14], VLISI chip design [15], robust optimization [16], network flows [17–19]. Additionally, problem (LMP) generally contains many optimal solutions that are not globally optimal, and so there exist significant theoretical and computational difficulties. For solving the generalized multiplicative programming problems, many optimization algorithms have been developed in the literature. Such as quadratic programming algorithms [2,20,21], finite algorithm [22], outcome-space approaches [23], approximate algorithms [24,25], cutting plane method [26], monotonic optimization approaches [10,27,28], bra
Data Loading...
