Getting started

In this chapter, you will:

• get an introduction of constraint programming ;

• meet Artelys Kalis ;

• discover how this book is organized ;

• discover how to obtain more information.

An overview of constraint programming

A Constraint Programming (CP) problem is defined by its decision variables with their domains and constraints over these variables. The problem definition is usually completed by a branching strategy (also referred to as enumeration or search strategy).

CP makes active use of the concept of variable domains, that is, the set out of which a decision variable takes its values. In finite domain Constraint Programming these are sets or intervals of integer numbers.

Each constraint in CP comes with its own (set of) solution algorithm(s), typically based on results from other areas, such as graph theory. Once a constraint has been established it maintains its set of variables in a solved state, i.e., its solution algorithm removes any values that it finds infeasible from the domains of the variables.

The constraints in a CP problem are linked by a mechanism called constraint propagation : whenever the domain of a variable is modified this triggers a re-evaluation of all constraints on this variable which in turn may cause modifications to other variables or further reduction of the domain of the first variable as shown in the example in Fig. 1 (the original domains of the variables are reduced by the addition of two constraints; in the last step the effect of the second constraint is propagated to the first constraint, triggering its re-evaluation).

Fig. 1 Example of constraint propagation, (a) finite domain (discrete) variables, (b) continuous variables.

A CP problem is built up incrementally by adding constraints and bounds on its variables. The solving of a CP problem starts with the statement of the first constraint. Values that violate the constraint relation are removed from the domains of the involved variables. Since the effect of a newly added constraint is propagated immediately to the entire CP problem it is generally not possible to modify or delete this constraint from the problem later on.

In some cases the combination of constraint solving and the propagation mechanism may be sufficient to prove that a problem instance is infeasible, but most of the time it will be necessary to add an enumeration for reducing all variable domains to a single value (consistent instantiation or feasible solution) or proving that no such solution exists. In addition it is possible to define an objective function (or cost function) and search for a feasible solution with the best objective function value (optimal solution).

What is Artelys Kalis ?

Artelys Kalis is an open constraint programming environment for solving combinatorial problems through a C++ library. It is based on constraint propagation techniques and powerful optimization strategies.

It is currently supporting integer variables and considering different types of constraints, including global constraints (constraints having a specific semantic and incorporating efficient propagation algorithms). As an example, you will find the KAllDifferent global constraint which enforces a list of variables to all take different values. It is often used for resource allocation constraints or assignments problems.

Artelys Kalis has been completely designed in an object-oriented manner. Variables, constraints, solutions, branching methods are provided as objects. Several standard classes for solution can be combined for specific solution search scheme.

Main features are:

• strength of constraint propagation ;

• simple and rich syntax for problem declaration ;

• multi-threaded generic search algorithms ;

• wide and extensible variety of objects for search algorithms ;

• ability to integrate user-defined objects in complex search strategies.

They yield to a number of benefits including:

• fast solution deductions ;

• rapid application developments ;

• reduced code size ;

• facilities for search strategies comparison.

Prerequisites

In order to develop applications with Artelys Kalis, this manual assumes you already know how to program in C++ and that you are able, if necessary, to find information about C++ in a specific programming guide.

It also assumes you are familiar with your operating system and development environment. Chapter 2 will explain how to install and use Artelys Kalis. You must be able to make C++ applications using a callable library or you know how to find such information (you will usually find it with your development environment documentation). Part of it is explained in chapter 2.

Overview of this manual

This chapter introduces constraint programming and Artelys Kalis.

Chapter 2 describes how to install Artelys Kalis and how to compile a program using the library.

Chapter 3 introduces the main concepts for solving a constraint problem. The main classes for problem description and resolution will be presented through an example.

Chapter 4 presents continuous variables and their use with non linear arithmetic constraints or others mixed integer/continuous constraints.

Chapter 5 describes optimization objects and the way you can use Artelys Kalis for optimization problems.

Chapter 6 describes main objects involved in tree search control and how to control the solution search.

Chapter 7 presents some strengthening techniques in constraint propagation and how to apply them with Artelys Kalis.

Chapter 8 focus on debugging and tracing tools available.

Chapter 9 describes deeply how to make new strategies using user-defined objects.

Chapter 10 presents the implementation of user constraints within the Artelys-Kalis framework.

Chapter 11 describes by the means of examples the use of the principal constraints available in Artelys-Kalis.

Chapter 12 presents the concepts behind scheduling and introduces the specialized objects that can be used for the representation and resolution of scheduling problems.

Conventions used in this manual

To help you to get the most out of this user guide, the following conventions have been employed:

• Artelys Kalis objects use the following code style: Kobject ;

• Important ideas are italicized ;

• C++ methods and statements are printed like myMethod().

Some additional graphical styles have also been used :

• Examples are given in a gray background in order to better visualize them in this way :

KSession mySession;

• Some important notes are given with a “Caution” icon. These are general points which we want to make sure that you are aware of. Here is an example:

Note

The KIntVar objects …

Reference manual

In addition to this User Guide, you can also find a Reference Manual in the standard distribution. It describes all objects involved in Artelys Kalis and all methods associated to them. You will find a description of each attributes and each method and some examples on how to use them.

The Reference Manual also contains a list of branching schemes and a list of constraints currently implemented in Artelys Kalis.

For more information

Artelys Kalis is developed, marketed and supported by Artelys. We have offices in Chicago, London, Los Angeles, Montréal and Paris. Support is provided in English or French.

Free time-limited trial versions of Artelys Kalis can be downloaded from www.artelys.com/kalis where you will also find product description, training course programs, recent news and examples.

Requests for information and purchase may be directed to:

Technical support: users under assistance may send questions related to Artelys Kalis, by e-mail, to the support team at: