A linear fractional optimization over an integer efficient set
Mahdi, Sara1 ; Chaabane, Djamal1
1 USTHB University, Faculty of Mathematics, Department of Operations Research, Bab-Ezzouar, BP32 El-Alia, 16122 Algiers, Algeria.
RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 265-278.

Mathematical optimization problems with a goal function, have many applications in various fields like financial sectors, management sciences and economic applications. Therefore, it is very important to have a powerful tool to solve such problems when the main criterion is not linear, particularly fractional, a ratio of two affine functions. In this paper, we propose an exact algorithm for optimizing a linear fractional function over the efficient set of a Multiple Objective Integer Linear Programming (MOILP) problem without having to enumerate all the efficient solutions. We iteratively add some constraints, that eliminate the undesirable (not interested) points and reduce, progressively, the admissible region. At each iteration, the solution is being evaluated at the reduced gradient cost vector and a new direction that improves the objective function is then defined. The algorithm was coded in MATLAB environment and tested over different instances randomly generated.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014036
Classification : 90C10, 90C26, 90C32, 90C29
Mots-clés : Multiple criteria programming, fractional programming, Integer programming, efficient set
Mahdi, Sara 1 ; Chaabane, Djamal 1

1 USTHB University, Faculty of Mathematics, Department of Operations Research, Bab-Ezzouar, BP32 El-Alia, 16122 Algiers, Algeria. 
@article{RO_2015__49_2_265_0,
     author = {Mahdi, Sara and Chaabane, Djamal},
     editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
     title = {A linear fractional optimization over an integer efficient set},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {265--278},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {2},
     year = {2015},
     doi = {10.1051/ro/2014036},
     zbl = {1310.90075},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2014036/}
}
TY  - JOUR
AU  - Mahdi, Sara
AU  - Chaabane, Djamal
ED  - Blazewicz, Jacek
ED  - Pesch, Erwin
ED  - Philipps, Cynthia
ED  - Trystram, Denis
ED  - Zhang, Guochuan
TI  - A linear fractional optimization over an integer efficient set
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 265
EP  - 278
VL  - 49
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2014036/
DO  - 10.1051/ro/2014036
LA  - en
ID  - RO_2015__49_2_265_0
ER  - 
%0 Journal Article
%A Mahdi, Sara
%A Chaabane, Djamal
%E Blazewicz, Jacek
%E Pesch, Erwin
%E Philipps, Cynthia
%E Trystram, Denis
%E Zhang, Guochuan
%T A linear fractional optimization over an integer efficient set
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 265-278
%V 49
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2014036/
%R 10.1051/ro/2014036
%G en
%F RO_2015__49_2_265_0
Mahdi, Sara; Chaabane, Djamal. A linear fractional optimization over an integer efficient set. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 265-278. doi : 10.1051/ro/2014036. https://www.numdam.org/articles/10.1051/ro/2014036/

M. Abbas and D. Chaabane, Optimizing a Linear Function over an Integer Efficient Set. Eur. J. Oper. Res. 174 (2006) 1140–1161. | DOI | Zbl

H.P. Benson, Optimization over the Efficient Set. J. Math. Anal. Appl. 98 (1984) 562–580. | DOI | Zbl

H.P. Benson, A finite Non adjacent Extreme Point Search Algorithm over the Efficient Set. J. Opt. Theor. Appl. 73 (1992) 47–64. | DOI | Zbl

H.P. Benson and S. Sayin, Optimizing over the Efficient Set: Four Special Cases. J. Optim. Theor. Appl. 80 (1994) 3–18. | DOI | Zbl

A. Cambini and L. Martein, A modified version of Martos’s algorithm for the linear fractional problem. Math. Oper. Res. 53 (1986) 33–44. | Zbl

D. Chaabane and M. Pirlot, A method for optimizing over the integer efficient set. J. Ind. Manag. Optim. 6 (2010) 811–823. | DOI | Zbl

D. Chaabane, B. Brahmi and Z. Ramdani, The augmented weighted Tchebychev norm for optimizing a linear function over an integer efficient set of a multicriteria linear program. Int. Trans. Oper. Res. 00 (2012) 1–15. | Zbl

J.G. Ecker and J.H. Song, Optimizing a Linear Function over an Efficient Set. J. Optim. Theor. Appl. 83 (1994) 541–563. | DOI | Zbl

J.G. Ecker and I.A. Kouada, Finding Efficient Points for Multi-objectve Linear Programs. Math. Program. 8 (1975) 375–377. | DOI

A.M. Geoffrion, Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22 (1968) 618–630. | DOI | Zbl

R. Gupta and R. Malhotra, Multi-criteria integer linear programming problem. Cahiers du CERO 34 (1992) 51–68. | Zbl

J.M. Jorge, An algorithm for optimizing a linear function over an integer efficient set. Eur. J. Oper. Res. 195 (2009) 98–103. | DOI | Zbl

B. Martos, Hyperbolic Programming. Naval Res. Logist. Quart. 11 (1964) 135–155. | DOI | Zbl

N.C. Nguyen, An Algorithm for Optimizing a Linear Function over the Integer Efficient Set. Konrad-Zuse-zentrum fur Informationstechnik, Berlin (1992).

J. Philip, Algorithms for the vector maximization problem. Math. Program. 2 (1972) 207–229. | DOI | Zbl

S. Sayin, Optimizing over the Efficient Set using a Top-Down Search of Faces. Oper. Res. 48 (2000) 65–72. | DOI | Zbl

R.E. Steuer, Multiple Criteria Optimization : Theory, Computation and Application. John Wiley & Sons, New York (1986). | Zbl

J. Sylva, A. Crema, A method for finding the set of non-dominated vectors for multiple objective integer linear programs. Eur. J. Oper. Res. 158 (2004) 46–55. | DOI | Zbl

J. Sylva and A. Crema, A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs. Eur. J. Oper. Res. 180 (2007) 1011–1027. | DOI | Zbl

J. Teghem and P. Kunsch, A survey of techniques for finding efficient solutions to multi-objective integer linear programming. Asia Pac. J. Oper. Res. 3 (1986) 95–108. | Zbl

L.A. Wolsey, Integer Programming. Wiley-Interscience publication, New York (1998). | Zbl

Y. Yamamoto, Optimization over the Efficient Set: overview. J. Global Optim. 22 (2002) 285–317. | DOI | Zbl

Cité par Sources :