A method for optimizing over the integer efficient set

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

October 2010, 6(4): 811-823. doi: 10.3934/jimo.2010.6.811

A method for optimizing over the integer efficient set

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

Received September 2009 Revised May 2010 Published September 2010

Abstract
Related Papers

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: Discrete Optimization, Efficient Set., Linear Programming, Multiple Objective Optimization.

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

Citation: Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial & Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811

References:

[1]	M. Abbas and D. Chaabane, An algorithm for solving multiple objective integer linear programming problem,, RAIRO Operations Research, 36 (2002), 351. doi: 10.1051/ro:2003006. Google Scholar
[2]	M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 174 (2006), 1140. doi: 10.1016/j.ejor.2005.02.072. Google Scholar
[3]	H. P. Benson, Existence of efficient solutions for vector maximization problems,, Journal of Optimization Theory and Appl, 26 (1978), 569. doi: 10.1007/BF00933152. Google Scholar
[4]	H. P. Benson and S. Sayin, Optimization over the efficient set: Four special cases,, Journal of Optimization Theory and Appl., 80 (1994), 3. doi: 10.1007/BF02196590. Google Scholar
[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. Google Scholar
[6]	Chaabane Djamal, "Contribution à l'Optimisation Multicritère en Variables Discrètes,", Ph.D thesis, (2007). Google Scholar
[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. doi: 10.1016/S0377-2217(03)00255-8. Google Scholar
[8]	G. B. Dantzig, On a linear programming combinatorial approach to the traveling salesman problem,, Operations Research, 7 (1959), 58. doi: 10.1287/opre.7.1.58. Google Scholar
[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. doi: 10.1007/BF02207641. Google Scholar
[10]	A. M. Geoffrion, Proper efficiency and the theory of vector maximization,, Journal of Mathematical Analysis and Applications, 22 (1968), 618. doi: 10.1016/0022-247X(68)90201-1. Google Scholar
[11]	R. Gupta and R. Malhotra, Multi-criteria integer linear programming problem,, Cahiers du CERO, 34 (1992), 51. Google Scholar
[12]	M. J. Jorge, An algorithm for optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 195 (2009), 98. doi: 10.1016/j.ejor.2008.02.005. Google Scholar
[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. doi: 10.1016/0377-2217(93)90190-X. Google Scholar
[14]	D. Klein and E. Hannan, An algorithm for multiple objective integer linear programming problem,, European Journal of Operational Research, 9 (1982), 378. doi: 10.1016/0377-2217(82)90182-5. Google Scholar
[15]	N. C. Nguyen, "An Algorithm for Optimizing a Linear Function Over the Integer Efficient Set,", Konrad-Zuse-Zentrum fur Informationstechnik Berlin, (1992). Google Scholar
[16]	J. Philip, Algorithms for the vector maximization problem,, Mathematical Programming, 2 (1972), 207. doi: 10.1007/BF01584543. Google Scholar
[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. doi: 10.1016/j.ejor.2006.02.049. Google Scholar
[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. doi: 10.1016/S0377-2217(99)00095-8. Google Scholar
[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. Google Scholar
[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. doi: 10.1016/0377-2217(95)00184-0. Google Scholar
[21]	Y. Yamamoto, Optimization over the efficient set, overview,, Journal of Global Optimization, 22 (2002), 285. Google Scholar

show all references

References:

[1]	M. Abbas and D. Chaabane, An algorithm for solving multiple objective integer linear programming problem,, RAIRO Operations Research, 36 (2002), 351. doi: 10.1051/ro:2003006. Google Scholar
[2]	M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 174 (2006), 1140. doi: 10.1016/j.ejor.2005.02.072. Google Scholar
[3]	H. P. Benson, Existence of efficient solutions for vector maximization problems,, Journal of Optimization Theory and Appl, 26 (1978), 569. doi: 10.1007/BF00933152. Google Scholar
[4]	H. P. Benson and S. Sayin, Optimization over the efficient set: Four special cases,, Journal of Optimization Theory and Appl., 80 (1994), 3. doi: 10.1007/BF02196590. Google Scholar
[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. Google Scholar
[6]	Chaabane Djamal, "Contribution à l'Optimisation Multicritère en Variables Discrètes,", Ph.D thesis, (2007). Google Scholar
[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. doi: 10.1016/S0377-2217(03)00255-8. Google Scholar
[8]	G. B. Dantzig, On a linear programming combinatorial approach to the traveling salesman problem,, Operations Research, 7 (1959), 58. doi: 10.1287/opre.7.1.58. Google Scholar
[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. doi: 10.1007/BF02207641. Google Scholar
[10]	A. M. Geoffrion, Proper efficiency and the theory of vector maximization,, Journal of Mathematical Analysis and Applications, 22 (1968), 618. doi: 10.1016/0022-247X(68)90201-1. Google Scholar
[11]	R. Gupta and R. Malhotra, Multi-criteria integer linear programming problem,, Cahiers du CERO, 34 (1992), 51. Google Scholar
[12]	M. J. Jorge, An algorithm for optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 195 (2009), 98. doi: 10.1016/j.ejor.2008.02.005. Google Scholar
[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. doi: 10.1016/0377-2217(93)90190-X. Google Scholar
[14]	D. Klein and E. Hannan, An algorithm for multiple objective integer linear programming problem,, European Journal of Operational Research, 9 (1982), 378. doi: 10.1016/0377-2217(82)90182-5. Google Scholar
[15]	N. C. Nguyen, "An Algorithm for Optimizing a Linear Function Over the Integer Efficient Set,", Konrad-Zuse-Zentrum fur Informationstechnik Berlin, (1992). Google Scholar
[16]	J. Philip, Algorithms for the vector maximization problem,, Mathematical Programming, 2 (1972), 207. doi: 10.1007/BF01584543. Google Scholar
[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. doi: 10.1016/j.ejor.2006.02.049. Google Scholar
[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. doi: 10.1016/S0377-2217(99)00095-8. Google Scholar
[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. Google Scholar
[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. doi: 10.1016/0377-2217(95)00184-0. Google Scholar
[21]	Y. Yamamoto, Optimization over the efficient set, overview,, Journal of Global Optimization, 22 (2002), 285. Google Scholar

[1]	Henri Bonnel, Ngoc Sang Pham. Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions. Journal of Industrial & Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789
[2]	Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417
[3]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[4]	Alireza Ghaffari Hadigheh, Tamás Terlaky. Generalized support set invariancy sensitivity analysis in linear optimization. Journal of Industrial & Management Optimization, 2006, 2 (1) : 1-18. doi: 10.3934/jimo.2006.2.1
[5]	Behrouz Kheirfam, Kamal mirnia. Comments on ''Generalized support set invariancy sensitivity analysis in linear optimization''. Journal of Industrial & Management Optimization, 2008, 4 (3) : 611-616. doi: 10.3934/jimo.2008.4.611
[6]	Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543
[7]	Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[8]	Artem Dudko. Computability of the Julia set. Nonrecurrent critical orbits. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2751-2778. doi: 10.3934/dcds.2014.34.2751
[9]	Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095
[10]	Jiawei Chen, Guangmin Wang, Xiaoqing Ou, Wenyan Zhang. Continuity of solutions mappings of parametric set optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2018138
[11]	Yu Zhang, Tao Chen. Minimax problems for set-valued mappings with set optimization. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 327-340. doi: 10.3934/naco.2014.4.327
[12]	Yue Qi, Zhihao Wang, Su Zhang. On analyzing and detecting multiple optima of portfolio optimization. Journal of Industrial & Management Optimization, 2018, 14 (1) : 309-323. doi: 10.3934/jimo.2017048
[13]	Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647
[14]	Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129
[15]	Sarah Ibri. An efficient distributed optimization and coordination protocol: Application to the emergency vehicle management. Journal of Industrial & Management Optimization, 2015, 11 (1) : 41-63. doi: 10.3934/jimo.2015.11.41
[16]	Ram U. Verma. General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 333-339. doi: 10.3934/naco.2011.1.333
[17]	Xueting Cui, Xiaoling Sun, Dan Sha. An empirical study on discrete optimization models for portfolio selection. Journal of Industrial & Management Optimization, 2009, 5 (1) : 33-46. doi: 10.3934/jimo.2009.5.33
[18]	Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[19]	Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767
[20]	Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences