# A simple and efficient dichotomic search algorithm for multi-objective mixed integer linear programs

arXiv: https://arxiv.org/abs/1911.08937 · HTML: https://mlsanity.com/paper/1911.08937/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2019.

## Built on by (most cited first, 1 of 1)

- [PINN Training using Biobjective Optimization: The Trade-off between Data Loss and Residual Loss](https://mlsanity.com/paper/2302.01810/) (2023)

## Abstract (arXiv)

We present a simple and at the same time fficient algorithm to compute all nondominated extreme points in the outcome set of multi-objective mixed integer linear programmes in any dimension. The method generalizes the well-known dichotomic scheme to compute the set of nondominated extreme points in the outcome set of a bi-objective programme based on the iterative solution of weighted sum scalarizations. It uses as a main routine a convex hull algorithm. The algorithm is illustrated with, and numerically tested on, instances of multi-objective assignment and knapsack problems. Experimental results confirm the computational efficiency of the approach. Finally, an implementation in incremental polynomial time with respect to the number of computed nondominated extreme points is possible, under the assumption that the lexicographic version of the problem can be solved in polynomial time.