TUD Logo

TUD Home » ... » Teaching » Winter Term 2008/09 » Foundations of Constraint Programming

Computational Logic

Foundations of Constraint Programming

Winter Term 2008/2009

Course Description

Lecturers:
Prof. Michael Thielscher, Mr. Sebastian Voigt

See the official Course Summary page for more details.

Time Table

  • Wednesdays 4. DS (E 005):
    • Lecture: 15.10., 29.10., 12.11., 3.12., 17.12., 14.1., 28.1.
    • Exercise: 22.10., 5.11., 26.11., 10.12., 7.1., 21.1., 4.2.

Consultations

Send an email to the lecturers to fix a date.

Details about the Examination

Written exam on the 11-th of February at 10.00 am in room E005 (all written materials allowed, no electronic devices, student and personal id cart have to be presented)

On the 5th of March between 1 pm and 2 pm you can have a look at your examination result in room 2004.

Handouts and Slides

Exercises

Date of exercise Handed out Exercise sheet
22.10.2008 15.10.2008 Exercise 1
05.11.2008 29.10.2008 Exercise 2
26.11.2008 12.11.2008 Exercise 3
10.12.2008 04.12.2008 Exercise 4
07.01.2009 18.12.2008 Exercise 5
21.01.2009 13.01.2009 Exercise 6
04.02.2009 28.01.2009 Exercise 7

Additional References

  • Book "Principles of Constraint Programming" by Krzysztof Apt in the library

Programs

Constraint Programming Lab

The presentation of the programs will take place on Monday the 9th of February at 1 pm in room 2026. Please have a printout of your program with you and be prepared to present the main structure and features of your work. You should talk approximately 5 to 7 minutes. Do not prepare slides or overheads.

Students should select one of the following two tasks. The final program should be submitted no later than February, 2nd, 2009. Students may decide to work in teams of two. Following the submission, all students will have to give a personal demonstration of their program. The successful completion of the programming task is a prerequisite to participate in the final examination for the course.
  • Task 1: Solitaire Battleship

    A fleet is placed somewhere inside a 10x10 grid contains. A fleet consists of one battleship (four grid squares in length), two cruisers (each three grid squares long), three destroyers (each two squares long) and four submarines (one square each). The ships may be oriented horizontally or vertically, and no two ships will occupy adjacent grid squares, not even diagonally. The digits along the right side of and below the grid indicate the number of grid squares in the corresponding rows and columns that are occupied by vessels.

    In each specific puzzle, one or more 'shots' have been taken to start off. These may show water (indicated by wavy lines), a complete submarine (a circle), or the middle (a square), or the end (a rounded-off square) of a longer vessel.

    Here is an example problem:

      -------------------
    2|          ~        |
    4|                   |
    3|                   |
    3|                   |
    2|                   |
    4|      o            |
    1|                  o|
    1|                   |
    0|                   |
    0|                   |
     --------------------
      0 5 0 2 2 3 1 3 2 2
    
    Each `o' in the grid indicates that a submarine must occupy that square,
    and the '~' indicates water.
    
    This is the solution to the example problem:
    
      -------------------
    2|              < >  |
    4|  ^   < = >        |
    3|  |           < >  |
    3|  |     < >        |
    2|  v               o|
    4|      o   < = >    |
    1|                  o|
    1|  o                |
    0|                   |
    0|                   |
     --------------------
      0 5 0 2 2 3 1 3 2 2
    

    The taks is to write a Constraint Logic Program that solves these puzzles. The program should accept as input a file containing a problem description of the format described in www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob014/SBInstanceFileFormat

    Hint: A number of difficult instances can be found on www.csplib.org (problem number 014).

  • Task 2: Warehouse Location Problem

    A company considers opening warehouses at some candidate locations in order to supply its existing stores. Each possible warehouse has the same maintenance cost, and a capacity designating the maximum number of stores that it can supply. Each store must be supplied by exactly one open warehouse. The supply cost to a store depends on the warehouse. The objective is to determine which warehouses to open, and which of these warehouses should supply the various stores, such that the sum of the maintenance and supply costs is minimized.

    Here is an example problem:

    MaintainanceCost = 30
    
    Warehouses = {Bonn,Bordeaux,London,Paris,Rome}
    
    Stores = 10 (labeled from 0 to 9)
    
    Capacity = [1,4,2,1,3] (indexed by the five Warehouses)
    
    SupplyCost = [
     [ 20, 24, 11, 25, 30 ],
     [ 28, 27, 82, 83, 74 ],
     [ 74, 97, 71, 96, 70 ],
     [  2, 55, 73, 69, 61 ],
     [ 46, 96, 59, 83,  4 ],
     [ 42, 22, 29, 67, 59 ],
     [  1,  5, 73, 59, 56 ],
     [ 10, 73, 13, 43, 96 ],
     [ 93, 35, 63, 85, 46 ],
     [ 47, 65, 55, 71, 95 ] ]  (indexed by Store x Warehouse)
    
    The optimal solution has value 383, where:
    
    Stores of Bonn = {3}
    Stores of Bordeaux = {1,5,6,8}
    Stores of London = {7,9}
    Stores of Paris = {}
    Stores of Rome = {0,2,4}
    

    The taks is to write a Constraint Logic Program that solves arbitrary instances of this problem. The program should accept as input a file containing a problem description of the format used to specify the example instances on www.csplib.org (problem number 034).

Last modified: 1st Feb 2010, 2.28 PM
Author: Dipl.-Inf. Sebastian Haufe