AASCIT - Journal - All Issues

ISSN: 2375-3927

International Journal of Mathematical Analysis and Applications

The Journal

Manuscript Information

KKT Conditions and Branch and Bound Methods on Pure Integer Nonlinear Programming

International Journal of Mathematical Analysis and Applications
Vol.2 , No. 4, Publication Date: Oct. 17, 2015, Page: 62-67

1595 Views Since October 17, 2015, 2290 Downloads Since Oct. 17, 2015

Paper in PDF (592K)

Follow on

Authors

[1]	Amalia Umami, Department of Mathematics, University of Sumatera Utara, Medan, Indonesia.
[2]	Esther Nababan, Department of Mathematics, University of Sumatera Utara, Medan, Indonesia.
[3]	Sawaluddin , Department of Mathematics, University of Sumatera Utara, Medan, Indonesia.

Abstract

Optimization problems are not only formed into a linear programming but also nonlinear programming. In real life, often decision variables restricted on integer. Hence, came the nonlinear programming. One particular form of nonlinear programming is a convex quadratic programming which form the objective function is quadratic and convex and linear constraint functions. In this research designed a completion of a convex quadratic integer programming with Karush Kuhn Tucker conditions which then reduces the integer convex quadratic programming into a linear complementary problem. Then used a modified simplex method and Branch and Bound method to obtain the optimal and integer solution and fulfill all the constraints. The obtained solution by using KKT conditions is a global optimum solution due to the problem studied is convex. This method is effective in finding integer solution with result that is not too far from the initial solution to the problem which is quite simple.

Keywords

Nonlinear Programming, Convex Quadratic Programming, Integer Programming, KKT Condition, Branch and Bound

Reference

[01]	Amalia. 2009. Peranan Persyaratan Karush-Kuhn-Tucker dalam Menyelesaikan Pemrograman kuadratis. [Skripsi]. Medan: Universitas Sumatera Utara.
[02]	Asih, M. N. 2012. Aplikasi metode Kuhn Tucker dalam Penjualan Oli Mobil. Jurnal Matematika. Vol.2 No.1. ISBN: 1693-1394.
[03]	Buchheim, C., Caprara, A. and Lodi, A. 2010. An Effective Branch-and-Bround Algorithm for Convex Quadratic Integer Programming. IPCO. University of Bologna.
[04]	Ferreira, M. A. M., Andrade, M., Matos, M. C. P., Filipe, J. A. and Voelho, M. P. 2010. Kuhn Tucker’s Theorem – The Fundamental Result in Convex Programming Applied to Finance and Economic Sciences. International Journal of Latest Trends in Finance & Economic Sciences. 2: 111 – 116.
[05]	Friedman, J. 1998. Linear Complementarity and Mathematical (Nonlinear) Programming. UBC.
[06]	Gupta, P. K and D. S. Hira. 2007. Operations Research. Ramnagar – New Delhi: Rajendra Ravindra.
[07]	Hemmeke, R, Köppe, M., Lee, J and Weismatel, R. 2009. Nonlinear Integer Programming. Magdeburg. Germany.
[08]	Hillier, F. S. 1994. Pengantar Riset Operasi. Jilid 1. Ed ke – 5. Wahyarasmana, D. Erlangga. Jakarta.
[09]	Lukananto, J. 2000. Pengantar Optimasi Non Linier. http://luk.staff.ugm.ac.id/optimasi/pdf/ nonlinier2003. [10 Maret 2014].
[10]	Rao, S. S. 1985. Optimization Theory and Aplications. Wiley Eastern Limited. New Delhi.
[11]	Siagian, P. 2006. Penelitian Operasional: Teori dan Praktek. Jakarta: Universitas Indonesia (UI-Press).
[12]	Sidabutar, J. 2008. Pengembangan Algoritma Pencarian Untuk Menyelesaikan Problema Program Tak Linier Integer Campuran. [Tesis]. Medan: Universitas Sumatera Utara. Program Pascasarjana.
[13]	Sinaga, M. S. 2008. Pengembangan Metode Pendekatan Pencarian Layak Untuk Menyelesaikan Problema Program Integer Tak Linier. [Tesis]. Medan: Universitas Sumatera Utara. Program Pascasarjana.
[14]	Sinurat, R. R. 2008. Studi Penyelesaian Problema Mixed Integer Programming dengan Menggunakan Metode Branch and Cut. [Skripsi]. Medan: Universitas Sumatera Utara.
[15]	Stewart, J. 1999. Kalkulus. Jilid 1. Ed ke- 4. Mahanani, N. Erlangga. Jakarta.
[16]	Taha, H. A. 2007. Operation Research an Introduction. Ed ke – 8. Fayetteville: University of Arkansas.
[17]	Williams, H. P. 2007. A Method for Finding All Solutions of a Linear Complementarity Problem. The London School of Economics and Political Science. Great Britain.
[18]	Yoon Ann, E. M. 2006. Branch and Bound Algorithm for Binary Quadratic Programming with Aplication In Wireless Network Communications. Iowa State University.