Explaining propagation for Gini and spread with variable mean

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

In optimisation problems involving multiple agents (stakeholders) we often want to make sure that the solution is balanced and fair. That is, we want to maximise total utility subject to an upper bound on the statistical dispersion (e.g., spread or the Gini coefficient) of the utility given to different agents, or minimise dispersion subject to some lower bounds on utility. These needs arise in, for example, balancing tardiness in scheduling, unwanted shifts in rostering, and desired resources in resource allocation, or minimising deviation from a baseline in schedule repair, to name a few. These problems are often quite challenging. To solve them efficiently we want to effectively reason about dispersion. Previous work has studied the case where the mean is fixed, but this may not be possible for many problems, e.g., scheduling where total utility depends on the final schedule. In this paper we introduce two log-linear-time dispersion propagators – (a) spread (variance, and indirectly standard deviation) and (b) the Gini coefficient – capable of explaining their propagations, thus allowing effective clause learning solvers to be applied to these problems. Propagators for (a) exist in the literature but do not explain themselves, while propagators for (b) have not been previously studied. We avoid introducing floating-point variables, which are usually not supported by learning solvers, by reasoning about scaled, integer versions of the constraints. We show through experimentation that clause learning can substantially improve the solving of problems where we want to bound dispersion and optimise total utility and vice versa.

Original languageEnglish
Title of host publication28th International Conference on Principles and Practice of Constraint Programming, CP 2022
EditorsChristine Solnon
Place of PublicationSaarbrücken/Wadern Germany
PublisherSchloss Dagstuhl
Number of pages16
ISBN (Electronic)9783959772402
DOIs
Publication statusPublished - 2022
EventInternational Conference on Principles and Practice of Constraint Programming 2022 - Haifa, Israel
Duration: 31 Jul 20228 Aug 2022
Conference number: 28th
https://cp2022.a4cp.org/ (Website)
http://chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://drops.dagstuhl.de/opus/volltexte/2022/16629/pdf/LIPIcs-CP-2022-0.pdf (Proceedings)

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl
Volume235
ISSN (Print)1868-8969

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2022
Abbreviated titleCP 2022
Country/TerritoryIsrael
CityHaifa
Period31/07/228/08/22
Internet address

Keywords

  • Constraint programming
  • Filtering algorithm
  • Gini index
  • Lazy clause generation
  • Spread constraint

Cite this