Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal

Renaud Lacour

in Economics Thesis from University Paris Dauphine from Paris Dauphine University

Abstract: This thesis deals with several aspects related to solving multi-objective problems, without restriction to the bi-objective case. We consider exact solving, which generates the nondominated set, and approximate solving, which computes an approximation of the nondominated set with a priori guarantee on the quality.We first consider the determination of an explicit representation of the search region. The search region, defined with respect to a set of known feasible points, excludes from the objective space the part which is dominated by these points. Future efforts to find all nondominated points should therefore be concentrated on the search region.Then we review branch and bound and ranking algorithms and we propose a new hybrid approach for the determination of the nondominated set. We show how the proposed method can be adapted to generate an approximation of the nondominated set. This approach is instantiated on the minimum spanning tree problem. We review several properties of this problem which enable us to specialize some procedures of the proposed approach and integrate specific preprocessing rules. This approach is finally supported through experimental results.

Keywords: Optimisation multi-objectifs; Représentation de la région de recherche; Algorithmes de séparation et évaluation; Algorithmes de ranking; Problème de l'arbre couvrant de poids minimal; Multi-objective optimization; Representation of the search region; Branch and bound algorithms; Ranking algorithms; Minimum spanning tree problem (search for similar items in EconPapers)
JEL-codes: C6 (search for similar items in EconPapers)
Date: 2014 Written 2014
Note: dissertation
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://basepub.dauphine.fr/xmlui/bitstream/123456789/14806/2/2014PA090067.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to basepub.dauphine.psl.eu:443 (Bad file descriptor) (http://basepub.dauphine.fr/xmlui/bitstream/123456789/14806/2/2014PA090067.pdf [301 Moved Permanently]--> https://basepub.dauphine.psl.eu/xmlui/bitstream/123456789/14806/2/2014PA090067.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:dau:thesis:123456789/14806

Ordering information: This item can be ordered from
http://basepub.dauph ... ndle/123456789/14806

Access Statistics for this book

More books in Economics Thesis from University Paris Dauphine from Paris Dauphine University Contact information at EDIRC.
Bibliographic data for series maintained by Alexandre Faure ( this e-mail address is bad, please contact ).