Solving multiobjective linear programming problems using ball center of polytopes

Document Type : ORO2013


Department of Applied Mathematics‎, ‎Faculty of Mathematics and Computer‎, ‎Shahid Bahonar University of Kerman‎, ‎Kerman‎, ‎Iran.


Here‎, ‎we aim to develop a new algorithm for solving a multiobjective linear programming problem‎. ‎The algorithm is to obtain a solution which approximately meets the decision maker's preferences‎. ‎It is proved that the proposed algorithm always converges to a weak efficient solution and at times converges to an efficient solution‎. ‎Numerical examples and a simulation study are used to illustrate the performance of the proposed algorithm‎.


Main Subjects

A. Abel and P. Korhonen, Using aspiration levels in an interactive interior multiobjective linear programming algorithm, European J. Oper. Res. 89 (1996), no. 1, 193--201.
B. Aghezzaf and T. Ouaderhman, An interactive interior point algorithm for multiobjective linear programming problems, Oper. Res. Lett. 29 (2001), no. 4, 163--170.
A. Arbel, An interior multiobjective linear programming algorithm, Comput. Oper. Res. 20 (1993), no. 7, 723--735.
A. Arbel and L. G. Vargas, Euclidean centers: computation, properties and a MOLP application, Math. Comput. Model. 48 (2008), no. 1-2, 197--205.
P. Armand, Finding all maximal efficient faces in multiobjective linear programming, Math. Program. 61 (1993), no. 3, 357--375.
P. Armand and C. Malivert, Determination of the efficient set in multiobjective linear programming, J. Optim. Theory Appl. 70 (1991), no. 3, 467--489.
D. S. Atkinson and P. M. Vaidya, A scaling technique for finding the weighted analytic center of a polytope, Math. Program. 57 (1992), no. 2, 163--192.
R. Benayoun, J. D. Montgolfier, J. Tergny and O. Laritchev, Linear programming with multiple objective functions: Step method (STEM), Math. Program. 1 (1971), no. 1, 366--375.
P. T. Boggs, P. D. Domich, J. R. Donaldson and C. Witzgall, Algorithmic enhancements to the method of centers for linear programming problems, INFORMS J. Comput. 1 (1989), no. 3, 159--171.
R. Caballero, M. Luque, J. Molina and F. Ruiz, MOPEN: A computational package for linear multiobjective and goal programming problems, Decis. Support Syst. 41 (2005) 160--175.
A. Cambini and L. Martein, Generalized Convexity and Optimization, Lecture Notes in Econom. and Math. Systems, 616, Springer-Verlag, Berlin, 2009.
H. K. Chen and H. W. Chou, Solving multiobjective linear programming problems- a generic approach, Fuzzy Sets and Systems 82 (1996), no. 1, 35--38.
J. G. Ecker, N. S. Hegner and I. A. Kouada, Generating all maximal efficient faces for multiple objective linear programs, J. Optim. Theory Appl. 30 (1980), no. 3, 353--381.
M. Ehrgott, Multicriteria Optimization, Springer-Verlag, Berlin, 2005.
M. Ehrgott and S. Ruzika, Improved constraint method for multiobjective programming, J. Optim. Theory Appl. 138 (2008), no. 3, 375--396.
J. T. Fagan and J. E. Falk, A method of Euclidean centers, Comput. Oper. Res. 23 (1996), no. 1, 13--25.
S. I. Gass and P. G. Roy, The compromise hypersphere for multiobjective linear programming, European J. Oper. Res. 144 (2003), no. 3, 459--479.
P. Huard, Resolution of mathematical programming with nonlinear constraints by the method of centers, in: J. Abadie (ed.), Nonlinear Programming, pp. 207--219, NorthHolland, Amsterdam, 1964.
P. G. Ipsilandis, Multiobjective linear programming model for scheduling linear repetitive projects, J. Constr. Eng. Manage. 133 (2007), no. 6, 417--424.
H. Isermann, The enumeration of the set of all efficient solutions for a linear multiple objective program, Oper. Res. Q. 28 (1977), no. 1, 711-725.
D. F. Jones and M. Tamiz, Practical Goal Programming, Springer, Berlin, 2010.
M. Luque, K. Miettinen, A. B. Ruiz and F. Ruiz, A two-slope achievement scalarizing function for interactive multiobjective optimization, Comput. Oper. Res. 39 (2012), no. 7, 1673--1681.
B. Metev and I. Yourdanov, Use of reference points for MOLP problems analysis, European J. Oper. Res. 68 (1993), no. 3, 374--378.
K. G. Murty, New Sphere Methods for LP, Tutorials in OR, INFORMS J. Comput. 2 (2009), no. 1, 62--80.
K. G. Murty and M. R. Oskoorouchi, Note on implementing the new sphere method for LP using matrix inversions sparingly, Optim. Lett. 3 (2009), no. 1, 137--160.
K. G. Murty and M. R. Oskoorouchi, Sphere Methods for LP, Algorithmic Oper. Res. 5 (2010), no. 1, 21--33.
L. Pourkarimi, M. A. Yaghoobi and M. Mashinchi, Determining maximal efficient faces in multiobjective linear programming problem, J. Math. Anal. Appl. 354 (2009), no. 1, 234--248.
F. Ruiz, M. Luque and J. Caballero, A classi_cation of the weighting schemes in reference point procedures for multiobjective programming, J. Oper. Res. Soc. 60 (2008), no. 4, 544--553.
L. Shao and M. Ehrgott, Approximating the nondominated set of an MOLP by approximately solving its dual problem, Math. Methods Oper. Res. 68 (2008), no. 2, 257--276.
G. Sonnevend, An analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in: A. Prekopa, J. Szelezsaan and B. Strazicky (eds.), System Modelling and Optimization, pp. 866--875, Lect. Notes Cont. Inf. Sci. 84, Springer, 1986.
R. E. Steuer, Multiple Criteria Optimization: Theory, Computation, and Application, Robert E. Krieger Publishing, Malabar, 1989.
E. Tarek, Method of centers algorithm for multi-objective programming problems, Acta Math. Sci. Ser. B Engl. Ed. 29 (2009), no. 5, 1128--1142.
T. B. Trafalis and R. M. Alkahtani, An interactive analytic center trade-off cutting plane algorithm for multiobjective linear programming, Comput. Ind. Eng. 37 (1999), no. 3, 649--669.
H. M. Winkels and M. Meika, An integration of efficiency projections into the Geoffrion approach for multiobjective linear programming, European J. Oper. Res. 16 (1984), no. 1, 113--127.
W. Xiao, Z. Liu, M. Jiang and Y. Shi, Multiobjective linear programming model on injection oil_eld recovery system, Comput. Math. Appl. 36 (1998), no. 5, 127--135.
P. L. Yu and M. Zeleny, The set of all nondominated solutions in linear cases and a multicriteria simplex method, J. Math. Anal. Appl. 49 (1975), no. 2, 430--468.
M. Zeleny, Linear Multiobjective Programming, Lecture Notes in Econom. and Math. Systems, 95, Springer-Verlag, Berlin-New York, 1974.
C. Zopounidis, D. K. Despotis and I. Kamaratou, Portfolio selection using the ADELAIS multiobjective linear programming system, Comput. Econ. 11 (1998), no. 3, 189--204.