An exact algorithm for biobjective integer programming problems

Birçok yöneylem araştırması uygulamasında ortaya çıkan iki amaçlı tamsayılı programlama problemlerinin tüm baskın noktalarını bulabilmek için amaç fonksiyonu uzayında arama yapan kesin bir algoritma önerildi. Bu algoritma, arama uzayının kutulara bölünmesi ve yön vektörü sabitlenmiş bir Pascoletti-Serafini skalarizasyon modeli çözülerek kutuların aranmasına dayanmaktadır. Algoritmanın skalarizasyon probleminde kullanılan parametre seçimlerinde değişiklik yapılarak varyantları geliştirildi. Bu varyantların hem kesin birer algoritma olarak hem de zaman kısıtlaması altındaki çözüm yaklaşımları olarak performansları bilgisayımsal deneyler yapılarak ortaya konuldu. Deney sonuçları algoritmanın özellikle çözülen tamsayılı programlama problemleri bakımından mevcut yaklaşımlara göre daha iyi olduğunu göstermektedir. Deneyler ayrıca farklı varyantların farklı açılardan avantajlarını ortaya koymaktadır: bazı varyantlar tüm baskın çözüm kümesini daha kısa sürede bulurken, diğerleri zaman kısıtlaması altında temsil bakımından daha iyi kalitede çözümler döndürmektedir.