|
|
Schedule
Note: All classes are 9-11:20am. Monday classes are held
in DC 3313; Thursday classes are held in MC 2036
Monday, September 10:
Monday, September 17:
Thursday, September 20:
Note: Not the usual room. Held in MC 2036.
Topic: Constraint propagation (continued)
-
Local consistency:
bounds consistency,
singleton consistencies,
k-consistency
-
Global constraints: alldifferent constraint, global cardinality
constraint, regular constraint, sequence constraint
Background reading:
-
W.-J. van Hoeve and I. Katriel.
Global constraints.
Chapter 6 in Handbook of Constraint Programming,
169-208,
Elsevier, 2006.
Monday, October 1:
Thursday, October 4:
Note: Not the usual room. Held in MC 2036.
Topic: Backtracking search
-
Branching strategies,
constraint propagation during search,
variable and value ordering heuristics
Background reading:
-
P. van Beek
Backtracking search algorithms.
Chapter 4 in Handbook of Constraint Programming,
85-134,
Elsevier, 2006.
Research papers:
-
F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais.
Boosting Systematic Search by Weighting Constraints.
Proceedings of the ECAI-2004, Valencia, Spain, 2004.
Presenter: Myung Sub Kim
(slides.ppt)
-
A. Zanarini and G. Pesant.
Solution Counting Algorithms for
Constraint-Centered Search Heuristics.
Proceedings of CP-2007, Providence, RI, 2007.
Presenter: Niv Shaft
(slides.ppt)
Due:
-
Critique of one of the papers from the list of papers for today.
Thursday, October 11:
Note: Not the usual room. Held in MC 2036.
Topic: Backtracking search (continued)
-
nogood recording,
non-chronological backtracking
Research papers:
-
U. Junker.
QuickXplain: Preferred Explanations and Relaxations
for Over-Constrained Problems.
Proceedings of the AAAI-2004,
San Jose, California, 2004.
Presenter: Olga Miltchman
(slides.ppt)
-
G. Katsirelos and F. Bacchus.
Generalized Nogoods in CSPs.
Proceedings of AAAI-2005,
Pittsburgh, 2005.
Presenter: Matthew Stephan
(slides.ppt)
Due:
-
Critique of one of the papers from the list of papers for today.
Monday, October 15:
Monday, November 5:
Monday, November 12:
Topic: Local search
-
Iterative improvement, non-improving steps, tabu search,
local search for constraint optimization problems
Background reading:
-
H.H. Hoos and E. Tsang.
Local search methods.
Chapter 5 in Handbook of Constraint Programming,
135-168,
Elsevier, 2006.
Research papers:
-
P. Van Hentenryck and L. Michel.
Synthesis of Constraint-Based Local Search
Algorithms from High-Level Models.
Proceedings of the AAAI-2007, Vancouver, 2007.
Presenter: Marshall Hahn
(slides.ppt)
-
P. Van Hentenryck and Y. Vergados.
Population-Based Simulated Annealing for Traveling Tournaments.
Proceedings of the AAAI-2007, Vancouver, 2007.
Presenter: Shahab Mohsen
(slides.ppt)
Due:
-
Critique of one of the papers from the list of papers for today.
Monday, November 19:
Topic: Modeling
-
Alternative models, auxiliary variables, implied constraints,
dominance constraints, reformulations, combining models
(slides.ppt)
Background reading:
-
B.M. Smith.
Modelling.
Chapter 11 in Handbook of Constraint Programming,
377-406,
Elsevier, 2006.
Research papers:
-
I. Dotu, A. del Val, and M. Cebrian.
Redundant Modeling for the QuasiGroup Completion Problem.
Proceedings of CP-2003, Kinsale, Ireland, 2003.
Presenter: Mehrdad Nojoumian
(slides.ppt)
-
N. Nethercote, P.J. Stuckey, R. Becket, S. Brand, G.J. Duck, G. Tack.
MiniZinc: Towards a standard CP modelling language.
Proceedings of CP-2007, Providence, RI, 2007.
Presenter: Kate Kinnear
(slides.ppt)
Due:
-
Critique of one of the papers from the list of papers for today.
Monday, November 26:
Topic: Modeling
-
Alternative models, auxiliary variables, implied constraints,
dominance constraints, reformulations, combining models
(slides.ppt)
Research papers:
-
B. M. Smith.
Symmetry and Search in a Network Design Problem.
Proceedings of CP-AI-OR-2005, Prague, 2005.
Presenter: Sayyid Hasan Riyaz
-
A.M. Frisch, C. Jefferson, and I. Miguel.
Symmetry Breaking as a Prelude to Implied Constraints:
A Constraint Modelling Pattern.
Proceedings of the ECAI-2004, Valencia, Spain, 2004.
Presenter: Abdul Jalil Mohamed
Monday, December 17:
Presentations of course projects. Each presentation will be
25 minutes (20 minute talk, 5 minutes for questions at the end):
-
Niv Shaft and Myung Sub Kim
-
Jun Fung and Matthew Stephan
-
Marshall Hahn and Kate Kinnear
-
Divya Nair and Mehrdad Nojoumian
-
Olga Miltchman and Shahab Mohsen
Friday, December 21:
|