Search Results

Documents authored by O'Sullivan, Barry

Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2024.39
An Investigation of Generic Approaches to Large Neighbourhood Search (Short Paper)

Authors: Filipe Souza, Diarmuid Grimes, and Barry O'Sullivan

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
A bottleneck in the more wide-spread use of approaches such as Large Neighborhood Search is the need for domain-specific knowledge. To this end, a number of generic LNS methods have previously been proposed that automate the selection of variables in the neighborhood with the aim of reducing the expertise requirement. Recently a new generic approach, Improved Variable-Relationship Guided LNS (iVRG), was proposed that showed promising initial results. This method combines static information regarding problem structure and dynamic information from search performance in its neighborhood selection. In this work, we first show the generalisability of the approach by comparing it on two widely studied problems, car sequencing and steel mill slab, where it outperformed existing generic approaches. We then provide a detailed examination of iVRG, investigating its key components (static/dynamic information, the use of a Tournament Selection operator) to assess their individual impact and provide insight into iVRGs overall behavior.
Cite as

Filipe Souza, Diarmuid Grimes, and Barry O'Sullivan. An Investigation of Generic Approaches to Large Neighbourhood Search (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 39:1-39:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{souza_et_al:LIPIcs.CP.2024.39,
  author =	{Souza, Filipe and Grimes, Diarmuid and O'Sullivan, Barry},
  title =	{{An Investigation of Generic Approaches to Large Neighbourhood Search}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{39:1--39:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.39},
  URN =		{urn:nbn:de:0030-drops-207248},
  doi =		{10.4230/LIPIcs.CP.2024.39},
  annote =	{Keywords: Combinatorial Optimization, Metaheuristics, Large Neighborhood Search (LNS), Machine Reassignment Problem, Car Sequencing Problem, Steel Mill Slab Problem}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.16
The Hybrid Flexible Flowshop with Transportation Times

Authors: Eddie Armstrong, Michele Garraffa, Barry O'Sullivan, and Helmut Simonis

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

Abstract
This paper presents the hybrid, flexible flowshop problem with transportation times between stages, which is an extension of an existing scheduling problem that is well-studied in the literature. We explore different models for the problem with Constraint Programming, MILP, and local search, and compare them on generated benchmark problems that reflect the problem of the industrial partner. We then study two different factory layout design problems, and use the optimization tool to understand the impact of the design choices on the solution quality.
Cite as

Eddie Armstrong, Michele Garraffa, Barry O'Sullivan, and Helmut Simonis. The Hybrid Flexible Flowshop with Transportation Times. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{armstrong_et_al:LIPIcs.CP.2021.16,
  author =	{Armstrong, Eddie and Garraffa, Michele and O'Sullivan, Barry and Simonis, Helmut},
  title =	{{The Hybrid Flexible Flowshop with Transportation Times}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{16:1--16: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.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.16},
  URN =		{urn:nbn:de:0030-drops-153075},
  doi =		{10.4230/LIPIcs.CP.2021.16},
  annote =	{Keywords: Constraint Programming, scheduling, hybrid flowshop}
}
Document
DOI: 10.4230/DagRep.4.10.1
Constraints, Optimization and Data (Dagstuhl Seminar 14411)

Authors: Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Michele Sebag

Published in: Dagstuhl Reports, Volume 4, Issue 10 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14411 "Constraints, Optimization and Data". Constraint programming and optimization have recently received considerable attention from the fields of machine learning and data mining; similarly, machine learning and data mining have received considerable attention from the fields of constraint programming and optimization. The goal of the seminar was to showcase recent progress in these different areas, with the objective of working towards a common basis of understanding, which should help to facilitate future synergies.
Cite as

Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Michele Sebag. Constraints, Optimization and Data (Dagstuhl Seminar 14411). In Dagstuhl Reports, Volume 4, Issue 10, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{deraedt_et_al:DagRep.4.10.1,
  author =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Sebag, Michele},
  title =	{{Constraints, Optimization and Data (Dagstuhl Seminar 14411)}},
  pages =	{1--31},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{10},
  editor =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Sebag, Michele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.10.1},
  URN =		{urn:nbn:de:0030-drops-48901},
  doi =		{10.4230/DagRep.4.10.1},
  annote =	{Keywords: Data mining, constraint programming, machine learning}
}
Document
DOI: 10.4230/DagRep.1.5.61
Constraint Programming meets Machine Learning and Data Mining (Dagstuhl Seminar 11201)

Authors: Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Pascal Van Hentenryck

Published in: Dagstuhl Reports, Volume 1, Issue 5 (2011)

Abstract
This report documents the programme and the outcomes of Dagstuhl Seminar 11201 "Constraint Programming meets Machine Learning and Data Mining". Our starting point in this seminar was that machine learning and data mining have developed largely independently from constraint programming till now, but that it is increasingly becoming clear that there are many opportunities for interactions between these areas: on the one hand, data mining and machine learning can be used to improve constraint solving; on the other hand, constraint solving can be used in data mining in machine learning. This seminar brought together prominent researchers from both communities to discuss these opportunities.
Cite as

Luc De Raedt, Siegfried Nijssen, Barry O'Sullivan, and Pascal Van Hentenryck. Constraint Programming meets Machine Learning and Data Mining (Dagstuhl Seminar 11201). In Dagstuhl Reports, Volume 1, Issue 5, pp. 61-83, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{deraedt_et_al:DagRep.1.5.61,
  author =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Van Hentenryck, Pascal},
  title =	{{Constraint Programming meets Machine Learning and Data Mining (Dagstuhl Seminar 11201)}},
  pages =	{61--83},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{5},
  editor =	{De Raedt, Luc and Nijssen, Siegfried and O'Sullivan, Barry and Van Hentenryck, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.5.61},
  URN =		{urn:nbn:de:0030-drops-32077},
  doi =		{10.4230/DagRep.1.5.61},
  annote =	{Keywords: Machine learning, data mining, constraint programming, constraints}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2485
Treewidth Reduction for Constrained Separation and Bipartization Problems

Authors: Dániel Marx, Barry O'Sullivan, and Igor Razgon

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.
Cite as

Dániel Marx, Barry O'Sullivan, and Igor Razgon. Treewidth Reduction for Constrained Separation and Bipartization Problems. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 561-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{marx_et_al:LIPIcs.STACS.2010.2485,
  author =	{Marx, D\'{a}niel and O'Sullivan, Barry and Razgon, Igor},
  title =	{{Treewidth Reduction for Constrained Separation and Bipartization Problems}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{561--572},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2485},
  URN =		{urn:nbn:de:0030-drops-24850},
  doi =		{10.4230/LIPIcs.STACS.2010.2485},
  annote =	{Keywords: Fixed-parameter algorithms, graph separation problems, treewidth}
}
Document
DOI: 10.4230/DagSemProc.07281.4
Directed Feedback Vertex Set is Fixed-Parameter Tractable

Authors: Igor Razgon and Barry O'Sullivan

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
We resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose an algorithm which solves this problem in $O(8^kk!*poly(n))$.
Cite as

Igor Razgon and Barry O'Sullivan. Directed Feedback Vertex Set is Fixed-Parameter Tractable. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{razgon_et_al:DagSemProc.07281.4,
  author =	{Razgon, Igor and O'Sullivan, Barry},
  title =	{{Directed Feedback Vertex Set is Fixed-Parameter Tractable}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.4},
  URN =		{urn:nbn:de:0030-drops-12363},
  doi =		{10.4230/DagSemProc.07281.4},
  annote =	{Keywords: Directed FVS, Multicut, Directed Acyclic Graph (DAG)}
}
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