DM841 (E22) - Heuristics and Constraint Programming for
Discrete Optimization

General information

Schedule

Contents

Introductory Classes

Week Date Topic and Slides Recommended Reading Additional Reading
20 May 17 Course Presentation poster
35 Sep 1 Course Organization, Motivations, Discrete Optimization
36 Sep 5 Constraint Programming by Example Compendium
36 Sep 6 Constraint Programming Languages and MiniZinc [SMT] chp. 1 [GM] chp. 12
36 Sep 7 MiniZinc [SMT] chp. 2
37 Sep 12 MiniZinc [SMT] chp. 2
37 Sep 13 Exercise Sheet 1 Solutions
37 Sep 14 Global Constraints in MiniZinc [SMT] chp. 2, sec 2.3;
[HK] sc 7.1-7.2
38 Sep 19 Global Constraints in MiniZinc [SMT] sc 2.3, [HK] sc 7.1-7.2
38 Sep 20 Exercise Sheet 2 Solutions
38 Sep 21 CSP Solving Assignment 1
39 Sep 26 Constraint Satisfaction Model and Notions of Local Consistency [S], [B], [Ba]
39 Sep 27 Constraint Propagation Algorithms for AC [B], [SC]
39 Sep 28 Exercise Sheet 3 Solutions
40 Oct 3 Exercise Sheet 3
40 Oct 4 Further Notions of Local Consistency [B]
40 Oct 5 Rule Iterations [B], [SC] Deadline Assignment 1
41 Oct 10 Exercise Sheet 4 Solutions Assignment 2; Template
41 Oct 11 Filtering Algorithms for Global Constraints [HK], [Hoo ch 3]
41 Oct 12 Filtering Algorithms for Scheduling Constraints [Hoo, 3.13.1, 3.13.2; 3.14.1]
43 Oct 24 Search and Random Restarts [Be, ch 4], [SMT, 2.5.4] Deadline Assignment 2
43 Oct 25 Search and Random Restarts Assignment 3; Template
44 Oct 31 Set Variables [SMT 2.2.6]
44 Nov 1 Symmetry Breaking [GPP], [MPG, sc 2.6.6]
44 Nov 2 Symmetry Breaking [GPP], [MPG, sc 2.6.6]
45 Nov 7 Satisfiability and SAT solving Sheet 5 [BHM, ch 1, 2, 3, 5.3]; SAT-Solving
45 Nov 8 Conflict-Driven Clause Learning [BHM, ch 4]
45 Nov 9 Local Search for SAT
46 Nov 14 Local Search Theory [MAK, sc 1, 2.1, 4.1]
46 Nov 15 Local Search Based Metaheuristics [MAK, ch 7], [BHM, ch 6] Assignment 4
46 Nov 17 Implementations [BMFP], [DS] EasyLocal
47 Nov 21 Working on Asg4 + Set Up
47 Nov 22 Experimental Analysis Part 1 Part 2, [GP, ch 18]
47 Nov 24 Algorithm Selection and Algorithm Portfolios (with Jacopo) [K] [GP, ch 17], [HHL], [LDC], [iR]
48 Nov 28 More on Local Search [MAK]
48 Nov 29 Construction Heuristics for TSP [Be], [No] Sheet 5
48 Dec 1 Local Search for TSP [Be] Sheet 6
49 Dec 5 Construction Heuristic Based Metaheuristics [BTW]
49 Dec 6 Adaptive Large Neighborhood Search [GP, ch 4]
49 Dec 8 Population Based Metaheuristics: Ant Colony [GP, ch 10] [DS, ch 2] [D]
50 Dec 12 Population Based Metaheuristics: Evolutionary Algorithms [GP, ch 8,9] [R] [H]
50 Dec 13 Very Large-Scale Neighborhoods [AEOP], [GP, ch 4] [LK],[KL],[CPV]; Deadline Assignment 4
50 Dec 15 Minimal Unsatisfiable Sets (Cancelled) [BHM, ch 6] Assignment 5, Results
51 Dec 19

Resources

Books

Excerpts from the following books will be used.

Other References

To be updated during the course.

Online Courses

Associations and Conferences