FID3014 Advanced Constraint Programming 7.5 credits

Avancerad villkorsprogrammering

Constraint Programming (CP) has established itself as both an academic field and a set of technologies for solving combinatorial (optimization) problems. This course is concerned with advanced topics in Constraint Programming that go beyond basic modeling and solving techniques. The course in particular focuses on connections of Constraint Programming with other approaches to combinatorial problem solving such as Boolean Satisfiability (SAT), Mathematical Programming, Dynamic Programming, and Local Search.

Offering and execution

Course offering missing for current semester as well as for previous and coming semesters

Course information

Content and learning outcomes

Course contents *

Constraint Programming (CP) has established itself as both an academic field and a set of technologies for solving combinatorial (optimization) problems. This course is concerned with advanced topics in Constraint Programming that go beyond basic modeling and solving techniques.  The course in particular focuses on connections of Constraint Programming with other approaches to combinatorial problem solving such as Boolean Satisfiability (SAT), Mathematical Programming, Dynamic Programming, and Local Search.

Topics include, but are not limited to: advanced search techniques such as restarts and portfolios; no-good learning and conflict analysis in SAT and CP; approaches for solving scheduling, assignment, placement, and planning problems; universal and domain-specific search heuristics; multi-objective optimization; LNS (Large Neighborhood Search); problem decompositions.

Intended learning outcomes *

After the course the student will be able to discuss, analyze, present, and critically review advanced and up-to-date specialized knowledge in Constraint Programming and make connections to knowledge in related areas.

Course Disposition

The course is organized as a reading course. Each student chooses four papers (or sets of connected papers) and for each paper the student will do the following:

  • carefully read and analyze the paper.
  • orally present the paper's content including methodology and contributions to the other course participants and the course's examiner. The presentation including discussion should take around one hour.
  • write a critical review of the paper that covers in particular: summary of contributions, methodology, significance, technical and experimental quality, and quality of presentation.

In addition to presenting four papers each, the student must read some of the papers assigned to the other course participants, attend their presentations, and actively contribute to the discussion of their papers.

Literature and preparations

Specific prerequisites *

Enrolled as a doctoral student.

Prerequisites:

The student should have completed a course on Constraint Programming on the master level such as for example "ID2204 Constraint Programming".

Recommended prerequisites

The student should have completed a course on Constraint Programming on the master level such as for example "ID2204 Constraint Programming".

Equipment

None.

Literature

The papers will be chosen from high-quality international venues such as the Constraints journal, the AI Journal, the Principles and Practice of Constraint Programming conference, the CP-AI-OR conference, and others, including book-chapters.

Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

Grading scale *

P, F

Examination *

    Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

    The examiner may apply another examination format when re-examining individual students.

    Other requirements for final grade *

    In order to pass the course, a student must have:

    • successfully presented four papers and have written a critical review for each paper.
    • read some of the papers assigned to the other course participants, attended the presentation of the other course participants, and actively participated in the discussion.

    Opportunity to complete the requirements via supplementary examination

    No information inserted

    Opportunity to raise an approved grade via renewed examination

    No information inserted

    Examiner

    No information inserted

    Ethical approach *

    • All members of a group are responsible for the group's work.
    • In any assessment, every student shall honestly disclose any help received and sources used.
    • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

    Further information

    Course web

    Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

    Course web FID3014

    Offered by

    EECS/Software and Computer Systems

    Main field of study *

    No information inserted

    Education cycle *

    Third cycle

    Add-on studies

    No information inserted

    Postgraduate course

    Postgraduate courses at EECS/Software and Computer Systems