Enhancing computations of nondominated solutions in MOLFP via reference points
- PDF / 331,168 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 27 Downloads / 189 Views
Enhancing computations of nondominated solutions in MOLFP via reference points João Paulo Costa · Maria João Alves
Received: 19 April 2013 / Accepted: 23 April 2013 © Springer Science+Business Media New York 2013
Abstract In previous work, Costa and Alves (J Math Sci 161:(6)820–831, 2009; 2011) have presented Branch & Bound and Branch & Cut techniques that allow for the effective computation of nondominated solutions, associated with reference points, of multi-objective linear fractional programming (MOLFP) problems of medium dimensions (ten objective functions, hundreds of variables and constraints). In this paper we present some results that enhance those computations. Firstly, it is proved that the use of a special kind of achievement scalarizing function guarantees that the computation error does not depend on the dimension of the problem. Secondly, a new cut for the Branch & Cut technique is presented. The proof that this new cut is better than the one in Costa and Alves (2011) is presented, guaranteeing that it reduces the region to explore. Some computational tests to assess the impact of the new cut on the performance of the Branch & Cut technique are presented. Keywords Multiple objective fractional programming · Reference points · Branch and Cut
1 Introduction A multiobjective linear fractional programming (MOLFP) problem can be formulated as follows [13]:
This work has been partially supported by FCT under project grant Pest-C/EEI/UI0308/2011, and by project EMSURE-Energy and Mobility for Sustainable Regions (CENTRO-07-0224-FEDER-002004). We would also like to recognize the support from the Faculty of Economics of University of Coimbra under the initiative “40th Anniversary of FEUC”. J. P. Costa (B) · M. J. Alves Faculty of Economics of University of Coimbra, INESC Coimbra, Av. Dias da Silva, 165, 3004-512 Coimbra, Portugal e-mail: [email protected] M. J. Alves e-mail: [email protected]
123
J Glob Optim
cpx + αp c1 x + α1 max z 1 = 1 , . . . , max z p = p d x + β1 d x + βp s.t. x ∈ S = x ∈ Rn |Ax = b, x ≥ 0
(1)
where ck , d k ∈ Rn ; αk , βk ∈ R, k = 1, . . . , p; A ∈ Rm×n ; b ∈ Rm . It is assume k that d x + βk > 0 for all x ∈ S, k = 1, . . . , p and S is bounded. Let z = z (x) = z 1 (x) , . . . , z p (x) denote the image vector of x in the objective function space, and define Z = {z ∈ R p : z = z (x) , x ∈ S}. A point x 1 ∈ S is weakly-nondominated if and only if there does not exist another point x ∈ S such that z k (x) > z k x 1 for all k = 1, . . . , p . A point x 1 ∈ S is nondominated if and only if there does not exist another point x ∈ S such that z k (x) ≥ z k x 1 , for k = 1, . . . , p, 1 and z k (x) > z k x for at least one k. A comprehensive description of the properties and applications of fractional programming, either mono-criterion or multicriteria (multiobjective), can be found in [12]. Kornbluth and Steuer [7] presented the fundamental characteristics of multiobjective linear fractional programming considering both strongly and weakly nondominated concept
Data Loading...
