Generalized algorithms for solving problems of discrete, integer, and Boolean programming are discussed. These algorithms are associated with the method of normalized functions and are based on a combination of formal and heuristic procedures. This allows one to obtain quasi-optimal solutions after a small number of steps, overcoming the NP -completeness of discrete optimization problems. Questions of constructing so-called “duplicate” algorithms are considered to improve the quality of discrete problem solutions. An approach to solving discrete problems with fuzzy coefficients in objective functions and constraints on the basis of modifying the generalized algorithms is considered. Questions of applying the generalized algorithms to solve multicriteria discrete problems are also discussed. The results of the paper are of a universal character and can be applied to the design, planning, operation, and control of systems and processes of different purposes. The results of the paper are already being used to solve power engineering problems.
KeywordsDiscrete OptimizationMethod of Normalized FunctionsDuplicate AlgorithmsFuzzy CoefficientsInterrelated ModelsMultiobjective Decision Making
Taha, H.A. (1982) Operations Research: An Introduction. 3rd Edition, Macmillan Publishing, New York.
Brown, D.E. and White, C.C. (1990) Operations Research and Artificial Intelligence: The Integration of Problem-Solving Strategies. Kluwer Academic Publishers, London. http://dx.doi.org/10.1007/978-94-009-2203-7
Ekel, P.Ya. (1990) Models and Methods of Discrete Optimization of Power Supply Systems. KPI, Kiev. (In Russian)
Korbut, A.A. and Finkelshtein, Yu.Yu. (1984) Approximate Methods of Discrete Programming. Soviet Journal of Computer and System Sciences, 22, 155-167.
Garey, M.A. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP—Completeness. W.H. Freeman, New York.
Papadimitrou, C.H. and Steiglitz, K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs.
Berzin, E.A. (1974) Optimal Resource Allocation and Elements of System Synthesis. Russkoe Radio, Moscow. (In Russian)
Dobson, G. (1982) Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data. Mathematics of Operations Research, 7, 515-531. http://dx.doi.org/10.1287/moor.7.4.515
Syslo, M., Deo, N., and Kowalik, J.S. (1983) Discrete Optimization Algorithms with Pascal Programs. Prentice-Hall, Englewood Cliffs.
Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009) Introduction to Algorithms. 3rd Edition, MIT Press, Cambridge, MA.
French, S. (1995) Uncertainty and Imprecision: Modelling and Analysis. Journal of the Operational Research Society, 7, 70-79. http://dx.doi.org/10.1057/jors.1995.8
Zimmermann, H. (2000) An Application-Oriented View of Modeling Uncertainty. European Journal of Operational Research, 122, 190-198. http://dx.doi.org/10.1016/S0377-2217(99)00228-3
Antunes, C.H. and Dias, C.L. (2007) Editorial: Managing Uncertainty in Decision Support Models. European Journal of Operational Research, 181, 1425-1426. http://dx.doi.org/10.1016/j.ejor.2006.03.049
Pedrycz, W. and Gomide, F. (1998) An Introduction to Fuzzy Sets: Analysis and Design. MIT Press, Cambridge, MA.
Ekel, P.Ya. (2202) Fuzzy Sets and Models of Decision Making. Computers and Mathematics with Applications, 44, 863-875. http://dx.doi.org/10.1016/S0898-1221(02)00199-2
Pedrycz, W., Ekel, P. and Parreiras, R. (2011) Fuzzy Multicriteria Decision-Making: Models, Methods, and Applications. John Wiley & Sons, Chichester.
Zorin, V.V. and Ekel, P.Ya. (1980) Discrete-Optimization Methods for Electrical Supply Systems. Power Engineering, 18, 19-30.
Ibaraki, T. (1976) Integer Programming Formulation of Combinatorial Optimization. Discrete Mathematics, 16, 39-42. http://dx.doi.org/10.1016/0012-365X(76)90091-1
Ekel, P.Ya. and Neto, F.H.S. (2006) Algorithms of Discrete Optimization and Their Applications to Problems with Fuzzy Coefficients. Information Sciences, 176, 2846-2868. http://dx.doi.org/10.1016/j.ins.2005.06.001
Hu, T.C. (1969) Integer Programming and Network Flows. Addison-Wesley, New York.
Ausiello, G., Crescenzi, P., Gambosi, G., Kan, V., Marchetti-Spaccamela, A. and Protasi, M. (1999) Complexity and Approximation. Springer, Berlin. http://dx.doi.org/10.1007/978-3-642-58412-1
Band-Jensen, J., Gutin, G. and Yeo, A. (2004) When the Greedy Algorithm Fails. Discrete Optimization, 1, 121-127. http://dx.doi.org/10.1016/j.disopt.2004.03.007
Orlovsky, S.A. (1981) Problems of Decision Making with Fuzzy Information. Nauka, Moscow. (in Russian)
Delgado, M. (1994) Fuzzy Optimization: Recent Advances. Physica-Verlag, Heidelberg.
Herrera, F. and Verdegay, J.L. (1995) Three Models of Fuzzy Integer Linear Programming. European Journal of Operations Research, 83, 581-593. http://dx.doi.org/10.1016/0377-2217(93)E0338-X
Herrera, F. and Verdegay, J.L. (1996) Fuzzy Boolean Programming Problems with Fuzzy Costs: A General Study. Fuzzy Sets and Systems, 81, 57-76. http://dx.doi.org/10.1016/0165-0114(94)00324-6
Ekel, P., Pedrycz, W. and Schinzinger, R. (1998) A General Approach to Solving a Wide Class of Fuzzy Optimization Problems. Fuzzy Sets and Systems, 97, 49-66. http://dx.doi.org/10.1016/S0165-0114(96)00334-X
Dubois, D. and Prade, H. (1979) Fuzzy Real Algebra: Some Results. Fuzzy Sets and Systems, 2, 327-348. http://dx.doi.org/10.1016/0165-0114(79)90005-8
Chen, S.J. and Hwang, C.L. (1992) Fuzzy Multiple Attribute Decision Making: Methods and Applications. Springer, New York. http://dx.doi.org/10.1007/978-3-642-46768-4
Lee-Kwang, H. (1999) A Method for Ranking Fuzzy Numbers and Its Application to Decision-Making. IEEE Transactions on Fuzzy Systems, 7, 677-685. http://dx.doi.org/10.1109/91.811235
Wang, K. and Kerre, E.E. (2001) Reasonable Properties for the Ordering of Fuzzy Quantities (I). Fuzzy Sets and Systems, 118, 375-385. http://dx.doi.org/10.1016/S0165-0114(99)00062-7
Horiuchi, K. and Tamura, N. (1998) VSOP Fuzzy Numbers and Their Fuzzy Ordering. Fuzzy Sets and Systems, 93, 197-210. http://dx.doi.org/10.1016/S0165-0114(96)00206-0
Galperin, E.A. and Ekel, P.Ya. (2005) Synthetic Realization Approach to Fuzzy Global Optimization via Gamma Algorithm. Mathematical and Computer Modelling, 41, 1457-1468. http://dx.doi.org/10.1016/j.mcm.2004.02.039
Abbasbandy, S. and Hajjari, T. (2009) A New Approach for Ranking of Trapezoidal Fuzzy Numbers. Computers and Mathematics with Applications, 57, 413-419. http://dx.doi.org/10.1016/j.camwa.2008.10.090
Sadi-Nezhad, S. and Shahnazari-Shahrezaei, P. (2013) Ranking Fuzzy Numbers Using Preference Ratio: A Utility Function Approach. Decision Science Letters, 2, 149-162. http://dx.doi.org/10.5267/j.dsl.2013.03.002
Cheng, C.H. (1998) A New Approach for Ranking Fuzzy Numbers by Distance Methods. Fuzzy Sets and Systems, 95, 307-313. http://dx.doi.org/10.1016/s0165-0114(96)00272-2
Fodor, J. and Roubens, M. (1994) Fuzzy Preference Modelling and Multicriteria Decision Support. Kluwer Academic Publishers, Boston. http://dx.doi.org/10.1007/978-94-017-1648-2
Parreiras, R. and Ekel, P. (2013) Construction of Nonreciprocal Fuzzy Preference Relations with the Use of Preference Functions. Pesquisa Operacional, 33, 305-323. http://dx.doi.org/10.1590/S0101-74382013000200010
Kokshenev, I., Parreiras, R.O., Ekel, P.Ya., Alves, G.B. and Menicucci, S.V. (2015) A Web-Based Decision Support Center for Electrical Energy Companies. IEEE Transactions on Fuzzy Systems, 23, 16-28. http://dx.doi.org/10.1109/TFUZZ.2014.2312984
Zhang, Q., Chena, J.C.H. and Chong, P.P. (2004) Decision Consolidation: Criteria Weight Determination Using Multiple Preference Formats. Decision Support Systems, 38, 247-258. http://dx.doi.org/10.1016/S0167-9236(03)00094-0
Zhang, Q., Wang, Y. and Yang, Y. (2007) Fuzzy Multiple Attribute Decision Making with Eight Types Of Preference Information. Proceedings of 2007 IEEE Symposium on Computational Intelligence in Multicriteria Decision Making, Honolulu, 1-5 April 2007, 288-293. http://dx.doi.org/10.1109/MCDM.2007.369103
Herrera-Viedma, E., Herrera, F. and Chiclana, F. (2002) A Consensus Model for Multiperson Decision Making with Different Preferences Structures. IEEE Transactions on Systems, Man and Cybernetics, 32, 394-402. http://dx.doi.org/10.1109/TSMCA.2002.802821
Yager, R.R. (1988) On Ordered Weighted Averaging Aggregation Operators in Multi-Criteria Decision Making. IEEE Transactions on Systems, Man and Cybernetics, 18, 183-190. http://dx.doi.org/10.1109/21.87068
Li, W.X. and Li, B.Y. (2010) An Extension of the Promethee II Method Based on Generalized Fuzzy Numbers. Expert Systems with Applications, 37, 5314-5319. http://dx.doi.org/10.1016/j.eswa.2010.01.004
Pareto, V. (1886) Cours D’économie Politique. Lousanne Rouge, Lousanne.
Coelho, C.A.C. (2002) Evolutionary Multi-Objective Optimization: Critical Review. In: Sarker, R., Mohammadian, M. and Yao, X., Eds., Evolutionary Optimization, Kluwer Academic Publishers, Boston, 117-146.
Ehrgott, M. (2005) Multicriteria Optimization. Springer-Verlag, Berlin.
Ekel, P.Ya. and Galperin, E.A. (2003) Box-Triangular Multiobjective Linear Programs for Resource Allocation with Application to Load Management and Energy Market Problems. Mathematical and Computer Modelling, 37, 1-17. http://dx.doi.org/10.1016/S0895-7177(03)80001-8
Bellman, R.E. and Zadeh, L.A. (1970) Decision-Making in a Fuzzy Environment. Management Science, 17, 141-164. http://dx.doi.org/10.1287/mnsc.17.4.B141
Ekel, P.Ya., Martini, J.S.C. and Palhares, R.M. (2008) Multicriteria Analysis in Decision Making Under Information Uncertainty. Applied Mathematics and Computation, 200, 501-516. http://dx.doi.org/10.1016/j.amc.2007.11.024
Pereira Jr., J.G., Ekel, P.Ya., Palhares, R.M. and Parreiras, R.O. (2015) On Multicriteria Decision Making under Conditions of Uncertainty. Information Sciences, 234, 44-59. http://dx.doi.org/10.1016/j.ins.2015.06.013
Araujo, W.J., Ekel, P.Ya., Filho, R.P.F., Kokshenev, I.V. and Schuffner, H.S. (2011) Monocriteria and Multicriteria Based Placement of Reactive Power Sources in Distribution Systems. International Journal of Applied Mathematics and Informatics, 5, 240-248.