An Exact Method for Optimizing a Linear Function over an Integer efficient Set

AUTHOR(S):

Fatma Zohra Ouail Usthb, Mohamed El-amine Chergui, Mustapha Moulai Usthb

TITLE

An Exact Method for Optimizing a Linear Function over an Integer efficient Set

ABSTRACT

In this article, a new methodology is proposed to solve the problem of optimizing a linear function over an integer efficient set, noted (OI). The great challenges on it were its classification as NP-hard and that only three methods were introduced in the literature during decades treating this issue. We propose in this study a generalization of our method [8], wherein all efficient solutions of a multiobjective integer linear program (MOILP) are achieved. Based upon the well known branch and bound technique and strengthened by efficient tests, the proposed methodology succeeds to find an optimal solution in a finite number of steps. The main feature is that it greatly saturates nodes in the tree, thus a large number of feasible solutions can be avoided for optimality or efficiency purposes. Also, we have chosen Jorge method to perform a comparative study.

KEYWORDS

Multiobjective programming; integer efficient set; optimizing over efficient set

REFERENCES

[1] M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set, European Journal of Operational Research 174, 2006, pp. 1140-1161.

[2] M. Abbas and M. Moula¨ı, Solving multiple objective integer linear programming, Journal of the Italian Operations Research Society (Ricerca Operativa) 29, 1999, pp. 15-38.

[3] M. Abbas and D. Chaabane, An algorithm for solving multiple objective integer linear programming problem, RAIRO Operations Research 36, 2002, pp. 351-364.

[4] M. Abbas, Mohamed El-Amine Chergui and Meriem Ait Mehdi, Efficient cuts for generating the non-dominated vectors for Multiple Objective Integer Linear Programming, International Journal of Mathematics in Operational Research (IJMOR), Vol. 4, No. 3, 2012.

[5] H. Benson, Optimization over the efficient set, Journal of Mathematical Analysis and Applications 98, 1984, pp. 562-580.

[6] H. Benson, An algorithm for optimizing over the weakly efficient set, European Journal of Operational Research 25, 1986, pp. 192-199.

[7] H. Benson , A Bisection-Extreme Point Search Algorithm for Optimizing over the Efficient Set in the Linear Dependence Case, Discussion paper, 1992.

[8] M. E-A. Chergui , M. Moula¨ı and F.Z. Oua¨ıl, Solving the Multiple Objective Integer Linear Programming Problem, Modeling, Computation and Optimization in Information Systems and Management Sciences Communications in Computer and Information Science Volume 14, 2008, pp. 69-76, .

[9] M. E-A. Chergui and M. Moula¨ı, An exact method for a discrete multiobjective linear fractional optimization, Journal of Applied Mathematics and Decision Science, Vol. 2008, Article ID 760191, 12 pages.

[10] J, Ecker and I. Kouada, Finding efficient points for linear multiple objective programs, Mathematical Programming 8, 1975, pp. 375-377.

[11] J, Ecker and J.H. Song, Optimizing a linear function over an efficient set, Journal of Optimization Theory and Application Vol 83, , 1994, pp. 541-563.

[12] R. Gupta and R. Malhotra, Multi-criteria integer linear programming problem,Cahiers de CERO 34, , (1992), pp. 51-68.

[13] R. Gupta and R. Malhotra, Multi-criteria integer linear fractional programming problem, Optimization 35, 1995, pp. 373-389.

[14] Isermann, Computational experience concerning payoff tables and minimum criterion values over the efficient set, European Journal of Operational Research 33, 1987, pp. 91-97.

[15] H. Isermann, Proper efficiency and the linear vector maximization problem, Operations Research 22, 1974, pp. 189-191.

[16] J. Jorge, A bilinear algorithm for optimizing a linear function over the efficient set of a multiple objective linear programming problem, Journal of Global Optimization 31, 2005, pp. 1-16.

[17] J. Jorge, An algorithm for optimizing a linear function over an integer efficient set, European Journal of Operational Research 195, 2009, pp. 98-103.

[18] D. Klein and E. Hannan, An algorithm for multiple objective integer linear programming problem, European Journal of Operational Research 9, 1982, pp. 378-385.

[19] Kirlik, Gokhan and Sayin, Serpil, A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems, European Journal of Operational Research, 232, issue 3, 2014, pp. 479-488.

[20] N.C. Nguyen, An algorithm for optimizing a linear function over the integer efficient set, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 1992.

[21] M. Ozlen andM. Azizoglu,Multi-objective integer programming: A general approach for generating all non-dominated solutions, presented at European Journal of Operational Research, 2009, pp.25-35.

[22] J. Philip, Algorithm for the VectorMaximization Problem, Mathematical Programming 2, 1972, pp. 207-229.

[23] G.R. Reeves and R.C. Reid ,Minimum values over the efficient set in multiple objective decision making, European Journal of Operational Research 36, 1988, pp. 334-338.

[24] J. Sylva and A. Crema, A method for finding the set of non-dominated vectors for multiple objective integer linear programs, European Journal of Operational Research, in press, 2003.

[25] D.J.White ,The maximization of a function over the efficient set via a penalty function approach, European Journal of Operational Research 94, 1996, pp. 143-153.

Cite this paper

Fatma Zohra Ouail Usthb, Mohamed El-amine Chergui, Mustapha Moulai Usthb. (2017) An Exact Method for Optimizing a Linear Function over an Integer efficient Set. International Journal of Mathematical and Computational Methods, 2, 142-149