Practical applications of combinatorial optimization problems often exhibit more than one objective (e.g., environmental costs), which can be addressed by multi-objective optimization. Unfortunately, solving multi-objective problems requires an expensive enumeration where each sub-problem is generally more challenging than their single-objective equivalent. As an alternative to a complete enumeration, the linear scalarization is a simple and popular approach consisting in aggregating the objectives into a single one with a weighted sum. This approach is able to provide a subset of the pareto-optimal solutions and can be easily implemented with single-objective solvers. However defining a limited set of weights to obtain a complete and diverse set of solutions remains difficult when considering any number of objectives. Despite several algorithmic and software contributions, no all-purpose weight-enumeration algorithm is currently available to our knowledge, the existing ones being limited to few problems and solvers.

We present an algorithmic and a software contribution to address this current limitation. Our algorithm is able to perform a complete enumeration by maintaining and efficiently updating a decomposition of a weight space. Practically, our software contribution is a library that is solver and problem independent. The user defines the call to their single-objective solver in a callback function and they are able to run the method to enumerate the supported extreme solutions. Our proof of concept is implemented in C++ and Python and is available at https://forge.inrae.fr/opteam/generaldichotomy. It relies on polytope computation libraries for the decomposition of the weights. The multi-language interface facilitates its use with modeling languages and solvers.