Benchmarking of Problems and Solvers: a Game-Theoretic Approach

• Autorzy: Gogodze Joseph

Identyfikatory

DOI

10.2478/fcds-2019-0008

• Języki publikacji: EN

Abstrakty

EN

In this note, we propose a game-theoretic approach for benchmarking computational problems and their solvers. The approach takes an assessment matrix as a payoff matrix for some zero-sum matrix game in which the first player chooses a problem and the second player chooses a solver. The solution in mixed strategies of this game is used to construct a notionally objective ranking of the problems and solvers under consideration. The proposed approach is illustrated in terms of an example to demonstrate its viability and its suitability for applications.

Słowa kluczowe

EN

benchmarking; software; solvers; problems; testing; multi objective decisionmaking problem

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2019
• Tom: Vol. 44, No. 2
• Strony: 137--150
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Gogodze Joseph

• Institute of Control System, TECHINFORMI, Georgian Technical University, 77 Kostava str., 0175 Tbilisi, Georgia

Bibliografia

• [1] Auger A., Hansen N., Performance evaluation of an advanced local search evolutionary algorithm, in: Proceedings of the IEEE Congress on Evolutionary Computation, 2, 2005, 1777-1784.
• [2] Benson H.Y., Shanno D.F., Vanderbei R.J., Interior-point methods for nonconvex nonlinear programming: Jamming and comparative numerical testing Operations Research and Financial Engineering, Princeton University ,Technical Report ORFE-00-02, 2000.
• [3] Billups S.C., Dirkse S.P., Ferris M.C., A comparison of algorithms for large-scale mixed complementarity problems, Comput. Optim. Appl., 7, 1997, 3–25.
• [4] Bondarenko A.S., Bortz D.M., More J.J., COPS: Large-scale nonlinearly constrained optimization problems, No. ANL/MCS-TM-237. Argonne National Lab., IL (US), 2000.
• [5] Bongartz I., Conn A.R., Gould N.I.M., Saunders M.A., Toint P.L., A numerical comparison between the LANCELOT and MINOS packages for large-scale numerical optimization Report 97/13, Namur University, 1997.
• [6] Brest J., Greiner S., Boskovic B., Mernik M., Zumer V., Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems IEEE transactions on evolutionary computation, 10, 6, 2006, 646-657.
• [7] Conn A.R., Gould N.I.M., Toint P.L, Numerical experiments with the LANCELOT package (Release A) for large-scale nonlinear optimization Math. Program. 73, 1996, 73–110.
• [8] Dolan E.D., Moré J.J., Benchmarking optimization software with performance profiles. Mathematical programming 91., 22002, pp. 201-213.
• [9] Ermoliev Y. M., Methods of solution of nonlinear extremal problems Cybernetics, 2, 4, 1966, 1-14.
• [10] Gogodze J., PageRank method for benchmarking computational Problems and their solvers International Journal of Computer Science Issues, 15, 3, 2018, 1-7.
• [11] Gogodze J., Using a Two-Person Zero-Sum Game to Solve a Decision-Making Problem Pure and Applied Mathematics Journal, 7, 2, 2018, 11-19.
• [12] Mallipeddi R., Suganthan P. N., Pan Q. K., Tasgetiren M. F., Differential evolution algorithm with ensemble of parameters and mutation strategies Applied Soft Computing, 11, 2, 2011, 1679-1696.
• [13] Mittelmann H., Benchmarking interior point LP/QP solvers Optim. Methods Softw. 12, 1999, 655–670.
• [14] Nash S.G., Nocedal J., A numerical study of the limited memory BFGS method and the truncated Newton method for large scale optimization SIAM J. Optim., 1, 1991, 358–372.
• [15] Qin A. K., Huang V. L., Suganthan P. N., Differential evolution algorithm with strategy adaptation for global numerical optimization IEEE transactions on Evolutionary Computation, 13, 2, 2009, 398-417.
• [16] Sala R., Baldanzini N., Pierini M., SQG-Differential Evolution for difficult optimization problems under a tight function evaluation budget in: International Workshop on Machine Learning Optimization and Big Data Springer Cham, 2017, 322-336.
• [17] Storn R., Price K., Differential Evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces Technical Report TR-95-012 Berkeley: ICSI, 1995.
• [18] Storn R., Price K., Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces J. of global optimization, 11, 4, 1997, 341-359.
• [19] Suganthan P.N., Hansen N., Liang J.J., Deb K., Chen Y.P., Auger A., Tiwari S., Problem definitions and evaluation criteria for the CEC 2005 special session on realparameter optimization KanGAL report, 2005005, 2005.
• [20] Vanderbei R.J., Shanno D.F., An interior-point algorithm for nonconvex nonlinear programming Comput. Optim. Appl., 13, 1999, 231–252.
• [21] Wang Y., Cai Z., Zhang Q., Differential evolution with composite trial vector generation strategies and control parameters IEEE Transactions on Evolutionary Computation, 151, 2011, 55-66.
• [22] Zeleny M., Multiple criteria decision making New York: McGraw-Hill, 1982.
• [23] Zhang J., Sanderson A. C., JADE: adaptive differential evolution with optional external archive IEEE Transactions on evolutionary computation, 135, 2009, 945-958.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).