IE 310 Deterministic Models in Optimization

Undergraduate Course, University of Illinois Urbana Champaign, 2022

Syllabus

Overview

  • Pre-requisites: Mathematical maturity at the level of a junior undergraduate student will be assumed. Prior coursework in Linear Algebra, Calculus and familiarity with Matrices is required.
  • The course will introduce fundamental topics in optimization at the undergraduate level. Some specific topics to be covered are: Formulations, Linear Programming, Simplex Method, Duality, Sensitivity Analysis, Transportation, Assignment Problems, Network Optimization Problems, Integer Programs, Nonlinear Optimization, and Game Theory.
  • Instructor: Zikun Ye (zikunye2 at illinois dot edu)
  • Lectures: Mon, Wed, Fri, 1:00-1:50pm, 2035 Campus Instructional Facility
  • Office Hour: Fri, 4:00-5:00pm, 13 Transportation Building
  • Credit Hours: 3 Hours
  • Teaching Assistants:
    • Kangcheng Lin (klin14 at illinois dot edu), Tue, 12–1pm, 416 Transportation Building
    • Sondria Cottrell (bcottre2 at illinois dot edu), Thu, 1–2pm, Zoom
  • Textbook for reference (not required): Introduction to Operations Research by Hillier and Lieberman (10th edition)
  • Grading Compositions:
    • Homeworks: 50%
    • Midterm exam: 15%
    • Final exam: 20%
    • Quizzes: 15%
  • Course Resources:
    • All course resources will be available in Canvas. See the resource on how to access Canvas
    • Lectures will be recorded and posted on Media Space (channel “IE310 Fall 2022”).
    • For discussions, we will use Canvas, which is highly catered to getting you help fast and efficiently from classmates and myself. Rather than emailing questions to me, I encourage you to post your questions on Canvas. This way, the answers would benefit everyone in the class.
    • For homework submissions, we will use Canvas.
  • Homework Policies:
    • Problem sets will be assigned approximately every week. Homework should be submitted to Canvas by 11:59pm Central Time on the due date. Late submissions by up to 3 hours will be accepted. After 3 hours passing the due, the submission leads to 20% reduction of the total points of assignments, e.g., submission with original 8/10 points is revised to 6/10.
    • HARD deadline of 3 days past the original due date. Late submissions after the hard deadline (penalty or not) lead to ZERO point (unless in very special cases and approved by instructor).
    • The lowest homework grade will be dropped out.
  • Course Description: The course will introduce fundamental topics in optimization at the undergraduate level. Some specific topics to be covered are: Linear Programming, SimplexMethod, Duality, Sensitivity Analysis, Game Theory, Transportation and Assignment Problems, Network Optimization Problems, Integer Programming, Nonlinear Optimization. This is a required course in the undergraduate IE and SED program.

  • Pre-requisites: Mathematical maturity at the level of a junior undergraduate student will be assumed. Specifically, prior coursework in Linear Algebra, Calculus and familiarity with Matrices is required, e.g., MATH 257 or MATH 415.

  • Student Learning Objectives: Formulate mathematical models for common operations research applications, Apply common optimization algorithms for a variety of optimization problems (e.g., linear programs, network models, integer programs)

  • Academic Integrity: See university integrity policy here.

Quizzes and Exams schedule:

  • Quiz 1: (scheduled) Wed 09/07 30 minutes take-home quiz. Covering: TBA in Canvas
  • Quiz 2: (scheduled) Wed 09/28 30 minutes take-home quiz. Covering: TBA in Canvas
  • Mid exam: (scheduled) Wed 10/19 90 minutes take-home exam. Covering: TBA in Canvas
  • Quiz 3: (tentative) Wed 10/26 30 minutes take-home quiz. Covering: TBA in Canvas
  • Quiz 3: (scheduled) Wed 11/16 30 minutes take-home quiz. Covering: TBA in Canvas
  • Final exam: (scheduled) 180 minutes take-home exam with 5-days time window. Covering: TBA in Canvas

Tentative list of topics

  • Linear Programming (Ch. 3, 4, 5, 6, 7)
    • Model formulation
    • Graphical approach
    • Simplex method
    • Duality theory
    • Sensitivity analysis
  • Applications
    • Game theory: Zero-sum games, Nash equilibrium
    • Online retailing: transportation problem
    • Online advertising: ad recommendation/allocation problem
    • Ride hailing: assignment problem
  • Optimization solver
    • Excel solver
  • Dynamic programming (Ch. 11)
    • Shortest path problem
    • Stagecoach problem
  • Nonlinear Programming (Ch. 13)
    • Unconstrained optimization - search methods
    • Constrained optimization - Lagrange multipliers, KKT conditions
  • Integer programming (Ch. 12)
    • Formulation, uses of binary variables

Lectures

The following is a tentative list of lectures. Subject to change. Lecture slides will be posted a day before the lecture in Canvas.

  • Week 1
    • Motivation of OR
    • Formulations Linear Programming
    • LP, Standard Form
  • Week 2
    • Linearization Techniques, Graphic Method
    • Corner Points, Simplex Method: Augmented LP, Basic Variables
    • Simplex Method: Adjacent CFPs, Recomputing new CFP, complete algorithm
  • Week 3
    • Labor day
    • Simplex Method: Algebraic Form
  • Week 4
    • Simplex Method: Tabular Form
    • Overview
  • Week 5
    • Shadow Prices
    • Dual LP
    • Duality Theory: weak and strong duality
  • Week 6
    • Duality Theory: complementary slackness
    • Advanced material: dual simplex method, sensitivity Analysis
    • LP Solving in Excel, Excel LP Solver Reports
  • Week 7
    • Application of LP: Transportation problem
  • Week 8
    • Application of LP: Assignment problem
  • Week 9
    • Review
    • Mid-term exam
  • Week 10
    • Game Theory I: Definition
    • Game Theory II: Solution Methods, Nash Equilibrum
  • Week 11
    • Shortest Path Problem, Dijkstra’s Algorithm
    • Dynamic Programming
  • Week 12
    • Machine learning and optimization
  • Week 13
    • Nonlinear Optimization: Stationary points, local min/max; convex functions and global-min; convex program
    • Nonlinear Optimization: Unconstrained optimization algorithms: bisection search and gradient descent
  • Week 14: Fall Break
  • Week 15
    • Integer Programming: Basics, Knapsack problem
    • Integer Programming: fixed-charge problem; matrix variable problems (facility location); solution algorithms
  • Week 16
    • Review