Tuğba SARAÇ, Büşra TUTUMLU, Emine AKYOL ÖZER

A HYBRID MODIFIED SUBGRADIENT ALGORITHM THAT SELF-DETERMINES THE PROPER PARAMETER VALUES

A successful solution algorithm for non-convex optimization problems is the Modified Subgradient Algorithm (MSGA), which solves dual problems based on the sharp augmented lagrangian function. However, its performance highly depends on its parameter values, and determining the appropriate parameter values is difficult as they can be completely different for each problem. In this study, a new hybrid solution approach that a tabu search algorithm to find the appropriate MSGA parameter values and the MSGA algorithm run together is proposed. Although it seems like a contradiction to use an algorithm that also has its parameters to determine the most appropriate parameter values of an algorithm, this contradiction is eliminated by fixing the parameter values of the tabu search algorithm. The proposed algorithm does not need appropriate values of any algorithm parameter. It can find appropriate parameter values for each problem itself starting with the same fixed initial values. To show the success of the developed algorithm, especially on 0-1 quadratic problems, it is compared with the classical MSGA algorithm by using the quadratic knapsack test instances taken in the literature. According to the obtained solutions, the superiority of the hybrid algorithm has been demonstrated.

Keywords:

Modified Subgradient Algorithm (MSGA), Tabu Search Algorithm, Quadratic Knapsack Problem,

PDF

___

[1] Li, D., (1999), Zero duality gap in integer programming: p-norm surrogate constraint method, Operations Research Letters, 25, 89–96.
[2] Gasimov, R., (2002), Augmented lagrangean duality and nondifferantiable optimization methods in non-convex programming, Journal of Global Optimization, 24, 187-203.
[3] Gasimov, R.N. and Rubinov, A.M., (2004), On augmented lagrangeans for optimization problems with a single constraint, Journal of Global Optimization, 28, 153-173.
[4] Gasimov, R.N. and Ustun, O., (2005), Solving the quadratic assignment problems using modified subgradient algorithm, Proceedings of 35th International Conference on Computers & Industrial Engineering, Istanbul, Turkey, 19-22 June 2012.
[5] Gasimov, R.N. and Ustun, O., (2007), Solving the quadratic assignment problem using F-MSG algorithm, Journal of Industrial and Management Optimization, 3, 173-191.
[6] Burachik, R.S., Kaya, C.Y. and Mammadov, M., (2010), An inexact modified subgradient algorithm for non-convex optimization, Computational Optimization and Applications, 45, 1-24.
[7] Sipahioglu, A. and Saraç, T., (2009), The performance of the modified subgradient algorithm on solving the 0-1 quadratic knapsack problem, INFORMATICA, 20, 1-12.
[8] Ustun, O. and Kasimbeyli, R., (2012), Combined forecasts in portfolio optimization: a generalized approach, Computers & Operations Research, 39, 805–819.
[9] Ulutas, B. and Saraç, T., (2012), Determining the parameters of MSG algorithm for multi period layout problem, Journal of Manufacturing Technology Management, 7, 922–936.
[10] Ozcelik, F. and Sarac, T., (2012), A genetic algorithm extended modified sub-gradient algorithm for cell formation problem with alternative routings, International Journal of Production Research, 15, 4025–4037.
[11] Takan, M.A. and Kasımbeyli, R., (2020), A hybrid subgradient method for solving the capacitated vehicle routing problem, Journal of Nonlinear and Convex Analysis, 21, 413-423.
[12] Bulbul, K.G. and Kasimbeyli, R., (2021), Augmented lagrangian based hybrid subgradient method for solving aircraft maintenance routing problem, Computers & Operations Research, 132.
[13] Chelouah, R. and Siarry, P, (2000), Tabu search applied to global optimization, European Journal of Operational Research, 123, 256-270.
[14] Li, H.L., (1992), An approximate method for local optima for nonlinear mixed integer programming problems, Computers and Operations Research, 19, 435-444.
[15] Billionnet, A. and Soutif, E., (2004), An exact method based on lagrangean decomposition for the 0-1 quadratic knapsack problem, European Journal of operational research, 157, 565-575.