Jan 30th 2017

Modeling Discrete Optimization (Coursera)

Created by:Delivered by:

Learn a new way to approach problem solving by stating the problem and letting powerful constraint solving software do the rest. This class teaches you the art of encoding complex discrete optimization problems in the MiniZinc modeling language and then shows you how to effortlessly solve them by leveraging state-of-the-art open-source constraint solving software.

Who is this class for: This course is primarily aimed at third- and fourth-year undergraduates interested in Artificial Intelligence, Computer Science, and Mathematics. Students are expected to have basic programming skills and a general comfort with mathematics. Knowledge of fundamental computer algorithms is helpful for following some of the optional course content.



Taming the Dragon, First Steps in MiniZinc

In this first module, you will learn the basics of MiniZinc, a high-level modeling language for discrete optimization problems. Combining the simplicity of MiniZinc with the power of open-source industrial solving technologies, you will learn how to solve tricky Cryptarithm puzzles with great ease.

Graded: Workshop: First Steps Solution

Graded: Workshop: Simple Puzzles Solution

Graded: Cryptarithm


Core Decisions

In this module you will examine some of the archetypal forms of decisions that need to be made in discrete optimization problems and how to represent them in MiniZinc. After this module Sudoku problems will never bother you again.

Graded: Workshop: Temperature Solution

Graded: Workshop: Group Photo Solution

Graded: Workshop: Team Again Solution

Graded: Latin Killer


Multiple Perspectives

In this module you will see how discrete optimization problems can often be seen from multiple viewpoints, and modelled completely differently from each viewpoint. Each viewpoint may have strengths and weaknesses, and indeed the different models can be combined to help each other. You will learn more about converting data into complex constraints or objectives to define a problem. The assignment will challenge you far more than earlier problems.

Graded: Workshop: Composition Solution

Graded: Gang Warfare


The Power of Predicates

You will learn how to encapsulate a complex constraint definition in a predicate definition to enable its reuse. This will enable the construction of far more complex models. You will learn methods to discover what is going wrong with your model and how to fix it. With these tools a complex plannning problem will be easy to solve.

Graded: Workshop: Lineup Solution

Graded: Workshop: Wumpus Solution

Graded: Fox Geese Corn


Challenging Applications

You will learn how to tackle challenging scheduling and packing problems, and the important combinatorial substructures that underly them. You will see how to model some of the complex constraints that arise in these applications. The assignment will tackle a simplification of a real world combined scheduling and packing problem.

Graded: Workshop: Pack Bend Solution

Graded: Port Scheduling


Other Topics (optional)

In this optional module you will get more insight into the type system of MiniZinc and how MiniZinc models are transformed to a form suitable for solving. Option types are used by MiniZinc to allow flexible specification of loops, and you may have experienced confusing error messages involving them, this will be much clearer after this module. Flattening explains how MiniZinc models are translated to solvers, giving you more insight into why some models are more efficient than others.


Under the Hood (optional)

This optional module gives insight into how the solvers used by MiniZinc actually work. With greater understanding of the solvers you can create more efficient models. Constraint programming (CP) solvers, like Gecode, also allow search to be programmed in the MiniZinc model, and this can make solving far more efficient. Mixed Integer Programming (MIP) solvers can handle many discrete optimization problems far more effectively than CP solvers, but they have a preference for linear constraints.