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 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 environment and tested over different instances randomly generated.
Accepté le :
DOI : 10.1051/ro/2014036
Mots-clés : Multiple criteria programming, fractional programming, Integer programming, efficient set
@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 = {http://archive.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 - http://archive.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 http://archive.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. http://archive.numdam.org/articles/10.1051/ro/2014036/
and , Optimizing a Linear Function over an Integer Efficient Set. Eur. J. Oper. Res. 174 (2006) 1140–1161. | DOI | Zbl
, Optimization over the Efficient Set. J. Math. Anal. Appl. 98 (1984) 562–580. | DOI | Zbl
, A finite Non adjacent Extreme Point Search Algorithm over the Efficient Set. J. Opt. Theor. Appl. 73 (1992) 47–64. | DOI | Zbl
and , Optimizing over the Efficient Set: Four Special Cases. J. Optim. Theor. Appl. 80 (1994) 3–18. | DOI | Zbl
and , A modified version of Martos’s algorithm for the linear fractional problem. Math. Oper. Res. 53 (1986) 33–44. | Zbl
and , A method for optimizing over the integer efficient set. J. Ind. Manag. Optim. 6 (2010) 811–823. | DOI | Zbl
, and , 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
and , Optimizing a Linear Function over an Efficient Set. J. Optim. Theor. Appl. 83 (1994) 541–563. | DOI | Zbl
and , Finding Efficient Points for Multi-objectve Linear Programs. Math. Program. 8 (1975) 375–377. | DOI
, Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22 (1968) 618–630. | DOI | Zbl
and , Multi-criteria integer linear programming problem. Cahiers du CERO 34 (1992) 51–68. | Zbl
, An algorithm for optimizing a linear function over an integer efficient set. Eur. J. Oper. Res. 195 (2009) 98–103. | DOI | Zbl
, 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).
, Algorithms for the vector maximization problem. Math. Program. 2 (1972) 207–229. | DOI | Zbl
, 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
, , 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
and , 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
and , 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
, Optimization over the Efficient Set: overview. J. Global Optim. 22 (2002) 285–317. | DOI | Zbl
Cité par Sources :
