desdeo’s documentation¶

# IMPORTANT NOTICE This version of DESDEO is no longer supported. Information on the latest, and actively developed version of desdeo, can be found [here](https://desdeo.misitano.xyz/software).

# DESDEO README #

DESDEO is a free and open source Python-based framework for developing and experimenting with interactive multiobjective optimization.

[Documentation is available.](https://desdeo.readthedocs.io/en/latest/)

[Background and publications available on the University of Jyväskylä Research Group in Industrial Optimization web pages.](https://desdeo.it.jyu.fi)

## Try in your browser ##

You can try a guided example problem in your browser: [choose how to deal with river pollution using NIMBUS](https://mybinder.org/v2/gh/industrial-optimization-group/desdeo-vis/master?filepath=desdeo_notebooks%2Fnimbus-river-pollution.ipynb). You can also [browse the other examples](https://mybinder.org/v2/gh/industrial-optimization-group/desdeo-vis/master?filepath=desdeo_notebooks).

## What is interactive multiobjective optimization? ##

There exist many methods to solve [multiobjective optimization](https://en.wikipedia.org/wiki/Multi-objective_optimization) problems. Methods which introduce some preference information into the solution process are commonly known as multiple criteria decision making methods. When using so called [interactive methods](https://en.wikipedia.org/wiki/Multi-objective_optimization#Interactive_methods), the decision maker (DM) takes an active part in an iterative solution process by expressing preference information at several iterations. According to the given preferences, the solution process is updated at each iteration and one or several new solutions are generated. This iterative process continues until the DM is sufficiently satisfied with one of the solutions found.

Many interactive methods have been proposed and they differ from each other e.g. in the way preferences are expressed and how the preferences are utilized when new solutions. The aim of the DESDEO is to implement aspects common for different interactive methods, as well as provide framework for developing and implementing new methods.

## Installation ##

### From conda-forge using Conda ###

This is the recommended installation method, especially for those who are newer to Python. First download and install the [Anaconda Python distribution](https://www.anaconda.com/download/).

Next, run the following commands in a terminal:

conda config –add channels conda-forge conda install desdeo desdeo-vis

Note: if you prefer not to install the full Anaconda distribution, you can install [miniconda](https://conda.io/miniconda.html) instead.

### From PyPI using pip ###

Assuming you have Pip and Python 3 installed, you can [install desdeo from PyPI](https://pypi.org/project/desdeo/) by running the following command in a terminal:

pip install desdeo[vis]

This installs desdeo and [desdeo-vis](https://github.com/industrial-optimization-group/desdeo-vis), which you will also want in most cases.

## Getting started with example problems ##

To proceed with this section, you must [first install Jupyter notebook](http://jupyter.org/install). If you’re using Anaconda, you already have it!

You can copy the example notebooks to the current directory by running:

python -m desdeo_notebooks

You can then open them using Jupyter notebook by running:

jupyter notebook

After trying out the examples, the next step is to [read the full documentation.](https://desdeo.readthedocs.io/en/latest/)

## Development ##

### Set-up ###

You should install the git pre-commit hook so that code formatting is kept consistent automatically. This is configured using the pre-commit utility. See [the installation instructions](https://pre-commit.com/#install). In short, pre-commit hook can be installed as

pip install –upgrade pre-commit pre-commit install

If you are using pipenv for development, you can install desdeo and its dependencies after obtaining a git checkout like so:

pipenv install -e .[docs,dev,vis]

### Tests ###

Tests use pytest. After installing pytest you can run:

pytest tests

### Release process ###

Make a release commit in which the version is incremented in setup.py and an entry added to HISTORY.md
Make a git tag of this commit with git tag v$VERSION
Push – including the tags with git push –tags
Upload to PyPI with python setup.py sdist bdist_wheel and twine upload dist/*

Background¶

This section contains background and is meant to serve as a quick guide or reference to the key concepts and practical issues required to make use of the interactive multi-objective optimization techniques in DESDEO.

What is NIMBUS?¶

As its name suggests, NIMBUS (Nondifferentiable Interactive Multiobjective BUndle-based optimization System) is a multiobjective optimization system being able to handle even nondifferentiable functions. It will optimize (minimize or maximize) several functions at the same time, creating a group of different solutions. One cannot say which one of them is the best, because the system cannot know the criteria affecting the ‘goodness’ of the desired solution. The user is the one that makes the decision. Usually, an example is the best way to make things clear:

Mathematical approach¶

Mathematically, all the generated solutions are ‘equal’, so it is important that the user can influence the solution process. The user may want to choose which of the functions should be optimized most, what are the limits of the objectives, etc. In NIMBUS, this phase is called a ‘classification’. We will discuss this procedure later.

Searching for the desired solution means actually finding the best compromise between many separate goals. If we want to get lower values for one function, we must be ready to accept the growth of another function. This is due to the fact that the solutions produced by NIMBUS are Pareto optimal. This means that there is no possibility to achieve better solutions for some component of the problem without worsening some other component(s).

Classification in NIMBUS¶

The solution process with NIMBUS is iterative. Since there is usually not only one absolutely right solution, you are asked to ‘guide the solver to a desired direction’. The classification is a process in which the desires of the user are expressed. You can choose which of the function values should be decreased from the current level and which of the functions are less important (i.e. their values can be increased).

Classification background¶

In NIMBUS, preferences are expressed by choosing a class for each of the objective functions.

When considering minimization, the class alternatives are:

<

The value should be minimized.

<=

The value should be minimized until the specified limit is reached.

=

The current value is OK.

>=

Value can be increased. Value should be kept below the specified upper bound.

<>

Value can change freely.

For maximization, directional signs are inverted:

>

The value should be maximized.

>=

The value should be maximized until the specified limit is reached.

=

The current value is OK.

<=

Value can be decreased. Value should be kept above the specified lower bound.

<>

Value can change freely.

If the second or the fourth alternative is selected, you are asked to specify the limits: an aspiration level or an upper/lower bound respectively for the function values;.

Aspiration level defines a desired value for the objective function.
Upper/lower bound defines the limit value that the function should not exceed, if possible.

Since we are dealing with Pareto optimal solutions (compromises) we must be willing to give up something in order to improve some other objective. That is why the classification is feasible only if at least one objective function is in the first two classes and at least one objective function is in the last two classes.

In other words, you must determine at least one function whose value should be made better. However that can not be done if there are no functions whose value can be worsened.

Classification using the widget¶

You may find it useful to follow along with the cylinder notebook while reading this section.

The current solution is shown graphically as a parallel coordinate plot. The classification can be made by either clicking points on the axes, or by manually adjusting the classification selection boxes and limit fields.

By default, maximization and minimization are displayed in their original units. You may wish to reformulate the problem so everything is minimized. This means all maximized functions are negated. To enable this, click settings and then check Reformulate maximization as minimization. To change the default, add the following to the beginning of your notebooks:

from desdeo_vis.conf import conf
conf(max_as_min=True)

Let us assume that the function under classification should be minimized. When you click on the corresponding axis, the system considers the axis value at the point you clicked on as a new limit value and inserts the numerical data into the limit field automatically. Selecting the point below the current solution means that function should be minimized (<=) until that limit is reached. If the point is selected above the current solution, we allow the function value to increase (>=) to that limit. Clicking a point below the whole bar means that the function should be minimized as much as possible (<). Correspondingly, if the value is selected above the whole bar, the function value can change freely (<>). If the current value of some function is satisfactory (=), you can express it by clicking the numeric value beside the bar.

In the case of maximization, the logic above is reversed. For example, if you click a point above the current solution, it indicates that the function should be maximized as much as possible. The desired extreme point of each function is indicated by a small black triangle inside the top or the bottom of each bar.

You can refine the graphical classification by changing the class of each objective function using the selection box or adjusting the value in its limit field.

Classifying the cylinder problem¶

This section walks you through creating a classification with the widget for the cylinder notebook.

The first solution we get from NIMBUS is reasonable. However, we may decide at this point that we want to increase the cylinder’s volume as much as possible, while still keeping the surface area and height difference low.

To do this, we select ( <> ) from the volume dropdown, because we allow (for now) the volume to be varied freely. The next column describes the solution for the surface area function. We want to know how much the volume will be when the surface area is 1900, so we select ( >= ) from the dropdown and enter 1900 into the box. For height difference we select ( <= ).

Classification without the widget¶

It is also possible to make a classification without the widget. Possibly reasons you might do this are because you are constructing an artificial decision maker, you are making your own preference selection widget, or because you are unable to use Jupyter notebook. In this case, maximizations are always reformulated as minimizations.

The preference information is specified using a Python object called desdeo.preference.NIMBUSClassification. If we wanted to make the same classification as above, it can be done like so:

 classification = NIMBUSClassification(method, [
('>=', 1205.843),
('<=', 378.2263),
('=', 0.0)]
 )

Specifying subproblems¶

We can specify the maximum number of new solutions generated by the classification given. It’s also possible to specify particular scalarization functions. See desdeo.method.NIMBUS.next_iteration() for more information.

Estimates of the ICV and Nadir¶

The result of the optimization is a vector, where the components are the values of the objective functions. When optimizing the functions individually and creating the vector of these values, we get the ICV; that is, the Ideal Criterion Vector.

The ICV tells us the best solution that exists for each objective, when the functions are treated independently. However, the ICV vector is infeasible because it is usually impossible to get the best of everything at the same time - one must make compromises. For minimized functions ICV represents the lower bounds in the set of Pareto optimal solutions and the values are shown on the x-axis of the bar graph. For maximized functions ICV represents the upper bounds in the Pareto optimal set and the values can be found at the top of the bars. If the problem is complicated (that is, nonconvex) the actual components of ICV are difficult to calculate. Thus, to make sure, we refer to ICV as an estimated ICV.

The nadir is in some sense the opposite of the ICV. It consists of component values for the ‘worst case’ solution vector. For minimized functions Nadir represents the upper bounds in the set of Pareto optimal solutions and the values can be found at the top of the bars. For maximized functions Nadir represents the lower bounds in the Pareto optimal set and the values are shown on the x-axis of the bar graph. In practise, the Nadir vector is only an estimation because it is also difficult (even impossible, in the general case) to calculate.

The estimated components of the ICV and the Nadir vector are updated during the calculations, whenever the solver founds improved values. If you know the exact values or better estimates of the ICV and Nadir vectors, you can correct the estimates of the system by setting the ideal and nadir properties of your subclass of desdeo.problem.PythonProblem.

What is NAUTILUS?¶

Most interactive methods developed for solving multiobjective optimization problems sequentially generate Pareto optimal solutions and the decision maker must always trade-off to get a new solution. Instead, the family of interactive trade-off-free methods called NAUTILUS starts from the worst possible objective values and improves every objective function step by step according to the preferences of the decision maker.

Recently, the NAUTILUS family has been presented as a general NAUTILUS framework consisting of several modules. To extend the applicability of interactive methods, it is recommended that a reliable software implementation, which can be easily connected to different simulators or modelling tools, is publicly available. In this paper, we bridge the gap between presenting an algorithm and implementing it and propose a general software framework for the NAUTILUS family which facilitates the implementation of all the NAUTILUS methods, and even other interactive methods. This software framework has been designed following an object-oriented architecture and consists of several software blocks designed to cover independently the different requirements of the NAUTILUS framework. To enhance wide applicability, the implementation is available as open source code.

Glossary¶

Pareto optimality: A criterion vector z* (consisting of the values of the objective functions at a point x*) is Pareto optimal if none of its components can be improved without impairing at least one of the other components. In this case, x* is also called Pareto optimal. Synonyms for Pareto optimality are efficiency, noninteriority and Edgeworth-Pareto optimality.
Weak Pareto optimality: A criterion vector z* (consisting of the values of the objective functions at a point x*) is weakly Pareto optimal if there does not exist any other vector for which all the components are better. In this case, x* is also called weakly Pareto optimal.

Ideal criterion vector (ICV)

The ideal criterion vector consists of the best possible values each objective function can achieve. The ICV represents the lower bounds of the set of Pareto optimal solutions. (That is, Pareto optimal set)

For minimized functions the ICV is given as the Lowest Value, and for maximized functions as the Highest Value.

Current solution

Current values of the objective functions.

Nadir vector (or nadir point)

Estimated upper bounds of the solutions in the Pareto optimal set. The nadir vector represents the worst values that each objective function can attain in the Pareto optimal set.

For minimized functions the Nadir is given as the Highest Value, and for maximized functions as the Lowest Value.

(Sub)gradient

A gradient of a function consists of its partial derivatives subject to each variable. A gradient vector exists for differentiable functions. For nondifferentiable functions a more general concept subgradient is used.

Aspiration levels

For each minimized function in the class <= and maximized function in the class >= you must specify an aspiration level. The aspiration level is the value which you desire function value should be decreased or increased to.

NOTE: For minimized functions the aspiration level must be between the lowest value and the current value of the objective function. For maximized function the aspiration level must be between the current and highest value of the objective function.

Upper and lower bounds

For each minimized function in the class >= and maximized function in the class <= you must specify a boundary value. The upper or lower bounds are the largest or smallest allowable objective function value respectively.

NOTE: For minimized function the upper bound value must be between the current and highest value of the objective function. For maximized function the lower bound value must be between the current and lowest value of the objective function.

Architecture¶

Overview of the current DESDEO architecture.¶

Topical guides¶

How to get your multi-objective optimization problem working with DESDEO¶

This section describes the different ways you can get your data, model or simulation corresponding to a multi-objective optimization problem working with DESDEO. Currently, there are three approaches to adding a new problem: creating the model in Python, importing a list of solutions as data from a CSV, or interfacing to another language via Thrift.

Creating the model in Python¶

This approach is based around the classes in desdeo.problem.porcelain. This section walks through the process of defining the cylinder problem: desdeo.problem.toy.CylinderProblem. You can work through the cylinder problem notebook to gain familiarity with the cylinder problem.

from desdeo.problem.porcelain import Objective, PorcelainProblem, Variable

class CylinderProblem(PorcelainProblem):
   """
   A description of the problem goes here.
   """

The first step is to import the classes we need and create a new class which inherits from desdeo.problem.porcelain.PorcelainProblem. You should always add a docstring describing the problem so it can be displayed in the notebook interface.

    r = Variable(low=5, high=15, start=10, name="Radius")
    h = Variable(low=5, high=25, start=10, name="Height")

Next, we can define variables using the desdeo.problem.porcelain.Variable class. Here, two variables r and h are defined as the radius and height and given a range of acceptable values, a starting value and a display name.

    @Objective("Volume", maximized=True)
    def volume(r, h):
        return math.pi * r ** 2 * h

Now we define one of the objectives: maximizing the volume of the cylinder. First we define a function that takes all variables r and h in the form we have just named them. The body of the function is the formula for the volume of a cylinder $\pi r^2 h$, translated to Python code. The function is then decorated with the desdeo.problem.porcelain.Objective class where it is given a display name and the direction (maximized versus minimized) is chosen.

    @Objective("Surface Area", maximized=False)
    def surface_area(r, h):
        return 2 * math.pi * r ** 2 + 2 * math.pi * r * h

    @Objective("Height Difference", maximized=False)
    def height_diff(r, h):
        return abs(h - 15.0)

We now define the other objectives, setting maximized=False to define them as minimization problems.

    class Meta:
        name = "Cylinder Problem"

Lastly, we define the inner class Meta which is where extra settings are stored. Here, we just define the display name for the problem.

Importing a list of solutions as data¶

In this approach, you start by generating a list of solutions and write out their corresponding objective values to a CSV file <https://en.wikipedia.org/wiki/Comma-separated_values>. DESDEO can then by used to find the row corresponding to the best solution according to some preferences.

The main class involved here is desdeo.problem.PreGeneratedProblem. Usage is simple, just pass in a filename parameter:

PreGeneratedProblem(
   filename="/path/to/my/file.csv")
)

PreGeneratedProblem only works with the desdeo.optimization.PointSearch (single-objective) optimization method. So a full example using ENAUTILUS would look like:

ENAUTILUS(
    PreGeneratedProblem(
        filename="/path/to/my/file.csv"
    ),
    PointSearch,
)

Interfacing to another language via Thrift¶

In some cases, your multi-objective optimization problem may be defined in terms of simulation software you already have available. In order to transfer information from the simulation to DESDEO, a Thrift interface is provided.

(Coming soon)

API documentation¶

`desdeo.core.ResultFactory`
`desdeo.method`	This package contains methods for interactively solving multi-objective optimisation problems.
`desdeo.method.base`	This module contains the abstract base class for all interactive methods.
`desdeo.method.NAUTILUS`	NAUTILUS method variants.
`desdeo.method.NIMBUS`(problem, method_class)	’
`desdeo.optimization`	This package contains methods for solving single-objective optimisation problems.
`desdeo.optimization.OptimizationProblem`	This module contains single objective optimization problems.
`desdeo.optimization.OptimizationMethod`	This module contains methods for solving single-objective optimization problems.
`desdeo.preference`	This package contains various classes acting as containers for preference information given by a decision maker about which objectives they are concerned with and to what degree.
`desdeo.preference.base`
`desdeo.preference.direct`
`desdeo.preference.nimbus`
`desdeo.problem`	This package contains tools for modelling multi-objective optimisation problems.
`desdeo.problem.porcelain`
`desdeo.problem.toy`	This module contains simple “toy” problems suitable for demonstrating different interactive multi-objective optimization methods.
`desdeo.problem.RangeEstimators`	Contains tools to estimate the range of objective values in the Patero optimal set.
`desdeo.result`	This package contains classes for representing results obtained from running the methods in desdeo.method.
`desdeo.utils`	DESDEO Utilities
`desdeo.utils.exceptions`
`desdeo.utils.warnings`