Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi

Year 2012, Volume: 25 Issue: 1, 57 - 74, 30.06.2012

Tuğba Saraç

Abstract

Uygun Çözüm Temelli Genişletilmiş
Subgadient Algoritması (UÇT-GSA) doğrusal olmayan matematiksel modeller için,
2004 yılında Gasimov ve diğerleri tarafından önerilmiştir. Sivri, genişletilmiş
Lagrange fonksiyonu ile kurulmuş ikil problemin çözümüne yönelik bir
yaklaşımdır. Bu yöntemin önemli üstünlükleri, çözüm sürecinin yakınsak olması,
sıfır ikil aralığın elde edilebilmesi ve sürekli problem üzerine herhangi bir
dışbükeylik veya türevlenebilirlik şartı olmaması olarak sayılabilir. Bu
çalışmada 01 tamsayılı doğrusal olmayan matematiksel modellerin UÇT-GSA ile
çözülebilmeleri için bir GAMS kodu geliştirilmiştir ve algoritmanın 0-1
tamsayılı doğrusal olmayan problemlerin çözümündeki başarısı karesel sırt
çantası, hücre oluşturma  ve dinamik
yerleşim problemleri kullanılarak araştırılmıştır.

Keywords

doğrusal olmayan progamlama, karasel sırt çantası problemi, hücre oluşturma problemi, dinamik yerleşim problemi

Solvıng The 0-1 Nonlınear Programmıng Models By Usıng The Modıfıed Subgradıent Algorıthm Based On Feasıble Values

Abstract

A modified subgradient algorithm
based on feasible values (F-MSG) has been proposed for solving nonlinear
mathematical models in 2004 by Gasimov et.al. 
It is an approach to solve dual problems constructed by sharp augmented
Lagrangian function. It has some remarkable features. For example, it is
convergent, and it guarantees zero duality gap for the problems such that its
objective and constraint functions are all Lipschtz. In this study, a GAMS
program has been developed for solving the nonlinear models by using FMSG.
Success of the algorithm on solving the 0-1 nonlinear programming problems has
been examined by using the quadratic knapsack, cell formation and dynamic
layout problems.   

Keywords

0-1 nonlinear programiming., modified sub-gradient algorithm based on feasible values (f-msg), Quadratic knapsack problem, cell formation problem, dynamic layout problem

References

• [1] R.T. Rockafellar, R.J.-B Wets, “Variational Analysis”, Springer, Berlin, 1998.
• [2] R.N. Gasimov, “Augmented Lagrangian duality and nondifferantiable optimization methods in nonconvex programming”, Journal of Global Optimization, Vol.24, pp.187-203, 2002.
• [3] R.N. Gasimov, A.M. Rubinov, O. Ustun, “The Modified Subgradient Algorithm Based on Feasible Dual Values and Solving the Quadratic Assignment Problems”, International Conference on Continuous Optimization (ICCOPT-I) August 2-4, Rensselaer Polytechnic Institute, Troy, New York, pp.31-32, 2004.
• [4] M.S. Bazaraa, H.D. Sherali, C.M. Shetty, “Nonlinear Programming. Theory and Algorithms”, John Wiley & Sons, Inc., New Jersey, 2006.
• [5] D.P. Bertsekas, “Nonlinear Programming”, Athena Scientific, Belmont, MA, 1995.
• [6] T. Saraç, A. Sipahioğlu, “Karesel sırt çantası problemi için subgradient temelli bir çözüm yaklaşımı”, Yöneylem Araştırması ve Endüstri Mühendisliği 26. Ulusal Kongresi, 3-5 Temmuz, İzmit-Kocaeli, pp.202-205, 2006.
• [7] R.N. Gasimov, O. Ustun, “Solving the quadratic assignment problem using F-MSG algorithm”, Journal of Industrial and Management Optimization, Vol.3, No.2, pp.173-191, 2007.
• [8] H.L. Li, “An approximate method for local optima for nonlinear mixed integer programming problems”, Computers and Operations Research, Vol.19, No.5, pp.435-444, 1992.
• [9] http://cedric.cnam.fr/~soutif/QKP/
• [10] A. Billionnet, E. Soutif, “An exact method based on Lagrangean decomposition for the 0-1 quadratic knapsack problem”, European Journal of Operational Research, Vol.157, No.3, pp.565575, 2003.
• [11] A. Kusiak, “The generalized group technology concept”, International Journal of Production Research, Vol.25, pp.561-569, 1987.
• [12] G.K. Adil, D. Rajamani, D. Strong, “Cell formation considering alternate routings”. International Journal of Production Research, Vol.34, pp.1361–1380, 1996.
• [13] Y.B. Moon, S.C. Chi, “Generalized part-family formation using neural network techniques”, Journal of Manufacturing Systems, Vol.11, pp.149-160, 1992.
• [14] Y.K. Won, S.H. Kim, “Multiple criteria clustering algorithm for solving the group technology problem with multiple process routings”. Computers and Industrial Engineering, Vol.32, pp.207– 220, 1997.
• [15] M.J. Rosenblatt, “The Dynamics of Plant Layout”, Management Science, Vol.3, pp.76-86, 1986.
• [16] D.G. Conway, M.A. Ventakaraman, “Genetic search and the dynamic facility layout problem”, Computers and Operations Research, Vol.21, No.8, pp.955-960, 1994.