Up: Teaching
Computer Science 890BR 
Constraint
Programming
Course Outline Spring/Summer 2011
|
Instructor: |
Office:
CW 308.13 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
Method
of Evaluation: |
Project
(4 Reports 30% + Presentation 20% + Implementation 20%) |
70% |
|
|
|
Final
Exam |
30% |
|
|
|
|
|
|
|
|
|
Recommended Documentation
- Constraint
Processing, R. Dechter, Academic Press, London
and San Diego, 2003.
- On-line guide to constraint programming by Roman Barták.
- Algorithms for Constraint Satisfaction Problems: A Survey, Kumar, AI Magazine 13(1):32-44, 1992.
Topics
- Constraint Processing: CSPs, Systematic Search for CSPs, Constraint Propagation,
Variable and Value Ordering Heuristics, Tree-Structured CSPs.
- Metaheuristics: Discrete Optimization
Problems, Decision vs Optimization Problems,
SAT, TSP, Partial Constraint Satisfaction, Branch and Bound, Stochastic
Local Search, Evolutionary Techniques.
- Combinatorial Auctions: Exact Methods,
Approximation Methods including Local Search and Evolutionary Techniques.
Project
·
The
term project consists of studying several exact and approximation techniques
for solving the combinatorial forward auctions problem.
·
3 progress reports (minimum of 10 pages for each)
have to be submitted respectively by the
end of May, end of June and end of July.
·
The first report should include a literature review
on solving online combinatorial auctions using exact and approximation methods.
·
The second report should include a detailed
description of the methods to study for solving the combinatorial forward
auctions.
·
The third report should describe the comparative
experimentation of the solving methods.
·
The
term report (minimum 20 pages) has to be submitted by Monday August 22nd and should include a literature
review, the detailed description of the methods explored, a discussion of the
comparative experimental results, concluding remarks and ideas for future work.
·
The
presentation and final exam will be scheduled between August 22nd and August 26th. The presentation
slides have to be submitted the day before the presentation.
·
The
code of the implementation has to be submitted by Friday August 26th.
·
All
the required materials (4 reports, presentation slides and code) have to be
submitted by email to mouhoubm@uregina.ca
Policies
·
Any
question regarding this course should be promptly addressed to the instructor
by email at mouhoubm@uregina.ca
·
All
the submitted materials (reports,
presentation slides and code) should be the student’s own original and
individual work. The student is encouraged to read the section on Academic Conduct and Misconduct of the Graduate Calendar.
Up:Teaching