About this course: Optimization is a common form of decision making, and is ubiquitous in our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions in manpower and material resources management also allow corporations to improve 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, all of these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Basic Modelling for Discrete Optimization. In this course you will learn much more about solving challenging discrete optimization problems by stating the problem in a state-of-the-art high level modeling language, and letting library constraint solving software do the rest. This course will focus on debugging and improving models, encapsulating parts of models in predicates, and tackling advanced scheduling and packing problems. As you master this advanced technology, you will be able to tackle problems that were inconceivable to solve previously. Watch the course promotional video here: https://www.youtube.com/watch?v=hc3cBvtrem0&t=8s
Who is this class for: The course is for penultimate/final year undergraduates and graduates in computing and related disciplines. You will need to have basic computer programming skills, and knowledge of fundamental algorithms, discrete mathematics, logic and linear algebra in order to take this course. Please note, this course is also available wholly in Chinese, see: https://www.coursera.org/learn/lisan-youhua-jianmo-gaojiepian
Created by: The University of Melbourne, The Chinese University of Hong Kong
Taught by: Prof. Jimmy Ho Man Lee, Professor
Department of Computer Science and Engineering
Taught by: Prof. Peter James Stuckey, Professor
Computing and Information Systems
| Level | Intermediate |
| Commitment | 5 weeks of study, 6-12 hours/week |
| Language | English |
| How To Pass | Pass all graded assignments to complete the course. |
| User Ratings |
Syllabus
WEEK 1
Debugging and Improving Models
Similar to computer programs, models can have bugs. In this module, you will see the symptoms (unsatisfiability, too many solutions, too few solutions) of different bugs, and learn methods to discover what is going wrong with your model and how to fix it. Equipped with these tools, you will be able to develop and debug complex models.
22 videos, 5 readings
- Video: Welcome to Advanced Modeling for Discrete Optimization
- Reading: Course Overview
- Reading: Start of Course Survey
- Video: 2.1.1 Model Debugging
- Video: 2.1.2 Tracing Models
- Video: 2.1.3 Relational Semantics
- Video: 2.1.4 Too Many Solutions
- Video: 2.1.5 Missing Solutions
- Video: 2.1.6 Basic Model Improvement
- Video: 2.1.7 Module 1 Summary
- Reading: Getting MiniZinc
- Reading: Workshop 5: Poetry Challenge
- Video: Workshop 5 Solution
- Video: Assignment Submission - IDE
- Video: Assignment Submission - CLI
- Reading: About the Reference Material
- Video: Reference 1: Basic Features
- Video: Reference 2: Booleans Expressions
- Video: Reference 3: Sets, Arrays and Comprehensions
- Video: Reference 4: Enumerated Types
- Video: Reference 5: Strings and Output
- Video: Reference 6: Option Types
- Video: Reference 7: Predicates
- Video: Reference 8: Flattening
- Video: Reference 9: Transforming Data
- Video: Reference 10: User Defined Functions
- Video: Reference 11: Command Line Interface
Graded: Escape to Jing Province
WEEK 2
Predicates
In this module, 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 with improved readability in a modular manner. You will also encounter for the first time a problem with multiple objectives and learn how to compress them into one single objective. In addition to this, you will learn how to model the banquet seating problem, which will assist you in many occasions in life.
6 videos, 1 reading
- Video: 2.2.1 Predicates
- Video: 2.2.2 The let-in Construct
- Video: 2.2.3 Using Predicates
- Video: 2.2.4 Contexts
- Video: 2.2.5 Module 2 Summary
- Reading: Workshop 6: Weighing an Elephant: Part 1
- Video: Workshop 6 Solution
Graded: Weighing the Elephant
WEEK 3
Scheduling
Learn how to tackle complex project scheduling problems of various forms, progressively from ones with only basic precedence requirements to ones with unary resources and even cumulative resources. You will see how to model some of the complex constraints that arise in these applications.
7 videos, 1 reading
- Video: 2.3.1 Basic Scheduling
- Video: 2.3.2 Disjunctive Scheduling
- Video: 2.3.3 Cumulative Scheduling
- Video: 2.3.4 Sequence Dependent Scheduling 1
- Video: 2.3.5 Sequence Dependent Scheduling 2
- Video: 2.3.6 Module 3 Summary
- Reading: Workshop 7: Visiting Zhuge Liang
- Video: Workshop 7 Solution
Graded: Suitor Schedule
WEEK 4
Packing
In this module, you will learn the important application of packing, from the packing of squares to rectilinear shapes with and without rotation. Again, you will see how to model some of the complex constraints that arise in these applications.
3 videos
- Video: 2.4.1 Square Packing
- Video: 2.4.2 Rectilinear Packing without Rotation
- Video: 2.4.3 Rectilinear Packing with Rotation
WEEK 5
Symmetry and Dominance
This final module looks at the various forms of symmetries that can appear in discrete optimization problems. You will learn various methods and special constraints to break such symmetries so as to increase solving efficiency. You will also learn the notion of dominance, which is a generalization of symmetries, and also dominance breaking techniques.
6 videos, 3 readings
- Video: 2.5.1 Symmetries and LexLeader
- Video: 2.5.2 Matrix Model Symmetries
- Video: 2.5.3 Value Symmetries
- Video: 2.5.4 Dominance
- Video: 2.5.5 Module 4 & 5 Summary
- Reading: Where to from here?
- Reading: Workshop 8: The Dieda Plasters
- Video: Workshop 8 Solution
- Reading: End of Course Survey
Graded: To Borrow Arrows from Thatched Boats
FAQs
How It Works
Coursework
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from Your Peers
Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
Certificates
Earn official recognition for your work, and share your success with friends, colleagues, and employers.
Creators
The University of Melbourne
The University of Melbourne is an internationally recognised research intensive University with a strong tradition of excellence in teaching, research, and community engagement. Established in 1853, it is Australia's second oldest University.
The Chinese University of Hong Kong
Founded in 1963, The Chinese University of Hong Kong (CUHK) is a forward looking comprehensive research university with a global vision and a mission to combine tradition with modernity, and to bring together China and the West. CUHK teachers and students hail from all corners of the world. CUHK graduates are connected worldwide through an expansive alumni network.
Ratings and Reviews
Looking forward to course 3!
Excellent course with very supportive staff and professors on the forum. On top of that aligning the assignments to "The Romance of Three Kingdoms" story makes it fun to follow along.
Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.
© 2017 Coursera Inc. All rights reserved.
Advanced Modeling for Discrete Optimization is an Excellent course, very challenging and satisfying at the same time; I will highly recommend this course to anyone that is serious about Discrete Optimization.
I will also to extend my thanks to Prof. Jimmy Ho-Man Lee and Prof. Peter James Stuckey for putting together this astounding course and the staff that work in this exceptional narrative to explain the concepts.
Thanks.