Research Article
BibTex RIS Cite

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

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.

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.

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

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

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.   

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.
There are 16 citations in total.

Details

Subjects Industrial Engineering
Journal Section Research Articles
Authors

Tuğba Saraç

Publication Date June 30, 2012
Published in Issue Year 2012 Volume: 25 Issue: 1

Cite

APA Saraç, T. (2012). Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi. Eskişehir Osmangazi Üniversitesi Mühendislik Ve Mimarlık Fakültesi Dergisi, 25(1), 57-74.
AMA Saraç T. Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi. ESOGÜ Müh Mim Fak Derg. June 2012;25(1):57-74.
Chicago Saraç, Tuğba. “Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi”. Eskişehir Osmangazi Üniversitesi Mühendislik Ve Mimarlık Fakültesi Dergisi 25, no. 1 (June 2012): 57-74.
EndNote Saraç T (June 1, 2012) Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi 25 1 57–74.
IEEE T. Saraç, “Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi”, ESOGÜ Müh Mim Fak Derg, vol. 25, no. 1, pp. 57–74, 2012.
ISNAD Saraç, Tuğba. “Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi”. Eskişehir Osmangazi Üniversitesi Mühendislik ve Mimarlık Fakültesi Dergisi 25/1 (June 2012), 57-74.
JAMA Saraç T. Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi. ESOGÜ Müh Mim Fak Derg. 2012;25:57–74.
MLA Saraç, Tuğba. “Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi”. Eskişehir Osmangazi Üniversitesi Mühendislik Ve Mimarlık Fakültesi Dergisi, vol. 25, no. 1, 2012, pp. 57-74.
Vancouver Saraç T. Tam Sayılı Doğrusal Olmayan Matematiksel Modellerin Uygun Çözüm Temelli Genişletilmiş Subgradient Algoritması İle Çözülmesi. ESOGÜ Müh Mim Fak Derg. 2012;25(1):57-74.

20873  13565  13566 15461  13568    14913