Department of Mathematics

Indian Institute of Science

Bangalore 560 012

 

SEMINAR

 

Speaker

:

Prof Benjamin Burton
Affiliation : The University of Queensland, Australia

Subject Area

:

Mathematics

 

Venue

:

Department of Mathematics, Lecture Hall I

 

Time

:

03.00 p.m.

 

Date  

:

September 02, 2016 (Friday)

Title

:

"Multiobjective optimisation and tropical geometry"
Abstract

:

Multiobjective optimisation involves optimising several quantities, such as time and money, simultaneously. The result is a polyhedral frontier of "best possible" solutions, which cannot improve one quantity without a trade-off against another. For linear programming, this frontier can be generated using Benson's outer approximation algorithm, which uses a sequence of scalarisations (single-objective optimisations), combined with classical algorithms from polytope theory. If we generalise to integer programming, then things become significantly more complex. The main problem is the loss of convexity - the frontier of best possible solutions no longer has a polyhedral description. In this talk we show how to overcome this problem using tropical geometry, which replaces plus and times with the operations max and plus. The optimal frontier can then be described in terms of tropical polyhedra, and can be generated using an analogous algorithm that combines integer scalarisations with tropical polyhedral algorithms. As a corollary, we obtain a new upper bound on the number of scalarisations required to find all optimal solutions. This is joint work with Michael Joswig.