Modelling diversity of solutions

Linnea  Ingmar; Maria Garcia de la Banda; Peter J. Stuckey; Guido Tack

doi:10.1609/aaai.v34i02.5512

Modelling diversity of solutions

Linnea Ingmar, Maria Garcia de la Banda, Peter J. Stuckey, Guido Tack

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

27 Citations (Scopus)

Abstract

For many combinatorial problems, finding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single “best solution” and, thus, it is useful to find a representation of the non-dominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in finding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simplified in the model. This paper describes a general framework for finding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.

Original language	English
Title of host publication	Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence
Editors	Vincent Conitzer, Fei Sha
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	1528-1535
Number of pages	8
Volume	34
Edition	2
ISBN (Electronic)	9781577358350
DOIs	https://doi.org/10.1609/aaai.v34i02.5512
Publication status	Published - 2020
Event	AAAI Conference on Artificial Intelligence 2020 - New York, United States of America Duration: 7 Feb 2020 → 12 Feb 2020 Conference number: 34th https://aaai.org/Conferences/AAAI-20/ (Website)

Publication series

Name	AAAI Conference on Artificial Intelligence
Publisher	AAAI Press
Number	2
Volume	34
ISSN (Print)	2159-5399
ISSN (Electronic)	2374-3468

Conference

Conference	AAAI Conference on Artificial Intelligence 2020
Abbreviated title	AAAI 2020
Country/Territory	United States of America
City	New York
Period	7/02/20 → 12/02/20
Other	The Thirty-Fourth AAAI Conference on Artificial Intelligence was held on February 7–12, 2020 in New York, New York, USA. The surge in public interest in AI technologies, which we have witnessed over the past few years, continued to accelerate in 2019–2020, with the societal and economic impact of AI becoming a central point of public and government discussion worldwide. AAAI-20 saw submissions and attendance numbers that were records in the history of the AAAI series of conferences and continued its tradition of attracting top-quality papers from all areas of AI. We were excited to see increases in submissions across almost all areas. The AAAI-20 program consisted of a core technical program of original research presentations, including a special track on AI for social impact and a sister conference track. It additionally featured a broad range of tutorials, workshops, invited talks, panels, student abstracts, a debate, and presentations by senior members. The program was rounded out by technical demonstrations, exhibits, an AI job fair, the AI in Practice program, a student outreach program, and a game night. The conference also continued its tradition of colocating with the long-running IAAI conference and the EAAI symposium, as well as the newer conference on AI, Ethics, and Society.
Internet address	https://aaai.org/Conferences/AAAI-20/ (Website)

Access to Document

10.1609/aaai.v34i02.5512

325513324-oaFinal published version, 535 KB

Cite this

Ingmar, L., Garcia de la Banda, M., Stuckey, P. J., & Tack, G. (2020). Modelling diversity of solutions. In V. Conitzer, & F. Sha (Eds.), Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence (2 ed., Vol. 34, pp. 1528-1535). (AAAI Conference on Artificial Intelligence; Vol. 34, No. 2). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/aaai.v34i02.5512

Ingmar, Linnea ; Garcia de la Banda, Maria ; Stuckey, Peter J. et al. / Modelling diversity of solutions. Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence. editor / Vincent Conitzer ; Fei Sha. Vol. 34 2. ed. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2020. pp. 1528-1535 (AAAI Conference on Artificial Intelligence; 2).

@inproceedings{bc7decd0adbd44d4862224e722ebaf3c,

title = "Modelling diversity of solutions",

abstract = "For many combinatorial problems, finding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single “best solution” and, thus, it is useful to find a representation of the non-dominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in finding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simplified in the model. This paper describes a general framework for finding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.",

author = "Linnea Ingmar and {Garcia de la Banda}, Maria and Stuckey, {Peter J.} and Guido Tack",

note = "Funding Information: Acknowledgements This work was partly sponsored by the Australian Research Council grant DP180100151. The authors would like to thank the anonymous reviewers for their helpful comments, and Ilankaikone Senthooran for providing instances for the case study in the experimental evaluation of this work. Publisher Copyright: Copyright {\textcopyright} 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; AAAI Conference on Artificial Intelligence 2020, AAAI 2020 ; Conference date: 07-02-2020 Through 12-02-2020",

year = "2020",

doi = "10.1609/aaai.v34i02.5512",

language = "English",

volume = "34",

series = "AAAI Conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

number = "2",

pages = "1528--1535",

editor = "Conitzer, {Vincent } and Sha, {Fei }",

booktitle = "Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence",

address = "United States of America",

edition = "2",

url = "https://aaai.org/Conferences/AAAI-20/",

}

Ingmar, L, Garcia de la Banda, M , Stuckey, PJ & Tack, G 2020, Modelling diversity of solutions. in V Conitzer & F Sha (eds), Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence. 2 edn, vol. 34, AAAI Conference on Artificial Intelligence, no. 2, vol. 34, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 1528-1535, AAAI Conference on Artificial Intelligence 2020, New York, New York, United States of America, 7/02/20. https://doi.org/10.1609/aaai.v34i02.5512

Modelling diversity of solutions. / Ingmar, Linnea ; Garcia de la Banda, Maria ; Stuckey, Peter J. et al.
Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence. ed. / Vincent Conitzer; Fei Sha. Vol. 34 2. ed. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2020. p. 1528-1535 (AAAI Conference on Artificial Intelligence; Vol. 34, No. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Modelling diversity of solutions

AU - Ingmar, Linnea

AU - Garcia de la Banda, Maria

AU - Stuckey, Peter J.

AU - Tack, Guido

N1 - Conference code: 34th

PY - 2020

Y1 - 2020

N2 - For many combinatorial problems, finding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single “best solution” and, thus, it is useful to find a representation of the non-dominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in finding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simplified in the model. This paper describes a general framework for finding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.

AB - For many combinatorial problems, finding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single “best solution” and, thus, it is useful to find a representation of the non-dominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in finding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simplified in the model. This paper describes a general framework for finding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.

UR - http://www.scopus.com/inward/record.url?scp=85091300996&partnerID=8YFLogxK

U2 - 10.1609/aaai.v34i02.5512

DO - 10.1609/aaai.v34i02.5512

M3 - Conference Paper

AN - SCOPUS:85091300996

VL - 34

T3 - AAAI Conference on Artificial Intelligence

SP - 1528

EP - 1535

BT - Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence

A2 - Conitzer, Vincent

A2 - Sha, Fei

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

T2 - AAAI Conference on Artificial Intelligence 2020

Y2 - 7 February 2020 through 12 February 2020

ER -

Ingmar L, Garcia de la Banda M , Stuckey PJ , Tack G. Modelling diversity of solutions. In Conitzer V, Sha F, editors, Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence. 2 ed. Vol. 34. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2020. p. 1528-1535. (AAAI Conference on Artificial Intelligence; 2). doi: 10.1609/aaai.v34i02.5512

Modelling diversity of solutions

Abstract

Publication series

Conference

Access to Document

Other files and links

Learning from learning solvers

Cite this

Modelling diversity of solutions

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

Learning from learning solvers

Cite this