GeneralDichotomy

A general and minimalist toolkit for multi-objective optimization

GeneralDichotomy is a library and a package to enumerate supported extreme solutions of general multi-objective optimization problems.

This package is independent of any single-objective optimization solver. The user implements the solving function that is called by the GeneralDichotomy algorithm. In return, the solving function provides to the algorithm the objective cost vector associated to the solution. Solution assignments are managed by the user and they can be associated to the objective cost vectors from their indices at the end of the search.

Internally, the GeneralDichotomy algorithm relies on polytope vertices enumeration to maintain a precise description of the convex hull of the Pareto front. Two polytope computation libraries can be currently used as backends: CDD and PPL. This organized search procedure provide an exhaustive set of supported (extreme) solutions when such set is enumerable. More generally, this tool can also be used with stochastic and heuristic optimizers to create a proxy of the Pareto convex hull.

The GeneralDichotomy core algorithm is implemented in C++. A C++ and a Python interface are available for the user-side (see examples). An additional Julia implementation interfaced with the JuMP package is also available.

Usage

The GeneralDichomy package can be used via the C++ or the Python programming interface. In both cases, the used creates a class where they can implement the call to their solver (which can be run from an external package for instance).

pygeneraldichotomy

Getting started

A simple example for solving linear assignment problems with cpmpy as single-objective optimization backend:

from pygeneraldichotomy import GeneralDichotomy, AbstractSolver
import cpmpy as cp
import numpy as np

class MyLapSolver(AbstractSolver):

    def __init__(self, instance):
        self.instance = instance

    def nobj(self):
        return self.instance.shape[0]

    def is_new(self, is_new_arg):
        ...

    def solve(self, weights, adj_solutions):
        nvar = self.instance.shape[1]
        x = cp.boolvar(shape=(nvar,nvar), name="x")
        weighted_obj = np.tensordot(weights, self.instance, axes=1)
        m = cp.Model([cp.sum(x[i])==1 for i in range(self.instance.shape[1])], minimize=cp.sum(weighted_obj*x))
        assert(m.solve())
        y = np.sum(x.value()*self.instance, (1,2))
        z = (y*weights).sum()
        assert(abs(m.objective_value() - z) <= 1e-3)
        return y.tolist(),z

obj1 = np.array([[3,6,4,5],
                [2,3,5,4],
                [3,5,4,2],
                [4,5,3,6]])
obj2 = np.array([[2,3,5,4],
                [5,3,4,3],
                [5,2,6,4],
                [4,5,2,5]])
obj3 = np.array([[4,2,4,2],
                [4,2,4,6],
                [4,2,6,3],
                [2,4,5,3]])

lapsolver = MyLapSolver(np.stack([obj1, obj2, obj3]))
gdalgorithm = GeneralDichotomy(lapsolver)

res = gdalgorithm.run(verbose=0)

print('solution cost vectors: ')
for elt in res[0]:
    print(elt)

install from releases

pygeneraldichotomy is available on pypi! It can be easily installed:

pip install pygeneraldichotomy

⚠️ We strongly recommend to install it in a virtual environment (conda, venv, ...) as it is still in a prototyping phase.

build from sources

Build and install from sources:

python -m build --wheel
pip install dist/*.whl

Build and test locally (for developers only):

cd "your_build_directory"
cmake .. [...]
cmake --build . -t pygdichotomy
export PYTHONPATH="your_build_directory"
python your_test_script.py

Or, in your python script:

import sys
sys.path.append("path_to_your_build_directory")

libgeneraldichotomy

libgeneraldichotomy is the C++ library

Library and package compilation

As a C++ library, the GeneralDichotomy development package must be compiled from its sources to be tested. Compilation instructions can be found on the dedicated wiki page [[Library compilation|Library-compilation]]. Note that the Python binding also needs a compilation step.

Examples

• Linear assignment [cpp,ortools]

cmake --build . -t example_lap_cpp_otools

• Linear assignment [cpp,toulbar2]

cmake --build . -t example_lap_cpp_tb2

• Linear assignment [python,pytoulbar2]

This example depends on the python package pytoulbar2 (python binding of the toulbar2 solver). It can be installed via pip install pytoulbar2 in a python environment.

To run the example from the example/python_lap directory:

export PYTHONPATH="${PYTHONPATH}:generaldichotomy_build_dir/pygeneraldichotomy" && python3 python_lap.py