Çarpımsal Ceza Modeli ile Tamsayılı Programlama

Abstract

Doğrusal olmayan optimizasyon problemlerinin çözüm yöntemlerinden birisi, kısıtların sağlanmama durumlarında amaç fonksiyonunu olumsuz yönde değiştirecek bir ceza uygulanmasıdır. Çarpımsal ceza modeli, son dönem çalışmalarında henüz yer almakla birlikte, literatürde farklı yaklaşımlara sahip ceza teknikleri de yer almaktadır. Tamsayılı programlama problemlerinin çözümünde kullanılan yöntemler arasında kesme düzlemi yaklaşımları, dal sınır yöntemleri ve evrimsel optimizasyon uygulamaları sayılabilir. Bu çalışma kapsamında ilk kez tamsayılı optimizasyon problemlerinin çözümünde çarpımsal ceza temelli kısıt sağlama yöntemi uygulanmıştır. Yöntem doğrusal olmayan ortak test problemlerinden Himmelblau üzerinde test edilmiş. Yöntemin, problemin kompleksliği ve büyüklüğü karşısındaki davranışı gözlemlenmiştir ve performansı da, diğer yaklaşımlarla karşılaştırmalı biçimde analiz edilmiştir. One of the solution methods for the nonlinear optimization problems is to apply penalty that changes the value of objective function as contrary to optimization direction. Multiplicative penalty method, has been already taken place in the recent studies whereas there can be found other approaches in the literature. Cutting plane approaches, branch and bound methods and evolutionary optimization applications can be regarded as essential solutions to integer programming problems. In scope of this study it is first time that the multiplicative penalty approach is used for integer programming as a new constraint handling method. The method is tested on the Himmelblau's problem which is one of the common test problems in the nonlinear optimization area. Method was also tested against complexity and size of the problem in terms of its performance as compared to existing methods' results.