Projects per year
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 loglineartime 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 floatingpoint 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 language  English 

Title of host publication  28th International Conference on Principles and Practice of Constraint Programming, CP 2022 
Editors  Christine Solnon 
Place of Publication  Saarbrücken/Wadern Germany 
Publisher  Schloss Dagstuhl 
Number of pages  16 
ISBN (Electronic)  9783959772402 
DOIs  
Publication status  Published  2022 
Event  International Conference on Principles and Practice of Constraint Programming 2022  Haifa, Israel Duration: 31 Jul 2022 → 8 Aug 2022 Conference number: 28th https://cp2022.a4cp.org/ (Website) http://chromeextension://efaidnbmnnnibpcajpcglclefindmkaj/https://drops.dagstuhl.de/opus/volltexte/2022/16629/pdf/LIPIcsCP20220.pdf (Proceedings) 
Publication series
Name  Leibniz International Proceedings in Informatics, LIPIcs 

Publisher  Schloss Dagstuhl 
Volume  235 
ISSN (Print)  18688969 
Conference
Conference  International Conference on Principles and Practice of Constraint Programming 2022 

Abbreviated title  CP 2022 
Country/Territory  Israel 
City  Haifa 
Period  31/07/22 → 8/08/22 
Internet address 
Keywords
 Constraint programming
 Filtering algorithm
 Gini index
 Lazy clause generation
 Spread constraint
Projects
 1 Active

ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)
SmithMiles, K., Stuckey, P., Taylor, P. G., Ernst, A., Aickelin, U., Garcia De La Banda, M., Pearce, A., Wallace, M., Bondell, H., Hyndman, R., Alpcan, T., Thomas, D. A., Anjomshoa, H., Kirley, M. G., Tack, G., Costa, A., Fackrell, M., Zhang, L., Glazebrook, K., Branke, J., O'Sullivan, B., O'Shea, N., Cheah, A., Meehan, A., Wetenhall, P., Bowly, D., Bridge, J., Faka, S., Mareels, I., Coleman, R. A. & Crook, J.
23/09/21 → 23/09/26
Project: Research