DROPS

Document

Tool Description

DOI: 10.4230/OASIcs.ICLP.2017.5

Logic Programming with Max-Clique and its Application to Graph Coloring (Tool Description)

Authors: Michael Codish, Michael Frank, Amit Metodi, and Morad Muslimany

Published in: OASIcs, Volume 58, Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)

Abstract

This paper presents pl-cliquer, a Prolog interface to the cliquer tool for the maximum clique problem. Using pl-cliquer facilitates a programming style that allows logic programs to integrate with other tools such as: Boolean satisfiability solvers, finite domain constraint solvers, and graph isomorphism tools. We illustrate this programming style to solve the Graph Coloring problem, applying a symmetry break that derives from finding a maximum clique in the input graph. We present an experimentation of the resulting Graph Coloring solver on two benchmarks, one from the graph coloring community and the other from the examination timetabling community. The implementation of pl-cliquer consists of two components: A lightweight C interface, connecting cliquer's C library and Prolog, and a Prolog module which loads the library. The complete tool is available as a SWI-Prolog module.

Cite as

Michael Codish, Michael Frank, Amit Metodi, and Morad Muslimany. Logic Programming with Max-Clique and its Application to Graph Coloring (Tool Description). In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017). Open Access Series in Informatics (OASIcs), Volume 58, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{codish_et_al:OASIcs.ICLP.2017.5,
  author =	{Codish, Michael and Frank, Michael and Metodi, Amit and Muslimany, Morad},
  title =	{{Logic Programming with Max-Clique and its Application to Graph Coloring}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{5:1--5:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Rocha, Ricardo and Son, Tran Cao and Mears, Christopher and Saeedloei, Neda},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2017.5},
  URN =		{urn:nbn:de:0030-drops-84559},
  doi =		{10.4230/OASIcs.ICLP.2017.5},
  annote =	{Keywords: Logic Programming, Constraints, Maximum Clique}
}

Document

DOI: 10.4230/OASIcs.ICLP.2016.21

Methods for Solving Extremal Problems in Practice

Authors: Michael Frank

Published in: OASIcs, Volume 52, Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016)

Abstract

During the 20 th century there has been an incredible progress in solving theoretically hard problems in practice. One of the most prominent examples is the DPLL algorithm and its derivatives to solve the Boolean satisfiability problem, which can handle instances with millions of variables and clauses in reasonable time, notwithstanding the theoretical difficulty of solving the problem. Despite this progress, there are classes of problems that contain especially hard instances, which have remained open for decades despite their relative small size. One such class is the class of extremal problems, which typically involve finding a combinatorial object under some constraints (e.g, the search for Ramsey numbers). In recent years, a number of specialized methods have emerged to tackle extremal problems. Most of these methods are applied to a specific problem, despite the fact there is a great deal in common between different problems. Following a meticulous examination of these methods, we would like to extend them to handle general extremal problems. Further more, we would like to offer ways to exploit the general structure of extremal problems in order to develop constraints and symmetry breaking techniques which will, hopefully, improve existing tools. The latter point is of immense importance in the context of extremal problems, which often hamper existing tools when there is a great deal of symmetry in the search space, or when not enough is known of the problem structure. For example, if a graph is a solution to a problem instance, in many cases any isomorphic graph will also be a solution. In such cases, existing methods can usually be applied only if the model excludes symmetries.

Cite as

Michael Frank. Methods for Solving Extremal Problems in Practice. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016). Open Access Series in Informatics (OASIcs), Volume 52, pp. 21:1-21:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{frank:OASIcs.ICLP.2016.21,
  author =	{Frank, Michael},
  title =	{{Methods for Solving Extremal Problems in Practice}},
  booktitle =	{Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016)},
  pages =	{21:1--21:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-007-1},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{52},
  editor =	{Carro, Manuel and King, Andy and Saeedloei, Neda and De Vos, Marina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2016.21},
  URN =		{urn:nbn:de:0030-drops-67513},
  doi =		{10.4230/OASIcs.ICLP.2016.21},
  annote =	{Keywords: Extremal Problems, Constraints, SAT Solving, Logic Programming, Parallelism}
}

Search Results

Documents authored by Frank, Michael

Logic Programming with Max-Clique and its Application to Graph Coloring (Tool Description)

Abstract

Cite as

Methods for Solving Extremal Problems in Practice

Abstract

Cite as

Thanks for your feedback!

Could not send message