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

General information

Schedule

Contents

Introductory Classes

Week Date Topic and Slides Recommended Reading Additional Reading
20 May 15 Course Presentation poster
36 Sep 4 Course Organization, Motivations, Discrete Optimization Compendium
36 Sep 5 Constraint Programming by Example
36 Sep 7 Constraint Programming Languages and MiniZinc [SMT] chp. 1 [W] chp. 1-3, [GM] chp. 12
37 Sep 11 MiniZinc [SMT] chp. 2
37 Sep 12 MiniZinc [SMT] chp. 2 Stable Marriage
37 Sep 14 Exercise Sheet 1 Solutions [W] chp. 4-10
38 Sep 18 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 21 Exercise Sheet 2 Solutions
39 Sep 25 Constraint Satisfaction Model and Notions of Local Consistency [S], [B], [Ba] CP Overview
39 Sep 26 Constraint Propagation Algorithms for AC [B], [SC]
39 Sep 28 Exercise Sheet 3 Solutions, [Ba], [N] Assignment 1; Template
40 Oct 5 Optimization at ForeFlight (Rasmus Adeltoft)
41 Oct 9 Further Notions of Local Consistency [B]
41 Oct 10 Rule Iterations [B], [SC], [MSV]
41 Oct 12 Exercise Sheet 4 Solutions Comments to Assignment 1
42 Oct 18 Assignment 2; Template
43 Oct 23 Filtering Algorithms for Global Constraints [HK 7.3-7.5]
43 Oct 24 Filtering Algorithms for Scheduling Constraints [Hoo, 3.13.1, 3.13.2; 3.14.1]
43 Oct 26 Search and Random Restarts [Be, ch 4], [SMT, 2.6] Deadline Assignment 2
44 Oct 30 Set Variables [SMT 2.2.8] Solutions Asg 2
44 Nov 1 Symmetry Breaking Assignment 3; Template
44 Nov 2 Satisfiability and SAT solving Sheet 5 [BHM, ch 3] [BHM, ch 1, 2, 3]; SAT-Solving
45 Nov 6 Satisfiability and SAT solving
45 Nov 7 Conflict-Driven Clause Learning [BHM, ch 4, 5.3]
45 Nov 9 Local Search for SAT [BHM, ch 6]
46 Nov 13 Local Search Theory [MAK, sc 1, 2.1, 4.1]
46 Nov 14 Local Search Based Metaheuristics [MAK, ch 7], [BHM, ch 6]
46 Nov 16 Exercise Sheet 6
47 Nov 20 Construction Heuristic Based Metaheuristics [BTW] Assignment 4
47 Nov 21 Adaptive Large Neighborhood Search [GP, ch 4], [BPLL]
47 Nov 23 Software Tools [BMFP], [DS] EasyLocal
48 Nov 27 Development tools + Set Up
48 Nov 28 Cancelled
48 Nov 30 Cancelled
49 Dec 4 Experimental Analysis Part 1 [GP, ch 18], [LBP]
49 Dec 5 Experimental Analysis Part 2
49 Dec 7 More on Local Search [MAK]
50 Dec 11 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] [E] [NSGA]
50 Dec 14 Algorithm Selection and Algorithm Portfolios (Jacopo Mauro) [K] [GP, ch 17], [HHL], [LDC], [iR]
51 Dec 18 Construction Heuristics for TSP [Be], [No], Sheet 7 Assignment 5
51 Dec 19 Local Search for TSP [Be] Sheet 8
51 Dec 20 Very Large-Scale Neighborhoods [AEOP], [GP, ch 4] [LK],[KL],[CPV]

Resources

Books

Excerpts from the following books will be used.

Other References

To be updated during the course.

MOOC Courses

Associations and Conferences

Evaluation

  • Ordinary exam: During the course there will be mandatory assignments. The final grade will be given by a weighted average of the grades received in the third and fifth assignments.

  • Re-exam: it consists of two assignments equivalent in size to the multiple assignments during the course.