The 19th International Conference on
Principles and Practice of
Constraint Programming
Uppsala, Sweden
September 16-20, 2013

Tutorials

Replication and Recomputation in Scientific Experiments

Speakers: Ian Gent, University of St. Andrews, UK, and Lars Kotthoff, University College Cork, Ireland

Abstract

Replication of experimental results is critical to the proper process of Science in any discipline. In Computer Science (and therefore Constraint Programming), replication of experimental results means recomputing and confirming them. Our discipline has the great advantage that computational experiments are inherently more replicable than in most disciplines: we simply re-run the program. Unfortunately, practical considerations result in many experiments not being replicable even though in principle they should be. This impacts the scientific integrity of the field as a whole.

This tutorial will discuss the general principles of “recomputation”. By recomputation, we mean the replication of experiments in computational science. The tutorial will be in two parts. First we will discuss the nature of computational experiments and why Computer Science would be better if experiments were made available for recomputation as standard practice. This will be based on “The Recomputation Manifesto” by Ian Gent, which argues that recomputation should become a standard part of Computer Science experimental methodology. The second part of the tutorial will discuss methods for making experiments recomputable. One method will be providing virtual machines to embody an experiment, but we will also discuss methods which are less intensive on resources such as bandwidth and storage space. The focus will be on making it easy for experimenters to make their experiments recomputable, and making it easy for other scientists to recompute past experiments.

We will invite participants in the tutorial to submit experiments for past and future papers to an experimental repository.

Short Bios

Ian Gent is Professor of Computer Science at the University of St Andrews, Scotland. His interest in the proper foundations of empirical science in computing date almost 20 years.

Lars Kotthoff is a postdoctoral researcher at Cork Constraint Computation Centre. His research focuses on algorithm selection and marrying optimisation methods and machine learning. He is also interested in how to conduct computational experiments better and ways of making them reproducible.

Constraint programming for the control of discrete event dynamic systems.

Speaker: Gérard Verfaillie, ONERA, France

Abstract

In this tutorial, after defining discrete event (hybrid) dynamic systems, their main features (complete or partial controllability, complete or partial observability), and the tools that are used to model them (automata, Petri nets, Markov chains), we will present the main properties that are sought when controlling such systems (safety, reachability, any property or criterion on state trajectories). Then, we will describe the main approaches that can be used to define a discrete controller (manual definition of decision rules, automatic learning of decision rules, automatic synthesis of policies, automatic synthesis of plans). After that, we will focus on three problems for which constraint programming is used or could be profitably used: the automatic synthesis of policies in non deterministic domains, the automatic synthesis of plans and schedules in deterministic domains, and the synthesis of plans and schedules applied to non deterministic domains (robustness, flexibility, planning and replanning, online planning).

Short Bio

Graduated from École Polytechnique (Paris) in 1971 and from SUPAÉRO (French National Engineering School in Aeronautics and Space, Computer Science Specialization, Toulouse) in 1985, Gérard Verfaillie is now Research Supervisor at ONERA (The French Aerospace Lab). His research activity is related to models, methods, and tools for combinatorial optimization and constrained optimization, especially for planning and decision-making. Automated planning of activities for Earth surveillance and observation satellites, either on the ground or on board, has been one of its main application domains.

Constraint Programming for Vehicle Routing Problems

Speaker: Phil Kilby, Optimization Research Group, NICTA

Abstract

Vehicle Routing deals with the problem of transporting goods or services from where they are to where they need to be. This might be delivering bread from depots to each individual shop, planning regular maintenance visits for elevators, or waste collection.

These problems are very diverse, and a large variety of objectives and constraints are seen in practice. Constraint Programming is an excellent tool to use in solving these problems, as it offers immense flexibility in specifying and solving the types of problem encountered in practice.

This tutorial will look at models for representing vehicle routing problems, and how they can be solved in practice. We will look at a number of solution methods, but concentrate on insertion-type methods that are able to make maximum use of constraint propagation.

We will start with basic formulations of the problem, but work our way through to some of the recent advances – like effective cost propagation, and dynamically partitioned Large Neighbourhood Search.

Short Bio

Philip Kilby is a Principal Researcher with Optimisation Research Group at NICTA, Australia. He has extensive experience in applying optimisation and constraint programming techniques to real-world problems, particularly in transportation.

MaxSAT Latest Developments

Speaker: Carlos Ansótegui, University of Lleida, Spain.

Abstract

The Maximum Satisfiability (MaxSAT) problem is the optimization version of the Satisfiability problem.SAT technology has been shown to be very effective for solving several industrial instances. Therefore, we expect MaxSAT technology to become an efficient approach for solving several industrial optimization problems. This technology can be applied in several domains, such as: scheduling and timetabling problems, FPGA routing, software package installation, design debugging, bioinformatics, probabilistic reasoning, etc.

Since 2006, MaxSAT solvers have experienced a significant boost in performance. In this tutorial, we will focus on the key details of the most efficient MaxSAT algorithms. These solvers, called SAT-based, consist in the reformulation of the MaxSAT problem as the resolution of a sequence of SAT instances. Therefore, state-of-the-art SAT solvers can be easily incorporated within this approach with almost no additional cost. In particular, SAT-based solvers show the best performance for the industrial instances available at the international MaxSAT Evaluation.

We will emphasize implementation aspects of the most efficient solvers not fully described in the literature. We will also show how to apply other technologies from Satisfiability Modulo Theories (SMT) and Integer Linear Programming (ILP). Finally, we will present modeling and solving frameworks for solving intensional WCSPs through their compilation into Weighted SMT instances.

Short Bio

Carlos Ansótegui is currently associate professor at the University of Lleida, Spain. His research interests include: modeling and solving decision and optimization problems, through the application of Constraint Programming techniques. In particular, those from Satisfiability, Satisfiability Modulo Theories or Maximum Satisfiability. He has coauthored several papers on efficient solvers for the MaxSAT problem. These solvers have ranked among the best at the international MaxSAT Evaluation.