Buy Now AED 170.99 + VAT

Monthly Subscription Starting at AED 99 + VAT

Discrete Optimization
  • Level Professional
  • Duration 65 hours
  • Course by The University of Melbourne
  • Offered by

About

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.

Modules

Welcome and Motivation

    • 2 Videos
    • 1 Readings
Show info about module content

2 Videos

  • Course Promo
  • Course Motivation - Indiana Jones, challenges, applications

1 Readings

  • Start of Course Survey

Preliminaries

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • Course Introduction - philosophy, design, grading rubric

1 Readings

  • Course Syllabus

Assignment

    • 1 Videos
    • 1 Programming
Show info about module content

1 Programming

  • Any Integer

1 Videos

  • Assignments Introduction & Any Integer

The Knapsack Problem

    • 6 Videos
Show info about module content

6 Videos

  • Knapsack 1 - intuition
  • Knapsack 2 - greedy algorithms
  • Knapsack 3 - modeling
  • Knapsack 4 - dynamic programming
  • Knapsack 5 - relaxation, branch and bound
  • Knapsack 6 - search strategies, depth first, best first, least discrepancy

Assignment

    • 2 Videos
    • 1 Programming
Show info about module content

1 Programming

  • Knapsack

2 Videos

  • Assignments Getting Started
  • Knapsack & External Solver

Next Steps

    • 1 Videos
Show info about module content

1 Videos

  • Exploring the Material - open course design, optimization landscape, picking your adventure

Constraint Programming

    • 10 Videos
Show info about module content

10 Videos

  • CP 1 - intuition, computational paradigm, map coloring, n-queens
  • CP 2 - propagation, arithmetic constraints, send+more=money
  • CP 3 - reification, element constraint, magic series, stable marriage
  • CP 4 - global constraint intuition, table constraint, sudoku
  • CP 5 - symmetry breaking, BIBD, scene allocation
  • CP 6 - redundant constraints, magic series, market split
  • CP 7 - car sequencing, dual modeling
  • CP 8 - global constraints in detail, knapsack, alldifferent
  • CP 9 - search, first-fail, euler knight, ESDD
  • CP 10 - value/variable labeling, domain splitting, symmetry breaking in search

Assignment

    • 1 Videos
    • 1 Programming
Show info about module content

1 Programming

  • Graph Coloring

1 Videos

  • Graph Coloring

Optimization Tools (optional)

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • Optimization Tools

1 Readings

  • Optimization Tools

Open Source Assignment (optional)

    • 1 Videos
    • 1 Programming
Show info about module content

1 Programming

  • Set Cover

1 Videos

  • Set Cover

Local Search

    • 9 Videos
Show info about module content

9 Videos

  • LS 1 - intuition, n-queens
  • LS 2 - swap neighborhood, car sequencing, magic square
  • LS 3 - optimization, warehouse location, traveling salesman, 2-opt, k-opt
  • LS 4 - optimality vs feasibility, graph coloring
  • LS 5 - complex neighborhoods, sports scheduling
  • LS 6 - escaping local minima, connectivity
  • LS 7 - formalization, heuristics, meta-heuristics introduction
  • LS 8 - iterated location search, metropolis heuristic, simulated annealing, tabu search intuition
  • LS 9 - tabu search formalized, aspiration, car sequencing, n-queens

Assignment

    • 1 Videos
    • 1 Programming
Show info about module content

1 Programming

  • Traveling Salesman

1 Videos

  • Traveling Salesman

Linear Programming

    • 6 Videos
Show info about module content

6 Videos

  • LP 1 - intuition, convexity, geometric view
  • LP 2 - algebraic view, naive algorithm
  • LP 3 - the simplex algorithm
  • LP 4 - matrix notation, the tableau
  • LP 5 - duality derivation
  • LP 6 - duality interpretation and uses

Mixed Integer Programming

    • 5 Videos
Show info about module content

5 Videos

  • MIP 1 - intuition, relaxation, branch and bound, knapsack, warehouse location
  • MIP 2 - modeling, big-M, warehouse location, graph coloring
  • MIP 3 - cutting planes, Gomory cuts
  • MIP 4 - convex hull, polyhedral cuts, warehouse location, node packing, graph coloring
  • MIP 5 - cover cuts, branch and cut, seven bridges, traveling salesman

Assignment

    • 1 Videos
    • 1 Programming
Show info about module content

1 Programming

  • Facility Location

1 Videos

  • Facility Location

Scheduling

    • 1 Videos
Show info about module content

1 Videos

  • Scheduling - jobshop, disjunctive global constraint

Assignment

    • 1 Videos
    • 1 Programming
Show info about module content

1 Programming

  • Vehicle Routing

1 Videos

  • Vehicle Routing

Decomposition Techniques

    • 2 Videos
    • 1 Readings
Show info about module content

2 Videos

  • Large Neighborhood Search - asymmetric TSP with time windows
  • Column Generation - branch and price, cutting stock

1 Readings

  • End of course survey

Auto Summary

Unlock the power of discrete optimization with this in-depth course designed for IT and Computer Science professionals. Offered by Coursera, this course dives into the core concepts and algorithms that solve complex search problems, such as constraint programming, local search, and mixed-integer programming. Discover how optimization technology impacts our everyday lives, from scheduling flights and coordinating steel production to managing electricity markets and facilitating medical treatments. This course provides a comprehensive introduction to discrete optimization, emphasizing practical applications in scheduling, vehicle routing, supply-chain optimization, and resource allocation. Ideal for professionals seeking to enhance their skills, this course spans a substantial 3900 minutes of engaging and informative content. With a Starter subscription, learners can access the material and advance their understanding of how optimization can solve real-world problems efficiently. Join now and transform your approach to complex search problems with the tools and techniques of discrete optimization.

Professor Pascal Van Hentenryck
Instructors

Professor Pascal Van Hentenryck

Dr. Carleton Coffrin
Instructors

Dr. Carleton Coffrin