IE 310 Deterministic Models in Optimization
Undergraduate Course, University of Illinois Urbana Champaign, 2022
Syllabus
Overview
 Prerequisites: 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:001:50pm, 2035 Campus Instructional Facility
 Office Hour: Fri, 4:005: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 speciﬁc 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.
Prerequisites: Mathematical maturity at the level of a junior undergraduate student will be assumed. Speciﬁcally, 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 takehome quiz. Covering: TBA in Canvas
 Quiz 2: (scheduled) Wed 09/28 30 minutes takehome quiz. Covering: TBA in Canvas
 Mid exam: (scheduled) Wed 10/19 90 minutes takehome exam. Covering: TBA in Canvas

Quiz 3: (tentative) Wed 10/26 30 minutes takehome quiz. Covering: TBA in Canvas  Quiz 3: (scheduled) Wed 11/16 30 minutes takehome quiz. Covering: TBA in Canvas
 Final exam: (scheduled) 180 minutes takehome exam with 5days 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: Zerosum 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
 Midterm 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 globalmin; 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: fixedcharge problem; matrix variable problems (facility location); solution algorithms
 Week 16
 Review