Solving Algorithms for Discrete Optimization (Coursera)

Good decisions on the use of scarce or expensive resources such as staffing and material resources also allow corporations to improve their profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, these problems are a nightmare to solve using traditional undergraduate computer science methods.

This course is intended for students who have completed Advanced Modelling for Discrete Optimization. In this course, you will extend your understanding of how to solve challenging discrete optimization problems by learning more about the solving technologies that are used to solve them, and how a high-level model (written in MiniZinc) is transformed into a form that is executable by these underlying solvers. By better understanding the actual solving technology, you will both improve your modeling capabilities, and be able to choose the most appropriate solving technology to use.

Syllabus

Week 1

Basic Constraint Programming

This module starts by using an example to illustrate the basic machinery of Constraint Programming solvers, namely constraint propagation and search. While domains represent possibilities for variables, constraints are actively used to reason about domains and can be encoded as domain propagators and bounds propagators. You will learn how a propagation engine handles a set of propagators and coordinates the propagation of constraint information via variable domains. You will also learn basic search, variable and value choices, and how propagation and search can be combined in a seamless and efficient manner. Last but not least, this module describes how to program search in MiniZinc.

Week 2

Advanced Constraint Programming

In this module, you will see how Branch and Bound search can solve optimization problems and how search strategies become even more important in such situations. You will be exposed to advanced search strategies, including restart search and impact-based search. The module also uncovers the inner workings of such global constraints as all different and cumulative.

Week 3

Mixed Integer Programming

This module starts by introducing linear programming and the Simplex algorithm for solving continuous linear optimization problems, before showing how the method can be incorporated into Branch and Bound search for solving Mixed Integer Programs. Learn Gomory Cuts and the Branch and Cut method to see how they can speed up solving.

Week 4

Local Search

This module takes you into the exciting realm of local search methods, which allow for efficient exploration of some otherwise large and complex search space. You will learn the notion of states, moves and neighbourhoods, and how they are utilized in basic greedy search and steepest descent search in constrained search space. Learn various methods of escaping from and avoiding local minima, including restarts, simulated annealing, tabu lists and discrete Lagrange Multipliers. Last but not least, you will see how Large Neighbourhood Search treats finding the best neighbour in a large neighbourhood as a discrete optimization problem, which allows us to explore farther and search more efficiently.