A constraint programming algorithm for finding leximin-optimal allocations

Authors

  • Rahmatullah Muin

DOI:

https://doi.org/10.52502/ijitas.v2i2.11

Keywords:

machine learning, detection systems

Abstract

In the context of constraint programming, we propose an algorithm solving the following problem: allocate in an equitable and efficient way a finite set of objects to agents each having their own utilities, under admissibility constraints. The algorithm calculates an allocation maximizing the leximin order on the utility profiles of the agents. We also describe the field of application that motivated this work: the sharing of satellite resources. We extract a simple and precise problem of fair allocation, which serves as a basis, thanks to a generator of test sets, for the evaluation of the proposed algorithm. Two implementations of the algorithm are compared, one in "pure" constraint programming, with Choco, the other in mixed linear programming with Cplex.

Downloads

Published

2020-04-30

How to Cite

[1]
R. Muin, “A constraint programming algorithm for finding leximin-optimal allocations”, IJITAS, vol. 2, no. 2, pp. 14–20, Apr. 2020.

Issue

Section

Articles