Exact and representation methods for multiobjective optimization problems

Abstract

Birçok gerçek hayat karar verme problemi birbiriyle çelişen birden fazla amacın dikkate alınmasını gerektirir. Karar verme sürecinde matematiksel programlama kullanıldığında, bu problem çok amaçlı eniyileme problemine dönüşür. Çok amaçlı eniyileme probleminde birden fazla amaç fonksiyonu dikkate alındığından eniyi çözüm yerine etkin çözüm kullanılmaktadır. Bir etkin çözümün bir amaç fonksiyonunun iyileştirilebilmesi için diğer amaç fonksiyonlarından birinin kötüleştirilmesi gerekmektedir. Çok amaçlı eniyileme problemine ait bütün etkin çözümler etkin çözüm kümesi olarak tanımlanır ve karar vericiye bütün uygun ödünleşme bilgisini sunar. Çok amaçlı eniyileme teorisine yapılan katkılar 1970'lere kadar uzanmaktadır. Diğer taraftan son 20 yılda ise farklı tipteki çok amaçlı eniyileme problemleri için pratik olarak uygulanabilir algoritmalar geliştirilmiştir. Bu çalışmalarda iki amaç fonksiyonlu problemler ve iki veya üç amaç fonskiyonuna sahip olan kesikli eniyileme problemleri dikkate alınmıştır. Bu tezde ikiden fazla amaç fonksiyonlu problemleri çözebilmek için gerekli olan teorik altyapı oluşturulmuştur. Daha sonrasında bu sonuçlar kullanılarak etkin çözüm kümesini türeten yeni bir yöntem önerilmiştir. Fakat etkin çözüm kümesi genellikle büyük bir kümedir ve bütün olarak değerlendirilmesi zordur. Bu nedenle etkin çözüm kümesi yerine bu kümenin bir alt kümesinin türetilmesi tercih edilebilmektedir. Bu özelliğe sahip olan kümelere temsili etkin çözüm kümesi denilmektedir. Temsili etkin çözüm kümesi birçok farklı yöntemle bulunabilir. Fakat bu kümenin belirlenen bir kalite garantisini sağlaması ile tanımlanan problem oldukça zordur. Bu kapsamda iki-seviyeli eniyileme problemleri kullanılmıştır. Bu tezde iki-seviyeli eniyileme prob- leminden faydalanılarak çok amaçlı eniyileme problemleri için temsili etkin çözüm kümesini belirli bir kalite garantisi ile türetebilecek bir algoritma önerilmiştir. Bu algoritma çok amaçlı doğrusal programlama problemleri üzerinde test edilmiştir.

Many real-world decision-making situations involve simultaneous consideration of conflicting objectives. When a mathematical programming framework is utilized to model such problems, the result is a multiobjective optimization problem, which no longer possesses a unique optimal objective function value. In multiobjective optimization, the set of efficient solutions is used instead of the optimal solution. An efficient solution has the property that no improvement on any objective is possible without sacrificing at least another objective. The solution to a multiobjective optimization problem consists of the efficient set which portrays all relevant trade-off information to a decision maker. Contributions to the theory of multiobjective optimization date back to the 1970s. During the last two decades there has been significant progress in terms of practically implementable algorithms to solve several versions of the multiple objective optimization problem. Among these is the bicriteria case that corresponds to optimization of two objective functions and a number of well-studied discrete optimization problems with two and sometimes three objectives. However, enumerating the efficient set and enabling the decision maker to find a most-preferred solution within the efficient set remains a challenge for the general case. In this work, we revisit the theory of multiple objective optimization with the goal of building algorithms that are capable of solving problems with more than two objectives. Our main concern is to develop methods that enumerate the efficient set for multiobjective optimization problems. We develop an algorithm that enumerates the entire set of solutions for multiple objective discrete optimization problems. However in general the efficient set is not easy to deal with, so it might be better to generate a fine subset of the efficient set. Such sets are called representations. We consider finding representations of the efficient set. Although representations of the efficient set can be found in many different ways, imposing quality guarantees has been a challenge. Our efforts in this direction lead to a bilevel programming-based subproblem. By using the bilevel formulation, we propose an algorithm to generate representations that satisfy the specified error factor. We test the algorithm on multiobjective linear programming problems.