2 Search Results for "Stergiou, Kostas"

Document
DOI: 10.4230/LIPIcs.CP.2023.30
The p-Dispersion Problem with Distance Constraints

Authors: Nikolaos Ploskas, Kostas Stergiou, and Dimosthenis C. Tsouros

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
In the (maxmin) p-dispersion problem we seek to locate a set of facilities in an area so that the minimum distance between any pair of facilities is maximized. We study a variant of this problem where there exist constraints specifying the minimum allowed distances between the facilities. This type of problem, which we call PDDP, has not received much attention within the literature on location and dispersion problems, despite its relevance to real scenarios. We propose both ILP and CP methods to solve the PDDP. Regarding ILP, we give two formulations derived from a classic and a state-of-the-art model for p-dispersion, respectively. Regarding CP, we first give a generic model that can be implemented within any standard CP solver, and we then propose a specialized heuristic Branch&Bound method. Experiments demonstrate that the ILP formulations are more efficient than the CP model, as the latter is unable to prove optimality in reasonable time, except for small problems, and is usually slower in finding solutions of the same quality than the ILP models. However, although the ILP approach displays good performance on small to medium size problems, it cannot efficiently handle larger ones. The heuristic CP-based method can be very efficient on larger problems and is able to quickly discover solutions to problems that are very hard for an ILP solver.
Cite as

Nikolaos Ploskas, Kostas Stergiou, and Dimosthenis C. Tsouros. The p-Dispersion Problem with Distance Constraints. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ploskas_et_al:LIPIcs.CP.2023.30,
  author =	{Ploskas, Nikolaos and Stergiou, Kostas and Tsouros, Dimosthenis C.},
  title =	{{The p-Dispersion Problem with Distance Constraints}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.30},
  URN =		{urn:nbn:de:0030-drops-190679},
  doi =		{10.4230/LIPIcs.CP.2023.30},
  annote =	{Keywords: Facility location, distance constraints, optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.54
Learning Max-CSPs via Active Constraint Acquisition

Authors: Dimosthenis C. Tsouros and Kostas Stergiou

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Constraint acquisition can assist non-expert users to model their problems as constraint networks. In active constraint acquisition, this is achieved through an interaction between the learner, who posts examples, and the user who classifies them as solutions or not. Although there has been recent progress in active constraint acquisition, the focus has only been on learning satisfaction problems with hard constraints. In this paper, we deal with the problem of learning soft constraints in optimization problems via active constraint acquisition, specifically in the context of the Max-CSP. Towards this, we first introduce a new type of queries in the context of constraint acquisition, namely partial preference queries, and then we present a novel algorithm for learning soft constraints in Max-CSPs, using such queries. We also give some experimental results.
Cite as

Dimosthenis C. Tsouros and Kostas Stergiou. Learning Max-CSPs via Active Constraint Acquisition. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{tsouros_et_al:LIPIcs.CP.2021.54,
  author =	{Tsouros, Dimosthenis C. and Stergiou, Kostas},
  title =	{{Learning Max-CSPs via Active Constraint Acquisition}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.54},
  URN =		{urn:nbn:de:0030-drops-153452},
  doi =		{10.4230/LIPIcs.CP.2021.54},
  annote =	{Keywords: Constraint acquisition, modeling, learning}
}
  • Refine by Author
  • 2 Stergiou, Kostas
  • 2 Tsouros, Dimosthenis C.
  • 1 Ploskas, Nikolaos

  • Refine by Classification
  • 2 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 1 Constraint acquisition
  • 1 Facility location
  • 1 distance constraints
  • 1 learning
  • 1 modeling
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact