Requirements

1. Objectives

• Many computational problems can be described in terms of restrictions imposed on possible solutions. Constraint Programming is a problem-solving technique that works by incorporating such restrictions into a programming environment. Constraint Programming draws on methods from artificial intelligence, logic programming, and operations research. It has been successfully applied in a number of fields such as scheduling, computational linguistics, and computational biology.
• The aim of this course is to create an understanding of the fundamental concepts underlying constraint programming; to develop skills in modeling and solving combinatorial problems; to develop skills in taking advantage of strong algorithmic techniques. The course has both a theoretical component, oriented on the study of the domain and of the relevant issues, and a practical component, oriented on the study of different typical problems, systems, platforms and libraries for constraints programming.

2. Class activities

• All activities require physical class participation. This is a full attendance, not a distance learning program.
• According to the National Education Act (1/2011), the recording of didactical activity by any means is only possible by explicit agreement of the teaching person. Consequently, no recording of any didactical activity, by any means and on any support, is allowed.
• This is a research oriented class. Your grade will be based on your own work and on your understanding of it, including your ability to explain, defend and analyse your work and your results.
• The students are invited to contact me individually, by email, at their own initiative, for any clarifications, explanations, consultations on class-relevant topics, research-relevant topics, or for required support or supervision for class-based activities.

3. Students activity

Software report

• Select two different CSP problems of your own, of a sensible complexity.
• The two problems will be of different topics; similar problems are rejected.
• Write a C++/Java program to solve the problems (use an imperative programming language).
• The CSP functionality has to be implemented separately of the main problem functionality.
• Implement at least the following methods:
  • a simple Backtracking based solution, as baseline;
  • at least two methods from the "Problem reduction" chapter;
  • at least two methods from the "Basic search strategies" and/or "Stochastic search methods" chapters;
  • functions to display the size of the constraint graph of problem;
  • functions to help comparatively analysing the methods.
• Use your own programming skills, and write your own code. Use the language of your choice.
• The student will report on his/her own actual and real experiments.
• This is not a collective work, and any assistance other than the student's own mind is not welcome.
• Constraint programming libraries may not be used.
• When using libraries, their use has to be openly documented, explained and justified.
• Any problem extensively discussed in the lecture notes and the lecture textbook may not be chosen.
• A relevant documentation hasd to be written, to include:
  • the problem,
  • the logical solution,
  • coverage of your experimentation,
  • comparative analysis of solutions,
  • relevant commented source code fragments.
• Comments inside the source file are necessary, but they do not represent a documentation.
• Any project with a documentation that contains plain text with no supporting floating bodies will be rejected. This is not an essay on English language and literature.

Research report

• An experimental study presenting and documenting the student's own experiments of an interesting application or experiment of CSP in natural science or other domains.
• The student will report on his/her own actual and real experiments.
• This is not a collective work, and any assistance other than the student's own mind is not welcome.
• The reports will convincingly show that the experiments and their analyses have actually been performed by the student.
• The reports will include the personal motivation for all the choices made.
• Computer science and all its subfields are excluded.
• Artificially designed games or situations are excluded.
• The topics approached by the student for the software project are excluded.
• All problems or subject discussed in class or available with the lecture notes are excluded.
• Any report that contains plain text with no supporting floating bodies will be rejected. This is not an essay on English language and literature.
• As a minimum, the following will be covered in the report:
  • the reasoning behind your choice
  • the problem, application or experiment that was solved via CSP methods
  • the CSP algorithms, methods and techniques used in this case
  • how the CSP-based solution was obtained and how this compares with the traditional approach
  • what do we learn from this report

© Prof.dr. Horia F. Pop