Willkommen an der Technischen Hochschule Nürnberg
Technische Hochschule Nürnberg Georg Simon Ohm

A Simple and Efficient Dichotomic Search Algorithm for Multi-Objective (Mixed-)Integer Linear Programmes

Datum:

Dienstag, 21. März 2017, 17.30-18.30 Uhr

Beschreibung:In this talk, we present a new algorithm to determine all nondominated extreme points in the outcome set of a Multi-Objective (Mixed-) Integer Linear Problem. More precisely, the goal is to find one feasible solution for each extremal supported nondominated point. This is easily achievable in the bi-objective case, because the natural order of nondominated points in this context allows to deduce a weight from two supported points to seek for other supported points with a procedure based on a dichotomic scheme.

However, this problem has long remained unsolved with p objectives, where p is greater than or equal to three. Indeed, the weight defined using p supported points in objective space does not necessarily have only positive components. Consequently, a direct extension of the classical dichotomic scheme is not possible.

After reviewing the main concepts introduced in the exact methods by Przybylski et al. (2010) and Özpeynirci and Köksalan (2010), and in the approximation method by Schandl et al. (2002), we give new insights about the main difficulties in the extension of the dichotomic scheme to the multi-objective case. Next, we propose a new exact method for which only weights with strictly positive components are considered. In contrast to the preceding propositions in the literature, this new method is at the same time, easy to understand, easy to implement, and computationally efficient. Experimental results on instances of the multi-objective assignment problem and of the multi-objective knapsack problem show the practical efficiency of the method.
Referent/in:Prof. Anthony Przybylski, Département informatique, Université de Nantes, Frankreich
Art:
Kolloquium
Raum:
KA.215
Ort:
K: STANDORT KESSLERPLATZ, Keßlerplatz 12
Veranstalter:
Fakultät AMP
Leitung:
Prof. Dr. Tim Kröger
Information:
http://www.th-nuernberg.de/institutionen/fakultaeten/angewandte-mathematik-physik-und-allgemeinwissenschaften/news-aktuelle-termine-veranstaltungen/kolloquium/page.html

Erstellt von AMP/KOM

Zurück
 
Vorschau Lageplan

So finden Sie den Weg an die TH Nürnberg.