• For Individuals
  • For Businesses
  • For Universities
  • For Governments
Coursera
Online Degrees
Careers
Log In
Join for Free
Coursera
The University of Melbourne
Discrete Optimization
  • About
  • Modules
  • Recommendations
  • Testimonials
  • Reviews
  1. Browse
  2. Computer Science
  3. Algorithms
The University of Melbourne

Discrete Optimization

Professor Pascal Van Hentenryck
Dr. Carleton Coffrin

Instructors: Professor Pascal Van Hentenryck

Instructors

Instructor ratings

We asked all learners to give feedback on our instructors based on the quality of their teaching style.

4.8 (167 ratings)
Professor Pascal Van Hentenryck
Professor Pascal Van Hentenryck
The University of Melbourne
1 Course•76,258 learners
Dr. Carleton Coffrin
Dr. Carleton Coffrin
The University of Melbourne
2 Courses•78,050 learners

76,258 already enrolled

Included with Coursera Plus

•Learn more
8 modules
Gain insight into a topic and learn the fundamentals.
4.8

(777 reviews)

Intermediate level
Some related experience required
Flexible schedule
7 weeks at 10 hours a week
Learn at your own pace
95%
Most learners liked this course

8 modules
Gain insight into a topic and learn the fundamentals.
4.8

(777 reviews)

Intermediate level
Some related experience required
Flexible schedule
7 weeks at 10 hours a week
Learn at your own pace
95%
Most learners liked this course
  • About
  • Modules
  • Recommendations
  • Testimonials
  • Reviews

Skills you'll gain

  • Computational Logic
  • Mathematical Modeling
  • Computer Programming
  • Combinatorics
  • Operations Research
  • Applied Mathematics
  • Computational Thinking
  • Linear Algebra
  • Algorithms
  • Graph Theory

Details to know

Shareable certificate

Add to your LinkedIn profile

Taught in English

See how employees at top companies are mastering in-demand skills

Learn more about Coursera for Business
 logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

There are 8 modules in this course

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming.

Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.

These lectures and readings give you an introduction to this course: its philosophy, organization, and load. They also tell you how the assignments are a significant part of the class. This week covers the common input/output organization of the assignments, how they are graded, and how to succeed in this class.

What's included

4 videos2 readings1 programming assignment

4 videos•Total 42 minutes
  • Course Promo•1 minute•Preview module
  • Course Motivation - Indiana Jones, challenges, applications•20 minutes
  • Course Introduction - philosophy, design, grading rubric•11 minutes
  • Assignments Introduction & Any Integer•9 minutes
2 readings•Total 20 minutes
  • Start of Course Survey•10 minutes
  • Course Syllabus•10 minutes
1 programming assignment•Total 60 minutes
  • Any Integer•60 minutes

These lectures introduce optimization problems and some optimization techniques through the knapsack problem, one of the most well-known problem in the field. It discusses how to formalize and model optimization problems using knapsack as an example. It then reviews how to apply dynamic programming and branch and bound to the knapsack problem, providing intuition behind these two fundamental optimization techniques. The concept of relaxation and search are also discussed.

What's included

9 videos1 programming assignment

9 videos•Total 100 minutes
  • Knapsack 1 - intuition•2 minutes•Preview module
  • Knapsack 2 - greedy algorithms•7 minutes
  • Knapsack 3 - modeling•8 minutes
  • Knapsack 4 - dynamic programming•17 minutes
  • Knapsack 5 - relaxation, branch and bound•14 minutes
  • Knapsack 6 - search strategies, depth first, best first, least discrepancy•14 minutes
  • Assignments Getting Started•13 minutes
  • Knapsack & External Solver•10 minutes
  • Exploring the Material - open course design, optimization landscape, picking your adventure•10 minutes
1 programming assignment•Total 300 minutes
  • Knapsack•300 minutes

Constraint programming is an optimization technique that emerged from the field of artificial intelligence. It is characterized by two key ideas: To express the optimization problem at a high level to reveal its structure and to use constraints to reduce the search space by removing, from the variable domains, values that cannot appear in solutions. These lectures cover constraint programming in detail, describing the language of constraint programming, its underlying computational paradigm and how it can be applied in practice.

What's included

13 videos1 reading2 programming assignments

13 videos•Total 247 minutes
  • CP 1 - intuition, computational paradigm, map coloring, n-queens•27 minutes•Preview module
  • CP 2 - propagation, arithmetic constraints, send+more=money•26 minutes
  • CP 3 - reification, element constraint, magic series, stable marriage•16 minutes
  • CP 4 - global constraint intuition, table constraint, sudoku•19 minutes
  • CP 5 - symmetry breaking, BIBD, scene allocation•18 minutes
  • CP 6 - redundant constraints, magic series, market split•11 minutes
  • CP 7 - car sequencing, dual modeling•18 minutes
  • CP 8 - global constraints in detail, knapsack, alldifferent•33 minutes
  • CP 9 - search, first-fail, euler knight, ESDD•25 minutes
  • CP 10 - value/variable labeling, domain splitting, symmetry breaking in search•28 minutes
  • Graph Coloring•6 minutes
  • Optimization Tools•5 minutes
  • Set Cover•8 minutes
1 reading•Total 10 minutes
  • Optimization Tools•10 minutes
2 programming assignments•Total 780 minutes
  • Set Cover•180 minutes
  • Graph Coloring•600 minutes

Local search is probably the oldest and most intuitive optimization technique. It consists in starting from a solution and improving it by performing (typically) local perturbations (often called moves). Local search has evolved substantially in the last decades with a lot of attention being devoted on which moves to explore. These lectures explore the theory and practice of local search, from the concept of neighborhood and connectivity to meta-heuristics such as tabu search and simulated annealing.

What's included

10 videos1 programming assignment

10 videos•Total 191 minutes
  • LS 1 - intuition, n-queens•13 minutes•Preview module
  • LS 2 - swap neighborhood, car sequencing, magic square•15 minutes
  • LS 3 - optimization, warehouse location, traveling salesman, 2-opt, k-opt•23 minutes
  • LS 4 - optimality vs feasibility, graph coloring•22 minutes
  • LS 5 - complex neighborhoods, sports scheduling•21 minutes
  • LS 6 - escaping local minima, connectivity•15 minutes
  • LS 7 - formalization, heuristics, meta-heuristics introduction•22 minutes
  • LS 8 - iterated location search, metropolis heuristic, simulated annealing, tabu search intuition•18 minutes
  • LS 9 - tabu search formalized, aspiration, car sequencing, n-queens•26 minutes
  • Traveling Salesman•10 minutes
1 programming assignment•Total 600 minutes
  • Traveling Salesman•600 minutes

Linear programming has been, and remains, a workhorse of optimization. It consists in optimizing a linear objective subject to linear constraints, admits efficient algorithmic solutions, and is often an important building block for other optimization techniques. These lectures review fundamental concepts in linear programming, including the infamous simplex algorithm, simplex tableau, and duality. .

What's included

6 videos

6 videos•Total 129 minutes
  • LP 1 - intuition, convexity, geometric view•23 minutes•Preview module
  • LP 2 - algebraic view, naive algorithm•13 minutes
  • LP 3 - the simplex algorithm•32 minutes
  • LP 4 - matrix notation, the tableau•20 minutes
  • LP 5 - duality derivation•22 minutes
  • LP 6 - duality interpretation and uses•17 minutes

Mixed Integer Programming generalizes linear programming by allowing integer variables, which dramatically changes the complexity of the problems but also broadens the potential applications significantly. These lectures review how to model problems in mixed-integer programming and how to solve mixed-integer programs using branch and bound. Advanced techniques such as cutting planes and polyhedral cuts are also covered.

What's included

6 videos1 programming assignment

6 videos•Total 135 minutes
  • MIP 1 - intuition, relaxation, branch and bound, knapsack, warehouse location•26 minutes•Preview module
  • MIP 2 - modeling, big-M, warehouse location, graph coloring•28 minutes
  • MIP 3 - cutting planes, Gomory cuts•20 minutes
  • MIP 4 - convex hull, polyhedral cuts, warehouse location, node packing, graph coloring•19 minutes
  • MIP 5 - cover cuts, branch and cut, seven bridges, traveling salesman•31 minutes
  • Facility Location•9 minutes
1 programming assignment•Total 600 minutes
  • Facility Location•600 minutes

These lectures cover some more advanced concepts in optimization. They introduce constraint-programming techniques for scheduling and routing.

What's included

2 videos1 programming assignment

2 videos•Total 51 minutes
  • Scheduling - jobshop, disjunctive global constraint•37 minutes•Preview module
  • Vehicle Routing•14 minutes
1 programming assignment•Total 600 minutes
  • Vehicle Routing•600 minutes

These lectures continues to cover some more advanced concepts in optimization. They introduce large neighborhood search, which often combines constraint programming and local search, and column generation which decomposes an optimization model into a master and pricing problem, using more complex variables.

What's included

2 videos1 reading

2 videos•Total 31 minutes
  • Large Neighborhood Search - asymmetric TSP with time windows•8 minutes•Preview module
  • Column Generation - branch and price, cutting stock•23 minutes
1 reading•Total 10 minutes
  • End of course survey•10 minutes

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.

Instructors

Instructor ratings

Instructor ratings

We asked all learners to give feedback on our instructors based on the quality of their teaching style.

4.8 (167 ratings)
Professor Pascal Van Hentenryck
Professor Pascal Van Hentenryck
The University of Melbourne
1 Course•76,258 learners
Dr. Carleton Coffrin
Dr. Carleton Coffrin
The University of Melbourne
2 Courses•78,050 learners

Offered by

The University of Melbourne

Offered by

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.

Explore more from Algorithms

  • T

    The Chinese University of Hong Kong

    Solving Algorithms for Discrete Optimization

    Course

  • T

    The Chinese University of Hong Kong

    Advanced Modeling for Discrete Optimization

    Course

  • T

    The Chinese University of Hong Kong

    Basic Modeling for Discrete Optimization

    Course

  • N

    National Taiwan University

    Operations Research (2): Optimization Algorithms

    Course

Why people choose Coursera for their career

Felipe M.
Learner since 2018
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

4.8

777 reviews

  • 5 stars

    89.57%

  • 4 stars

    7.72%

  • 3 stars

    1.15%

  • 2 stars

    0.12%

  • 1 star

    1.41%

Showing 3 of 777

M
MG
5

Reviewed on May 6, 2024

To achieve success in this course, you will need college math up to and including Linear Algebra and 3 to 6 months of Python coding experience. This is nearly a graduate school level course.

S
SK
5

Reviewed on May 29, 2019

Exceptional coverage of optimization fundamentals. Learning of practical applied methods. Real university level course, no water down "data science". Absolutely love it! Thank you professor Pascal.

G
GD
5

Reviewed on May 1, 2019

I just completed the course. This an amazing course with an Outstanding professor and highly interesting, although difficult, assignments. Thanks for this! I am proud to have finished

View more reviews
Coursera Plus

Open new doors with Coursera Plus

Unlimited access to 10,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Learn more

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Explore degrees

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Learn more

Frequently asked questions

Good programming skills, knowledge of algorithms and linear algebra.

A minimal knowledge of python is necessary to integrate with the course infrastructure. Outside of that, students are free to use any language of their choice.

A motivated student spending the time on the programming assignment will succeed in this class.

At the discrete optimization store: http://www.zazzle.com.au/discreteoptimization

Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:

  • The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.

  • The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.

When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

You will be eligible for a full refund until two weeks after your payment date, or (for courses that have just launched) until two weeks after the first session of the course begins, whichever is later. You cannot receive a refund once you’ve earned a Course Certificate, even if you complete the course within the two-week refund period. See our full refund policyOpens in a new tab.

Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.

More questions

Visit the learner help center

Financial aid available,

Coursera Footer

Technical Skills

  • ChatGPT
  • Coding
  • Computer Science
  • Cybersecurity
  • DevOps
  • Ethical Hacking
  • Generative AI
  • Java Programming
  • Python
  • Web Development

Analytical Skills

  • Artificial Intelligence
  • Big Data
  • Business Analysis
  • Data Analytics
  • Data Science
  • Financial Modeling
  • Machine Learning
  • Microsoft Excel
  • Microsoft Power BI
  • SQL

Business Skills

  • Accounting
  • Digital Marketing
  • E-commerce
  • Finance
  • Google
  • Graphic Design
  • IBM
  • Marketing
  • Project Management
  • Social Media Marketing

Career Resources

  • Essential IT Certifications
  • High-Income Skills to Learn
  • How to Get a PMP Certification
  • How to Learn Artificial Intelligence
  • Popular Cybersecurity Certifications
  • Popular Data Analytics Certifications
  • What Does a Data Analyst Do?
  • Career Development Resources
  • Career Aptitude Test
  • Share your Coursera Learning Story

Coursera

  • About
  • What We Offer
  • Leadership
  • Careers
  • Catalog
  • Coursera Plus
  • Professional Certificates
  • MasterTrack® Certificates
  • Degrees
  • For Enterprise
  • For Government
  • For Campus
  • Become a Partner
  • Social Impact
  • Free Courses
  • ECTS Credit Recommendations

Community

  • Learners
  • Partners
  • Beta Testers
  • Blog
  • The Coursera Podcast
  • Tech Blog

More

  • Press
  • Investors
  • Terms
  • Privacy
  • Help
  • Accessibility
  • Contact
  • Articles
  • Directory
  • Affiliates
  • Modern Slavery Statement
  • Do Not Sell/Share
Learn Anywhere
Download on the App Store
Get it on Google Play
Logo of Certified B Corporation
© 2025 Coursera Inc. All rights reserved.
  • Coursera Facebook
  • Coursera Linkedin
  • Coursera Twitter
  • Coursera YouTube
  • Coursera Instagram
  • Coursera TikTok
Coursera

Welcome back

​
Your password is hidden
​

or

New to Coursera?


Having trouble logging in? Learner help center

This site is protected by reCAPTCHA Enterprise and the Google Privacy Policy and Terms of Service apply.