Finding the non-dominated set of the bi-objective quadratic knapsack problem

Abstract

Çok amaçlı optimizasyon gerçek hayat problemlerini modellemeyi ve çözmeyi amaçlar. İki amaç fonksiyonlu problemlerde de çok amaçlı optimizasyonda olduğu gibi etkin çözümler bulunmaya çalışılır. İki amaç fonksiyonlu doğrusal sırt çantası problemi çok sayıda etkin çözümü bulunan zor kabul edilen bir problemdir. Bu problemin karesel versiyonu olan iki amaç fonksiyonlu karesel sırt çantası problemini (İKSP) çalıştık. Literatürdeki uygulamalar yetersiz olduğundan etkin çözüm kümesinin yapısının araştırılmasını hedefledik. Etkin çözümler kümesini bulmak için epsilon kısıt yöntemini, destekli etkin çözümleri bulmak için ise bir doğrusal skalarizasyon yöntemi kullandık. Farklı doluluk değerleri ile rassal yaratılan İKSP'leri CPLEX ile çözüp sonuçları illüstrasyonlar ve kapsama hataları ile raporladık. Doluluk değerleri düşükken doğrusal versiyona yaklaşan İKSP'ler daha çok sayıda etkin çözüme sahiptir. Çözdüğümüz problemler için etkin çözüm sayılarının çok fazla olmadığını gene de yüksek cpu zamanları gerektirdikleri için zor problemler olduklarını belirledik. Destekli etkin çözümlerin ağırlıklı doğrusal skalarizasyon ile bulunmasının daha kolay olduğunu söyleyebiliriz. Bu çözümler tüm çözüm kümesinin bir temsili olarak alındığında ortalama kapsama hatalarının kabul edilebilir seviyede olduğu görülebilir. Bunların yanında, üç köşegenli matrislerle oluşturulmuş İKSP'leri de çözüp raporladık. Bu problemlerin çözümü ise daha kolaydı ve daha az çözüm zamanı gerektirdi.

Multi-objective optimization aims to model and solve real life problems. In bi-objective problems, as in the case of multi-objective problems, non-dominated solutions are of interest. The bi-objective linear knapsack problem is well-studied and is known to be a difficult problem with a lot of non-dominated solutions. We have studied the quadratic version of this problem, the bi-objective quadratic knapsack problem (BQKP). Our goal is to investigate the structure of the non-dominated set in BQKP since reports on implementations in the literature are inadequate so far. We use the epsilon constraint method to find non-dominated solutions and use a linear scalarization to obtain supported non-dominated solutions.Randomly generated BQKP's with different percentage of fullness values are solved on the commercial solver CPLEX and results of these problems are reported with illustrations and coverage errors. BQKP's with small percentage of fullness levels resembles more to the linear version of the problem with higher number of non-dominated solutions. We observe that the number of non-dominated solutions is not many for the size of BQKP's we had solved yet the problem is still hard to solve since some of the test problems required long cpu times. Supported non-dominated solutions are relatively easier to obtain by using a weighted sum scalarization. When supported non-dominated solutions are regarded as a representation of the entire non-dominated set, averages coverage errors are at acceptable levels for all problem types studied in this work. BQKP's with tri-diagonal quadratic matrices are also solved and reported. Tri-diagonally structured problems are easier to solve and require less computation time.