☰ Declarative Programming in Machine Learning

Constraints Satisfaction Programming

Code of conduct

Exam dates

Instructor

Prof.dr. Horia F. Pop, Email:

Preliminaries

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.

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.

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.

Schedule of activities

The Teams class access code is cyseh8a.

• Wed 15-19

• Week 13 - national holiday; no classes

Online resources

• Lecture notes and other resources are available on the UBB Sharepoint platform.
• Please understand that the lecture notes will be posted here AFTER the class.

Detailed contents

1. Administrivia (1 hour)
2. Graphs related concepts (2 hours)
3. Logic Programming in Problems Solving (2 hours)
4. Introduction (1 hour) [1, Ch. 1]
   1. What is a constraint satisfaction problem?
   2. Formal Definition of the CSP
   3. Constraint Representation and Binary CSPs
   4. Examples and Applications of CSPs
   5. Constraint Programming
5. CSP solving - An overview (2 hours) [1, Ch. 2]
   1. Problem Reduction
   2. Searching For Solution Tuples
   3. Solution Synthesis
   4. Characteristics of Individual CSPs
6. Fundamental concepts in the CSP (3 hours) [1, Ch. 3]
   1. Concepts Concerning Satisfiability and Consistency
   2. Relating Consistency to Satisfiability
   3. (i, j)-consistency
   4. Redundancy of Constraints
7. Problem reduction (4 hours) [1, Ch. 4]
   1. Node and Arc-consistency Achieving Algorithms
   2. Path-consistency Achievement Algorithms
   3. Post-conditions of PC Algorithms
   4. Algorithm for Achieving k-consistency
   5. Adaptive-consistency
8. Basic search strategies for solving CSPs (4 hours) [1, Ch. 5]
   1. General Search Strategies
   2. Lookahead Strategies
   3. Gather-information-while-searching Strategies
   4. Hybrid Algorithms and Truth Maintenance
   5. Comparison of Algorithms
9. Search orders in CSPs (2 hours) [1, Ch. 6]
   1. Ordering of Variables in Searching
   2. Ordering of Values in Searching
   3. Ordering of Inferences in Searching
10. Exploitation of problem-specific features (2 hours) [1, Ch. 7]
    1. Problem Decomposition
    2. Recognition and Searching in k-trees
    3. Problem Reduction by Removing Redundant Constraints
    4. Cycle-cutsets, Stable Sets and Pseudo-Tree-Search
    5. CSPs with Binary Numerical Constraints
11. Stochastic search methods for CSPs (2 hours) [1, Ch. 8]
    1. Hill-climbing
    2. Connectionist Approach
12. Optimization in CSPs (2 hours) [1, Ch. 10]
    1. The Constraint Satisfaction Optimization Problem
    2. The Partial Constraint Satisfaction Problem

Bibliography

1. Edward P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London and San Diego, 1993, ISBN 0-12-701610-4
2. Roman Bartak, On-line Guide to Constraint Programming, Charles University, Prague, Website
3. Grzegorz Kondrak, A Theoretical Evaluation of Selected Backtracking Algorithms, M.Sc. Thesis, University of Alberta, Edmonton, 1994, PDF file
4. Constraint programming: introduction, Website

Optional bibliography

1. Some challenges for constraint programming, Website (ACM Computing Surveys)
2. Visual constraint programming tool: Oz explorer, Website
3. Algorithms for constraint satisfaction problems: A survey AI magazine, 1992, 13/1
4. Constraint satisfaction algorithms, BA Nadel, Computational Intelligence, Vol 5, 1989, pp 188-224.
5. Constraint satisfaction, AK Mackworth, Encyclopaedia of AI, Volume I, Stuart C Shapiro (ed), John Wiley and Sons, 1987, pp205-211.
6. Partial constraint satisfaction, EC Freuder and RJ Wallace, AI, vol 58, 1992, pp 21-70. (special issue on constraint based reasoning).

Constraint libraries

• Easy CSP (Java library, free software), author Victor Cordis, UBB 2010 graduate
• Choco (Java library, free software)
• Gecode (C++ library, free software)
• Disolver (C++ library, proprietary)
• ILOG Solver (C++ library, proprietary)
• Koalog Constraint Solver (Java library, proprietary)
• Minion (C++ program, GPL)
• Comet (C style language for constraint programming, GPL)
• Mozart (Oz based, Free software)

Libraries with scientific articles

• Google Scholar
• CiteSeerX
• arXiv.org

Collections with datasets for experimentation

• Google Dataset Search
• UC Irvine ML Repository
• CMU ML Datasets
• Best Public Datasets for ML and Data Science

Grading scheme

• 30% = First report (written and presented)
• 30% = Second report (written and presented)
• 40% = Final exam paper (written paper in the exams session)

Minimal requirements:

• A minimal grade average of 5 (five).
• A minimal grade of 5 (five) at the final exam.
• At least one report submitted during the semester.
  
  
• Any evaluation of the submitted materials is done during the examination session.

Rules relevance:

• All rules are equally valid for all students.
• There are no exceptions to these rules.

Students deliverables

First report

• deadline for setting the time slot = week 5, Monday 00:00 hours
• the time slot is scheduled via email on a first come first served basis, according to available slots
• the written report is send via this link as a ZIP archive including all necessary files
• if the upload system allows a ZIP archive, the file will be named r1-studentname.ZIP and uploaded as such
• if the upload system does not allow a ZIP archive, the file will be named r1-studentname.ZIP.PDF and uploaded as such
• class presentations = weeks 6-9
• the reports presentation schedule is published read-only and updated on the UBB Sharepoint platform; please do not ask for write permissions

Second report

• deadline for setting the time slot = week 9, Monday 00:00 hours
• the time slot is scheduled via email on a first come first served basis, according to available slots
• the written report is send via this link as a ZIP archive including all necessary files
• if the upload system allows a ZIP archive, the file will be named r2-studentname.ZIP and uploaded as such
• if the upload system does not allow a ZIP archive, the file will be named r2-studentname.ZIP.PDF and uploaded as such
• class presentations = weeks 10-14
• the reports presentation schedule is published read-only and updated on the UBB Sharepoint platform; please do not ask for write permissions

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

Grading of the software report

• Any report will be written in Microsoft Word (or Word online) as a DOCX file, formatted as A4, with Times New Roman 12 pt fonts, single line spacing, 2 cm wide margins.
• For the purpose of these reports, you will use Microsoft Word or compatible software. LaTeX and any other tools not leading to a DOCX file are irrelevant. This is not negociable.
• Any report not satisfying these requirements will be rejected.

The grade is set based on the following:

• completeness of the lab documentations
• quality of the lab programs
• the grading is based on:
  • 3.0 p = quality of written documentation
  • 4.0 p = quality and complexity of the source code
  • 3.0 p = quality of oral presentation

The deliverables should include:

• text file(s) with the source code (other files requiring extra procedures to obtain the source code are not acceptable);
• running-time executable files;
• data files for the tests;
• documentation (DOCX format exclusively).

Grading of the research report

• Any report will have 4,500-5,000 words and 5-10 references, will be written in Microsoft Word (or Word online) as a DOCX file, formatted as A4, with Times New Roman 12 pt fonts, single line spacing, 2 cm wide margins.
• For the purpose of these reports, you will use Microsoft Word or compatible software. LaTeX and any other tools not leading to a DOCX file are irrelevant. This is not negociable.
• Any report not satisfying these requirements will be rejected.

You will prepare and submit the following:

• the research paper, as one DOCX file
• one page executive summary, as one DOCX file
• the presentation support, as one PDF file

The grading is done as follows:

• 7.0 p = quality of written materials;
• 3.0 p = quality of oral presentation.

The grade is composed by taking into account the following:

• the papers have to represent your own work;
• the title and contents have to match the requirements;
• the papers have to fulfill the requirements of an article:
  • length of 4,500-5,000;
  • suggestive title corresponding to the contents;
  • 10 lines abstract;
  • introductory section, detailing the purpose of the paper;
  • a section integrating the topic of the paper in the general field;
  • a few main sections, according to your topic;
  • concluding remarks section;
  • bibliography of five to 10 titles; the bibliography entries have to be written correctly and completely; all the bibliography items have to be cited in the text;
• the presentation support has to correspond to the written text; any information from the presentation support has to be provided in the report itself;

Grade penalties

Complying with the requirements

• Failure to comply with the requirements leads to rejection of the report.

Penalties apply for delays

• Delays in time slot selections:
  • If the time slot is selected after the deadline, the penalty is the number of weeks between the deadline and the selection date.
  • If the time slot is not selected at all, any report submitted is ignored.
  • All emails sent to select a time slot are confirmed. If you get no confirmation, this means I did not receive your email.
• Delays in submissions of work:
  • The earliest day a report may be presented is one day after the report is submitted.
  • Multiple submissions are possible, but the last submission before the actual presentation will be considered.
  • All submissions sent on or after the presentation date will be, of course, ignored.
  • While multiple submissions are allowed, repeated uploads at intervals of few minutes are discouraged.
  • If the last submission of the report is done on or after the scheduled presentation date, the penalty is the number of weeks between the scheduled date and the submission date.
  • This penalty penalizes the extra amount of time actually required to complete the work. Such penalty refers to calendar weeks, which include, naturally, Saturdays, Sundays, National Holidays, the two weeks Christmas and New Year Holiday, the Easter Holiday, etc.

Further considerations

On reports contents

• The writing, expressing, coverage, and points of view of the presented ideas have to be your own work.
• The burden of proof stays with the writer, not the reader: the text has to confirm beyond any reasonable doubt that the student actually did the experiments s/he is commenting on.
• You cannot submit (parts of) the same work for different reports and/or different disciplines, in order to get different grades. Naturally, different disciplines mean different work.
• There is no exception to the allowed size of the reports.

On reports submission

• All reports will be submitted via the provided links.
• All work should be done inside the 14 weeks of the semester. The submission deadlines respect students holidays. Delays past the submission deadlines are offered as an exception, to allow for partial grading.
• Overlap of delays into holidays are, obviously, not an invitation for free extension of said deadlines. Consequently, all delays are penalized based on calendar time.

On reports presentation

• The reports not presented according to the schedule may be presented later after all the normally scheduled reports are presented and only with the strict observance of the official schedule.
• The points for the quality of the oral presentation are awarded (in full or in part) only if there is an actual oral presentation.
• No student may have two presentations on the same date.

Examination sessions

Activity outside the semester

• All research reports / software projects are part of the semester activity and have to be submitted inside the 14 weeks period, i.e. by the last Friday of the semester.
• No report or software project can be resubmitted and no activity can be redone for grade increase in the resit session or otherwise.

The regular examination session

• According to academic regulations, two exam dates are set:
  • the first date is set by agreement with the students;
  • the second date is set by the teacher alone.
• The attendance regulations are:
  • the students have to attend the first date;
  • the students may attend the second date at the discretion of the teacher.

The resit session

• According to academic regulations, one exam date is set.
• Only the written exam will be organized. All other activity is semester activity, and not subject to regrading.

© Prof.dr. Horia F. Pop