HomeAboutLecturesProblem ClassesAssessmentResources

About Constraint Programming and Optimisation

Many important practical problems involve deciding how to allocate scarce resources while obeying constraints on how those resources can be used.

These tasks can all be modelled as constrained decision problems or constrained optimisation problems. The problems consist of a set of decision variables, a set of constraints limiting the values these variables can take simultaneously, and possibly a function describing some quantity we want to maximise or minimise. We can then search for solutions or do some automated reasoning to eliminate bad choices and to find good decisions.

Toolkits and libraries for optimisation have been around for decades, and many different constraint-based tools are available. See, for example, IBM's CP Optimzer, or the open source Java library Choco. The Insight centre for data analytics in the Department of Computer Science at UCC is one of the leading international research laboratories in constraint programming, and we work with many industry partners on applications of constraint technology.

In this module, we will explore how to model these problems, how to solve them using the Choco Java library, and how the underlying algorithms work, and we will study how complex these problems can become. We will also look at some other methods for solving such problems, including local search algorithms like iterated hill climbing and genetic algorithms, and we may look at linear and mixed-integer programming.

Note: constraint programming requires you think about programming in a new way -- rather than concentrate on how to solve a problem, we concentrate on how to specify the problem precisely. To do this, you have to be capable of clear thinking. To write the programs, in this module, you need to be familiar with object oriented programming in Java. To understand the algorithms that the solver uses underneath, you need to understand algorithms and data structures. The formal pre-requisites are CS1112 and CS1113 (the two 1st year modules on Foundations of Computer Science), CS2514 (the second year module on OOP in Java) and CS2515 (the first 2nd year module on Data Structures and Algorithms). If you did not complete 1st year or 2nd year in UCC, then you need to have passed equivalent modules elsewhere. Finally, you would benefit from having taken CS2516 (Algorithms and Data Structures II), for more advanced algorithms, and CS4618 (Artificial Intelligence I), or an equivalent, for the basics of search.