moiptimiser 0.0.12

Multi-Objective Integer Programming with Gurobi and Python

Multi-Objective Integer Programming with Gurobi and Python

The optimisation software from Gurobi now supports multi-objective programming.

Since there are multiple objectives, there may be many solutions, each of which may optimise the objectives with a different set of priorities. Finding all such solutions can be algorithmically costly, so Gurobi’s solver only returns a single result.

However, due to the importance of such functionality, much research has been invested into finding better algorithms that can efficiently find all solutions.

This python package extends Gurobi’s multi-objective functionality by using the algorithms developed by (Ozlen et al., 2014) and (Tamby & Vanderpooten, 2020). It provides a module that can be used in python programs, as well as a command line tool that can read multi-objective LP files.

Many of the examples found in this project have been converted from the examples shared by William Pettersson on figshare, which were used to benchmark the parallel processing algorithm described in (Pettersson & Ozlen, 2019).

• Free software: MIT license

Installation

pip install moiptimiser

You can also install the in-development version with:

pip install https://github.com/bayan/python-moiptimiser/archive/master.zip

Documentation

https://python-moiptimiser.readthedocs.io/

Development

Install python libraries:

pip install cmake dlib gurobipy tox twine wheel bumpversion

To run the all tests and checks run:

tox

To run the all python automated tests run:

tox -e py39

To create a new patch and upload to github:

bumpversion patch
git push -u origin master
git push -u origin master vX.X.X

To package and deploy to PyPI:

python setup.py clean --all sdist bdist_wheel
twine upload --skip-existing dist/*.whl dist/*.gz

To run as a script from the command line:

cd src/
python3 -m moiptimiser /path/to/example.lp

References

Ozlen, M., Burton, B.A., MacRae, C.A.G., 2014. Multi-Objective Integer Programming: An Improved Recursive Algorithm. J Optim Theory Appl 160, 470–482. https://doi.org/10.1007/s10957-013-0364-y

Pettersson, W., & Ozlen, M. (2019). Multiobjective Integer Programming: Synergistic Parallel Approaches. INFORMS Journal on Computing, 32(2), 461–472. https://doi.org/10.1287/ijoc.2018.0875

Tamby, S., & Vanderpooten, D. (2020). Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems. INFORMS Journal on Computing, 33(1), 72–85. https://doi.org/10.1287/ijoc.2020.0953

Changelog

0.0.0 (2020-05-13)

• First release on PyPI.

0.0.1 (2020-05-19)

• First working version, using the (Ozlen et al., 2014) algorithm, for minimisation problems.

0.0.2 (2020-05-19)

• Implemented maximisation problem solving.

• Improved documentation.

• Improved testing suite.

0.0.3 (2021-11-24)

• New state of the art algorithm - two stage approach from (Tamby & Vanderpooten, 2020) - implemented and set as the default for the command line executable.

0.0.4 (2021-11-24)

• Documentation and changelog changes that were missed in previous release.

0.0.5 (2021-11-24)

• Specify python version to prevent failing documentation build on https://readthedocs.org/

0.0.6 (2021-12-05)

• Specify which algorithm to use from the command line.

• Keep track of the number of solver calls and report in output.

• Bug fixes to (Tamby & Vanderpooten, 2020) implementation.

0.0.7 (2021-12-05)

• Provide feasible solutions to solver for (Tamby & Vanderpooten, 2020) implementation.

• Lower required python version number from 3.9 to 3.7 to get online docs compiling.

0.0.8 (2021-12-06)

• Finally got the documentation compiling on https://readthedocs.org/

• Implemented direct strategy from (Tamby & Vanderpooten, 2020).

0.0.9 (2021-12-07)

• Track and report the number of infeasible problems attempted.

• Converted examples from William Pettersson on figshare to be used for testing algorithms and benchmarking.

0.0.10 (2021-12-08)

• Fixed rounding bug in (Ozlen et al., 2014).

• Minor code clean up and documentation updates.

0.0.11 (2021-12-08)

• Documentation bug fix.

0.0.12 (2021-12-14)

• Refactored (Ozlen et al., 2014) to fix bugs, simplify the code and tweak the performance.

• Changed CPU Time format in command line output