A method for optimizing over the integer efficient set

Chaabane Djamal; Pirlot Marc

doi:10.3934/jimo.2010.6.811

Article Contents

2010, Volume 6, Issue 4: 811-823. Doi: 10.3934/jimo.2010.6.811

This issue Previous Article Externality of contracts on supply chains with two suppliers and a common retailer Next Article An exterior point linear programming method based on inclusive normal cones

A method for optimizing over the integer efficient set

Chaabane Djamal^1, and
Pirlot Marc^2,

1.
USTHB - Faculty of Mathematics - Operations Research Department, Bp 32 El Alia, BEZ, Algiers, 16121
2.
UMONS, Faculté Polytechnique, 9 Rue Houdain-Mons, Mons 7000

Received: August 31, 2009

Revised: April 30, 2010

Published: September 2010

Abstract Related Papers Cited by

Abstract

In this paper, we are interested in optimizing a linear function on the set of efficient solutions of a Multiple Objective Integer Linear Programming problem ($MOILP $). We propose an exact algorithm for maximizing a linear function denoted $ \phi $ on the set of efficient solutions of a $MOILP$ problem without having to enumerate explicitly all the elements of this set. Two techniques are used: the first is to reduce progressively the admissible domain by adding more constraints eliminating all the dominated points by the current solution; the second, when the new solution obtained by maximizing the function $\phi $ in the reduced area is not efficient, an exploration procedure is applied over the edges incident to this solution in order to find new alternative efficient solutions if they exist. The algorithm produces not only an optimal value of the linear function but also a subset of non-dominated solutions in the direction of $\phi$ that can be helpful in the practice.

Keywords:

Mathematics Subject Classification: Primary: 90C29, 90C26; Secondary: 90C10.

Citation:

Related Papers

Cited by

References

[1]	M. Abbas and D. Chaabane, An algorithm for solving multiple objective integer linear programming problem, RAIRO Operations Research, 36 (2002), 351-364.doi: 10.1051/ro:2003006.
[2]	M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set, European Journal of Operational Research, 174 (2006), 1140-1161.doi: 10.1016/j.ejor.2005.02.072.
[3]	H. P. Benson, Existence of efficient solutions for vector maximization problems, Journal of Optimization Theory and Appl, 26 (1978), 569-580.doi: 10.1007/BF00933152.
[4]	H. P. Benson and S. Sayin, Optimization over the efficient set: Four special cases, Journal of Optimization Theory and Appl., 80 (1994), 3-18.doi: 10.1007/BF02196590.
[5]	V. J. Bowman, On the relationship of the Tchebytcheff norm and the efficient frontier of multiple-criteria objectives, Lecture Notes in Economics and Mathematical Systems, 130 (1976), 76-85.
[6]	Chaabane Djamal, "Contribution à l'Optimisation Multicritère en Variables Discrètes," Ph.D thesis, UMONS, Polytechnic Faculty of Mons, Belgium, 2007.
[7]	A. Crema and J. Sylva, A method for finding the set of non-dominated vectors for multiple objective integer linear programs, European Journal of Operational Research, 158 (2004), 46-55.doi: 10.1016/S0377-2217(03)00255-8.
[8]	G. B. Dantzig, On a linear programming combinatorial approach to the traveling salesman problem, Operations Research, 7 (1959), 58-66.doi: 10.1287/opre.7.1.58.
[9]	J. G. Ecker and J. H. Song, Optimizing a linear function over an efficient set, Journal of Optimization Theory and Applications, 83 (1994), 541-563.doi: 10.1007/BF02207641.
[10]	A. M. Geoffrion, Proper efficiency and the theory of vector maximization, Journal of Mathematical Analysis and Applications, 22 (1968), 618-630.doi: 10.1016/0022-247X(68)90201-1.
[11]	R. Gupta and R. Malhotra, Multi-criteria integer linear programming problem, Cahiers du CERO, 34 (1992), 51-68.
[12]	M. J. Jorge, An algorithm for optimizing a linear function over an integer efficient set, European Journal of Operational Research, 195 (2009), 98-103.doi: 10.1016/j.ejor.2008.02.005.
[13]	J. N. Karaivanova and S. C. Narula, An interactive procedure for multiple objective integer linear programming problems, European Journal of Operational Research, 68 (1993), 344-351.doi: 10.1016/0377-2217(93)90190-X.
[14]	D. Klein and E. Hannan, An algorithm for multiple objective integer linear programming problem, European Journal of Operational Research, 9 (1982), 378-385.doi: 10.1016/0377-2217(82)90182-5.
[15]	N. C. Nguyen, "An Algorithm for Optimizing a Linear Function Over the Integer Efficient Set," Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 1992.
[16]	J. Philip, Algorithms for the vector maximization problem, Mathematical Programming, 2 (1972), 207-229.doi: 10.1007/BF01584543.
[17]	J. Sylva and A. Crema, A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs, European Journal of Operational Reserach, 180 (2007), 1011-1027.doi: 10.1016/j.ejor.2006.02.049.
[18]	Ta Van Tu, Optimization over the efficient set of a parametric multiple objective linear programming problem, European Journal of Operational Reserach, 122 (2000), 570-583.doi: 10.1016/S0377-2217(99)00095-8.
[19]	J. Teghem and P. Kunsch, A survey of techniques for finding efficient solutions to multiobjective integer linear programming, Asia Pacific Journal of Operations Research, 3 (1986), 95-108.
[20]	D. J. White, The maximization of a function over the efficient set via a penalty function approach, European Journal of Operational Research, 94 (1996), 143-153.doi: 10.1016/0377-2217(95)00184-0.
[21]	Y. Yamamoto, Optimization over the efficient set, overview, Journal of Global Optimization, 22 (2002), 285-317.