CO327 Deterministic OR Models 2021-spring

I update this page often. Refresh / clear your browser memory / use incognito mode to avoid your browser showing the old version of page

Lastest update: 21-Aug (will not update anymore for the 2021-Spring semester)

• 0. Course info (grades, assignments, etc.), Outline (UWaterloo), Tutorial 0,

• 1. Introduction to Linear programming, Tutorial 1, Assignment 1 (deadline May-27 11:55 am)

• 2. Introduction to Integer programming, Tutorial 2, Assignment 2 (deadline June-1 11:25 am), Set covering and urban planning

• 3. Introduction to other programs

  • Airport traffic control, composite max-min program and the extreme-case modelling trick

  • Auction, Introduction to Conic optimisation

  • Electric grid network, Introduction to Polynomial program

  • MAXCUT, Introduction to Quadratic program and semidefinite program

  • \(p\)-median problem, Introduction to Mixed Integer program

  • Assignment 3 (deadline June-21 23:55)

• 4. How to solve: Computer program

  • How to solve LP and IP

  • MATLAB program

  • \(\ell_p\) norms

  • Assignment 4 (deadline June-30 23:55)

• Mid-term on Lecture material 1,2,3,4, solution

• 5. Applications in data science

  • Be a image processing engineer: Image inpainting

  • Be a statistician: piecewise linear function and robust curve fitting

  • About scribing and \(\LaTeX\), LaTeX simple example source code, LaTeX advanced example source code

  • Assignment 5 (deadline July-31 23:55), Data files, solution

• 6. Theory (No notes, scribing, submission deadline August 16 )

  • Linear, Conic and Convex combination

  • Hyperplane and Halfspace

  • Polyhedron and convex set

  • Polyhedron of LP feasible set

  • Interior and Boundary

  • Fundamental theorem of LP

  • \(\mathbf{A}\) is usually singular in LP

  • Active and Passive constraints

  • \(\mathbf{c} \in \)cone spanned by active rows of \(\mathbf{A}\) at an optimal point

  • Sensitivity of LP with perturbation on \(\mathbf{b}\)

  • Sensitivity analysis example and introduction to complementary slackness

  • Weak Duality and its implications

  • Unimodular Matrix and the Fundamental Theorem of LP relaxation

  • Example

• 7. Other applications

  • Be an economist: 2-player zero-sum game

  • Be a logistic engineer: Optimal transport and resource allocation, Example

  • Be a data scientist: Modern optimal transport in machine learning

  • Graph models

  • Be an industrial engineer: Production scheduling and Optimal control

  • Be a puzzle solver: Sudoku and more

  • Be a logician: logic puzzles

  • About project

• Final (deadline Aug 16 23:55 EDT)

• Other stuffs

  • The Better Boarding Method Airlines Won't Use

Calendar

Assignments

• Assignment 1, Solution

• Assignment 2, Solution

• Assignment 3, Solution

• Assignment 4, Solution

• Mid-term take home exam, Solution

• Assignment 5, Data files, Solution

• Scribe note

• Final, Solution

A list of mathematics models we have seen in CO327

• Dieting

• Job assignment

• Profit maximisation in manufacture

• Transportation planning

• Employee worksheet

• Traveling salesman

• Tower defence

• Knapsack

• Purchase policy making

• Resource allocation

• Set cover

• Facility location and urban planning

• Airport traffic control

• Networkless electricity economic model

• Pari–mutuel auction

• MAXCUT

• p-median problem

• L-1,L-2,L-infinity norm minimisation

• Image inpainting

• Robust curve fitting

• Change point detection

• Capacitated p-median and p-center problem

• Project management: activity scheduling

• Stable marriage matching problem

• Minesweeper

• Constraint Satisfaction Problem

• Two-person Zero-sum Game

• Optimal transport and resource allocation