QA227 : Approximation algorithms for multicriteria optimization problems and their application
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2014
Authors:
Zohreh Azizi [Author], Jafar Fathali[Supervisor], Mehrdad Ghaznavi[Supervisor], Maryam Ghorani[Advisor]
Abstarct: In this thesis, we first explain Benson’s original algorithm for solving multi-objective linear programming problems in objective space. With some small changes to its procedures, we improve the computational speed. Then, applying changes on Benson’s algorithm, we obtain approximation version of the algorithm for multiobjective linear problems. This algorithm by creating inner and outer approximations of the nondominated set, provides a set of ε-nondominated points. Later, multiobjective convex optimization are discussed. In these problems, it is required to compute an infinite set of nondominated points. Using the Benson’s algorithm for MOLP, a method for approximating the nondominated set of convex multiobjective nonlinear programming problems is proposed . We prove that the inner approximation provides a set of weakly ε-nondominated points. In the case, the objectives and constraints are differentiable, is presented an efficient way to carry out the main step of the algorithm, i.e. the construction of a hyperplane separating an exterior point from the feasible set in objective space. Finally, the importance of approximation algorithms subject, will be identified with state application in the beam intensity optimization problems of radiotherapy planning, that can be formulated as a multiobjective linear programme with three objectives.
Keywords:
#Multiobjective optimization #Approximation algorithm #Convex optimization #Benson’s algorithm #ε-nondominated point #ε-efficient solution #Radiotherapy Link
Keeping place: Central Library of Shahrood University
Visitor: