Metadata-Version: 2.4
Name: pygeneraldichotomy
Version: 0.0.1.5
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: description
Dynamic: description-content-type
Dynamic: license-file

# 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](https://github.com/cddlib/cddlib) and [PPL](https://github.com/BUGSENG/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](https://jump.dev/) 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:

```python
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](https://pypi.org/project/pygeneraldichotomy/)! It can be easily installed:

```bash
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:

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

Build and test locally (for developers only):

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

Or, in your python script:

```python
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`
