Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée

Lyes Belhoul

in Economics Thesis from University Paris Dauphine from Paris Dauphine University

Abstract: Our aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem.

Keywords: Énumération ordonnée; Branch and Bound; Problèmes d’optimisation combinatoire mono et multi-Objectifs; Problème d’affectation; Problème du voyageur de commerce asymétrique; Ordered Enumeration; Mono and Multi-Objective Combinatorial Optimization Problems; Assignment Problem; Asymmetric Travelling Salesman Problem (search for similar items in EconPapers)
JEL-codes: C61 (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/14672/2/2014PA090060.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/14672/2/2014PA090060.pdf [301 Moved Permanently]--> https://basepub.dauphine.psl.eu/xmlui/bitstream/123456789/14672/2/2014PA090060.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/14672

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

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 ).