DM841 (E21) - 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
35 Sep 1 Course Organization, Motivations, Discrete Optimization Compendium
35 Sep 2 Constraint Programming by Example
35 Sep 3 Constraint Programming Languages and MiniZinc [SMT] chp. 1 [GM] chp. 12
36 Sep 8 MiniZinc [SMT] chp. 2
36 Sep 9 MiniZinc [SMT] chp. 2
37 Sep 16 Global Constraints in MiniZinc [SMT] chp. 2, sec 2.3; [HK] sc 7.1-7.2
37 Sep 17 Global Constraints in MiniZinc [SMT] sc 2.3, [HK] sc 7.1-7.2 Assignment 1
38 Sep 23 CSP Solving
38 Sep 24 Constraint Satisfaction Model and Notions of Local Consistency [S], [B], [BA]
39 Sep 29 Constraint Propagation Algorithms for AC [B], [SC]
39 Oct 1 Further Notions of Local Consistency [B]
40 Oct 6 Rule Iterations [B], [SC] Assignment 2; Template
40 Oct 8 Filtering Algorithms for Global Constraints [HK], [Hoo ch 3]
41 Oct 13 Filtering Algorithms for Scheduling Constraints [Hoo, sc. 3.13.1, 3.13.2; 3.14.1]
41 Oct 14 Search and Random Restarts [Be, ch 4] Assignment 3; Template
41 Oct 15 Search [Be, ch 4]
43 Oct 27 Random Restarts [SMT, 2.5.4]
43 Oct 28 Set Variables [SMT 2.2.6]
44 Nov 3 Symmetry Breaking [GPP], [MPG, sc 2.6.6]
44 Nov 4 Satisfiability, SAT solving SAT-Solving [BHM, ch 1, 2, 3, 5.3]
44 Nov 5 Conflict-Driven Clause Learning [BHM, ch 4]
45 Nov 10 Minimal Unsatisfiable Sets, Local Search [BHM, ch 6]
45 Nov 11 Local Search Theory [MAK, sc 1, 2.1, 4.1]
45 Nov 12 Exercises: LS for SAT
46 Nov 17 Local Search Based Metaheuristics [MAK, ch 7], [BHM, ch 6]
46 Nov 18 Implementations [BMFP], [DS] EasyLocal
46 Nov 19 Working Set Up Assignment 4
47 Nov 24 Local Search for TSP [Be], [No]
47 Nov 25 Construction Heuristics for TSP [Be]
48 Dec 2 More on Local Search [MAK]
48 Dec 2 Construction Heuristic Based Metaheuristics [BTW]
48 Dec 3 Population Based Metaheuristics: Ant Colony [GP, ch 10] [DS, ch 2] [D]
48 Dec 3 Population Based Metaheuristics: Evolutionary Algorithms [GP, ch 8,9] [R] [H]
49 Dec 9 Experimental Analysis [GP, ch 18]
49 Dec 10 Algorithm Configuration and Selection [GP, ch 17] [HHL], [LDC], [iR]
50 Dec 16 Very Large-Scale Neighborhoods [AEOP], [GP, ch 4] [LK],[KL],[CPV]
50 Dec 17 Adaptive Large Neighborhood Search [GP, ch 4] Assignment 5; Template

Exercises

Week Date Notes and Assignments Solutions
36 Sep 15 Sheet 1 solutions
38 Sep 22 Sheet 2 solutions
39 Sep 30 Sheet 3 solutions
40 Oct 7 Sheet 4 solutions
47 Nov 25 Sheet 5
48 Dec 1 Sheet 6

Resources

Reading Material

No textbook is required. Excerpts from the following books will be used.

Main books
Other References

Online Courses

Associations and Conferences

Libraries

Recreative Material