Generalized Algorithms of Discrete Optimization and Their Power Engineering Applications

Roberto Berredo¹, Petr Ekel^1,2*, Helder Ferreira^2,3, Reinaldo Palhares⁴, Douglas Penaforte⁵

¹Advanced System Optimization Technologies—ASOTECH, Belo Horizonte, Brazil.
²Graduate Program in Electrical Engineering, Pontifical Catholic University of Minas Gerais, Belo Horizonte, Brazil.
³CEMIG Distribution, Belo Horizonte, Brazil.
⁴Graduate Program in Electrical Engineering, Federal University of Minas Gerais, Belo Horizonte, Brazil.
⁵CEMIG Generation and Transmission, Belo Horizonte, Brazil.

DOI: 10.4236/eng.2015.78049                

Abstract

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.

Keywords

Discrete Optimization, Method of Normalized Functions, Duplicate Algorithms, Fuzzy Coefficients, Interrelated Models, Multiobjective Decision Making

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Taha, H.A. (1982) Operations Research: An Introduction. 3rd Edition, Macmillan Publishing, New York.
[2]	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
[3]	Ekel, P.Ya. (1990) Models and Methods of Discrete Optimization of Power Supply Systems. KPI, Kiev. (In Russian)
[4]	Jeroslow, R.C. (1974) Trivial Integer Programs Unsolvable by Branch-and-Bound. Mathematical Programming, 6, 105-109. http://dx.doi.org/10.1007/BF01580225
[5]	Korbut, A.A. and Finkelshtein, Yu.Yu. (1984) Approximate Methods of Discrete Programming. Soviet Journal of Computer and System Sciences, 22, 155-167.
[6]	Garey, M.A. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP—Completeness. W.H. Freeman, New York.
[7]	Papadimitrou, C.H. and Steiglitz, K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs.
[8]	Berzin, E.A. (1974) Optimal Resource Allocation and Elements of System Synthesis. Russkoe Radio, Moscow. (In Russian)
[9]	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
[10]	Syslo, M., Deo, N., and Kowalik, J.S. (1983) Discrete Optimization Algorithms with Pascal Programs. Prentice-Hall, Englewood Cliffs.
[11]	Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009) Introduction to Algorithms. 3rd Edition, MIT Press, Cambridge, MA.
[12]	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
[13]	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
[14]	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
[15]	Pedrycz, W. and Gomide, F. (1998) An Introduction to Fuzzy Sets: Analysis and Design. MIT Press, Cambridge, MA.
[16]	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
[17]	Pedrycz, W., Ekel, P. and Parreiras, R. (2011) Fuzzy Multicriteria Decision-Making: Models, Methods, and Applications. John Wiley & Sons, Chichester.
[18]	Zorin, V.V. and Ekel, P.Ya. (1980) Discrete-Optimization Methods for Electrical Supply Systems. Power Engineering, 18, 19-30.
[19]	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
[20]	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
[21]	Hu, T.C. (1969) Integer Programming and Network Flows. Addison-Wesley, New York.
[22]	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
[23]	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
[24]	Orlovsky, S.A. (1981) Problems of Decision Making with Fuzzy Information. Nauka, Moscow. (in Russian)
[25]	Delgado, M. (1994) Fuzzy Optimization: Recent Advances. Physica-Verlag, Heidelberg.
[26]	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
[27]	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
[28]	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
[29]	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
[30]	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
[31]	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
[32]	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
[33]	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
[34]	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
[35]	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
[36]	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
[37]	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
[38]	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
[39]	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
[40]	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
[41]	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
[42]	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
[43]	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
[44]	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
[45]	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
[46]	Pareto, V. (1886) Cours D’économie Politique. Lousanne Rouge, Lousanne.
[47]	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.
[48]	Miettinen, K.M. (1999) Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston.
[49]	Ehrgott, M. (2005) Multicriteria Optimization. Springer-Verlag, Berlin.
[50]	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
[51]	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
[52]	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
[53]	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
[54]	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.