Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

University of Melbourne

Modeling Discrete Optimization

University of Melbourne via Coursera

This course may be unavailable.

Overview

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. View the MOOC promotional video here: http://tinyurl.com/huyhq2e

*Important note*

This course will close for new learner enrollment on May 15, 2017 PST; it will be replaced by the Basic and Advanced Modeling for Discrete Optimization courses: https://tinyurl.com/lr87ctn

These two courses tackle the same modeling curriculum as MDO, but use a unique pedagogy (fable-based learning) where all the problems addressed are situated in a story, in this case, the “Romance of the Three - a famous Chinese fable. The revamped material is available in English and Chinese, and the workshops and assignments are all different. The pacing of the courses is slower than MDO, with a more gradual increase in difficulty of assignments, and updated to the latest MiniZinc language features. We hope this will make the whole experience more streamlined and enjoyable.

Syllabus

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.

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.

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.

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.

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.

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.

Taught by

Peter Stuckey and Carleton Coffrin

Reviews

3.8 rating, based on 6 Class Central reviews

Start your review of Modeling Discrete Optimization

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.