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.
Syllabus
WEEK 1
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.
WEEK 2
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.
WEEK 3
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.
WEEK 4
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.
WEEK 5
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.
WEEK 6
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.
WEEK 7
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.