2026-07-23T07:30:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16650 2024-03-06T10:57:57Z ddc:004 open_access

Explaining Propagation for Gini and Spread with Variable Mean Ek, Alexander Schutt, Andreas Stuckey, Peter J. Tack, Guido Spread constraint Gini index Filtering algorithm Constraint programming Lazy clause generation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Ek and Andreas Schutt and Peter J. Stuckey and Guido Tack 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.21 urn:nbn:de:0030-drops-166503 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.21 eng https://creativecommons.org/licenses/by/4.0/legalcode