You are here

CP Tutorials

Four tutorials have been accepted at CP 2015.

Constraints and Bioinformatics: results and challenges

Agostino Dovier, University of Udine, Italy

Biology is a source of challenging problems for the entire field of Computer Science in general, and for the areas of computational logic and constraint programming, in particular. Successful approaches to these problems are likely to have significant applications in several fields of research, such as medicine, agriculture, industry, etc.

In this tutorial a brief overview of Bioinformatics will be presented. According to Crick's central dogma, information flow from DNA sequences to RNA sequences (transcription) and from RNA to Protein (translation). Informatics is called into play for modeling/analyzing various parts of this scheme. Genomics studies (eg problems associated to Haplotype/Phylogenetic inference and inference), Structural studies (eg problems associated to RNA secondary structure prediction and Protein structure prediction) and, finally, Systems studies (problems associated to reasoning with biological networks) will be introduced. The relevant approaches based on constraint programming (and affine techniques, such as SAT, ASP) to some of these problems will be discussed. Most of these results have been presented in issues of the workshop on constraint based methods for Bioinformatics and related publications (see, e.g., http://clp.dimi.uniud.it/wcb/). However, these approaches are not yet the definitive solution to all problems, and participants can address some points where their experience can make the difference...

Slides: https://users.dimi.uniud.it/~agostino.dovier/SLIDES/CORK_CP15.pdf

Lagrangian Relaxation for Domain Filtering

Hadrien Cambazard, G-SCOP - Grenoble Institute of Technology - School of Industrial Engineering, Grenoble, France

Lagrangian relaxation (LR) is a very important technique in operations research to reformulate and solve an integer linear program. From a Constraint Programming (CP) point of view, it offers a very simple and powerful framework to perform cost-based filtering.  The goal of the present tutorial is to explain Lagrangian relaxation and how it can be embedded as a filtering mechanism in constraint solvers.

This tutorial is designed for a Constraint Programming audience without any background in Lagrangian relaxation. Firstly, we will focus on explaining Lagrangian duality and the resolution of the Lagrangian dual with the most popular algorithms. Secondly, we will discuss cost-based filtering in the Lagrangian framework and illustrate the relationship to linear programming reduced-cost based filtering. Many ideas will be illustrated on the Multi-cost-regular and AtMostNValue global constraints. Finally we will review and discuss the current use of LR by the CP community.

Slides: http://pagesperso.g-scop.grenoble-inp.fr/~cambazah/page2/assets/tutorial_CP_2015.pdf

Towards embedded Answer Set Solving

Torsten Schaub, University of Potsdam, Germany

Answer Set Programming (ASP) offers a declarative tool for modeling and solving combinatorial (optimization) problems, while being tailored to knowledge representation and reasoning tasks. Its appealing combination of declarativeness and performance allows for concentrating on an actual problem, rather than a smart way of implementing it. So far, however, ASP was mainly used as a one-shot solving formalism, dealing with one problem at a time. On the other hand, in practice, ASP constitutes an under-the-hood technology that is usually embedded in a larger encompassing software system. This brings about the need to interact with an environment and to deal with its dynamics.

This tutorial has its focus on putting ASP at work. This comprises a good understanding of ASP's solving technology as well as basic skills in ASP's modeling capacities. In view of ASP's growing dissemination, we focus on the usage of ASP for modeling complex reasoning scenarios. This involves an introduction to the API of CLINGO 4, an ASP system with control capacities expressible in Python. We illustrate this by modeling the round-based board game Ricochet Robots and show how it was used in ASPRIN, a system for optimizing combinations of qualitative and quantitative preferences.

Slides: http://www.cs.uni-potsdam.de/~torsten/Potassco/Tutorials/cp15.pdf

XCSP3

Frederic Boussemart, Christophe Lecoutre and Cedric Piette

In this tutorial, we shall present a major revision of the format XCSP 2.1, called XCSP3, to build integrated representations of combinatorial constrained problems. This new format is able to deal with mono/multi optimization, many types of variables, cost functions, reification, views, annotations, variable quantification, distributed, probabilistic and qualitative reasoning. The new format is made compact, highly readable, and rather easy to parse. Interestingly, it partly captures the structure of the problem models, through the possibilities of declaring arrays of variables, and identifying syntactic and semantic groups of constraints. The number of constraints is kept under control by introducing a set of approximately 50 basic constraint forms, and producing almost automatically some of their variations through lifting, restriction, sliding, logical combination and relaxation mechanisms. As a result, XCSP3 encompasses practically all constraints that can be found in major constraint solvers developed by the CP community. We shall also present our website, developed conjointly with the format, which contains many series of XCSP3 problem instances coupled with a system of queries that allows selecting instances from very precise criteria. It also provides a package of tools for parsing and checking XCSP3 instances. The objective of XCSP3 is to ease the effort required to test and compare different algorithms by providing a common test-bed of combinatorial constrained instances.

Slides: http://booleconferences.ucc.ie/sites/default/files/slidesXCSP3_CP15.pdf