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.