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