Math Models of OR, Fall 2023.

MATP4700.

Contents of this page:

Course Basics

• Course outline.
• Grades, software, notes, and other material will be posted on LMS.
• We’ll be conducting all class-related discussion on Piazza this semester. The quicker you begin asking questions on Piazza (rather than via emails), the quicker you’ll benefit from the collective knowledge of your classmates and instructors. We encourage you to ask questions when you’re struggling to understand a concept. You can even do so anonymously. Link
• Office hours:
  • in-person: Tuesdays, 2.30-4pm, AE 325. Masks required.
  • on webex: Thursdays, 1-3pm, https://rensselaer.webex.com/meet/mitchj
  • in-person with the TA: Mondays, 2-3.30pm, AE 317.
• A simple pivot tool from Bob Vanderbei, an RPI alum and Princeton profesor.

Grades

Homeworks

• Homework 1, due September 8 on LMS. Solutions are available on LMS.
• Homework 2, due September 19 on LMS. Solutions are available on LMS.
• Homework 3, due September 26 on LMS. Solutions are available on LMS.
• Homework 4, due October 17 on LMS. Solutions are available on LMS.
• Homework 5, due October 31 on LMS. Solutions are available on LMS.
• Homework 6, due November 21 on LMS. Solutions are available on LMS.
• Homework 7, not collected or graded. Solutions are available on LMS.

Exams

• Old exams are available on LMS.
• Graded exams are available on gradescope.
• Exam 1 will be in class on Tuesday, October 3. It will cover the material in the first 9 lectures.
  You can bring one 8.5x11 sheet of paper with handwritten notes (no scanning or photocopying!) You can write on both sides.
• Exam 2 will be on Tuesday, November 7.
  The topics covered will come from Lectures 11-19.
  You can bring one 8.5x11 sheet of paper with handwritten notes (no scanning or photocopying!) You can write on both sides.
• Exam 3 will be on Friday, December 8.
  The topics covered will come from Lectures 21-27.
  You can bring one 8.5x11 sheet of paper with handwritten notes (no scanning or photocopying!) You can write on both sides.

Project

• The first part of the project is due on October 27th.
• The second part of the project is due on November 17th. My model file is available.
• The third part of the project is due on December 5th.

Notes

Formulating linear optimization problems

• Lecture 1
  • Introduction: 01A_intro (0.1, 1.1, 1.2)
  • Some examples: 01B_more_examples (1.3)
  • Some contemporary applications of optimization (not covered in 2020): 01C_optimization_applications
  • Links to the lecture.
• Lecture 2
  • Two models from the text (1.1, 1.3).
  • Standard form: 02A_standardform (2.1,2.9)
  • Handling min-max and absolute values: 02B_maxmin (1.5)
  • Simplex tableaus: 02C_tableaus (2.2)
  • Links to the lecture.

Solving linear optimization problems

• Lecture 3
  • Pivoting: 03A_pivoting (2.3)
  • Choosing the pivot element: 03B_choosingpivot (2.4)
  • Optimal and unbounded forms: 03C_optimalform (2.5)
  • Solving a linear optimization problem: 03D_solvingLOP (2.6)
  • Links to the lecture.
• Lecture 4
  • Some definitions: 04A_definitions
  • The method of artificial variables: 04B_artificial (2.8)
  • Possible outcomes for the method of artificial variables: 04C_artificial_cases (2.8)
  • Links to the lecture.
• Lecture 5
  • Degeneracy: 05A_degeneracy (4.5)
  • An example of cycling: 05B_egcycling (4.5)
  • More on geometry of linear optimization problems: 05C_geometry (3.1,3.2,3.3)
  • Links to the lecture.
• Lecture 6
  • Revised simplex: 06A_revisedsimplex (4.2)
  • An example of revised simplex: 06B_revisedsimplexexample (4.2)
  • Links to the lecture.
• Lecture 7
  • Multiple optimal solutions: 07B_multipleoptima (3.4)
  • Convexity: 08A_convexity (3.5)
  • The Klee-Minty cube: 09A_kleeminty
  • Links to the lecture.
• Lecture 8
  • Equivalence of extreme points and basic feasible solutions: 07A_bfsextreme
  • Implementing simplex: 09B_simplex (4.1,4.4)
  • Links to the lecture.
• Lecture 9
  • Handling upper bounds: 08B_upperbounds
  • Introduction to AMPL: 09C_ampl. You don't need to look at AMPL until after Exam 1.
  • Links to the lecture.
• Lecture 10
  • Exam 1.
    

Duality in linear optimization

• Lecture 11
  • Motivations for the dual problem: 11A_duality_motivation
  • Constructing a dual problem: 12B_dual_construction (5.2)
  • Links to the lecture.
• Lecture 12
  • Relations between primal and dual problems: 12A_dualityrelations (5.1)
  • Strong duality: 12C_strongduality (5.1)
  • Complementary slackness: 13B_complementaryslackness (5.1.5)
  • Links to the lecture.
• Lecture 13
  • Constructing dual solutions using complementary slackness: 13C_dualcs
  • The dual simplex algorithm: 14A_dualsimplex (5.3)
  • Dual simplex and simplex applied to the dual: 14B_dualsimplexindual (5.3.2)
  • Links to the lecture.
• Lecture 14
  • Theorems of the alternative: 15A_farkas (Exercise 5.5.29)
  • Exploiting complementary slackness: 13D_f94cs
  • Links to the lecture.
• Lecture 15
  • Economic interpretation of dual variables: 13A_shadowprices (5.1.4)
  • Sensitivity analysis: 14C_sensitivityanalysis (5.4)
  • Links to the lecture.

Problems on networks

• Lecture 16
  • The transportation problem: 15B_transportation (5.2.2, 6.1)
  • Applying simplex to the transportation problem: 16A_trans_simplex (6.1)
  • Solving a transportation problem: 16B_trans_solve (6.1)
  • The assignment problem and variants of transportation problems: 16C_assignment (6.2, 6.5.3)
  • Links to the lecture.
• Lecture 17
  • Minimum cost flows on general networks: 17A_general_networks (6.3, 6.4)
  • Network simplex: 17B_networksimplex (6.5)
  • Links to the lecture.
• Lecture 18
  • Finding an initial spanning tree: 18A_gennet_initial (6.4.1)
  • Augmenting flow algorithms: 18B_augmentingflows
  • An overview of network flow problems: 18C_networkflowproblems (Chapter 6)
  • Links to the lecture.
• Lecture 19
  • Multicommodity network flow problems: 19A_multicommodity
  • The traveling salesman problem: 19B_tsp (6.5.3)
  • Links to the lecture.
• Lecture 20
  • Exam 2

Integer optimization problems

• Lecture 21
  • Solving integer optimization problems: 21A_branching (7.1, 7.2)
  • Branch-and-bound: 21B_bandb (7.3)
  • Links to the lecture.
• Lecture 22
  • Integer optimization formulations: 22A_formulations (7.6.1)
  • Facility location problems: 22B_facilitylocation (7.6.2)
  • Crew scheduling: 22C_crewscheduling
  • Links to the lecture.
• Lecture 23
  • Gomory cutting planes: (7.7.2)
  • Cutting planes for knapsack problems: 21C_knapsack (7.7.2)
  • Branch-and-cut: (7.7.2)
• Lecture 24
  • Compressed sensing introduction: 24A_compresssedsensingintro (1.8)
  • Compressed sensing models: 24B_compresssedsensingmodels (1.8)
  • Links to the lecture.

Interior point methods

• Lecture 25
  • Primal-dual interior point methods: 25A_interior, 25B_interior (21.1)
  • Strict complementarity: 25C_strictcomplementarity
  • Links to the lecture.

Dynamic programming

• Lecture 26
  • Shortest path problems with stages: 26A_dptrain (7.8.1)
  • Dijkstra's algorithm: 26B_dijkstra
  • Solving knapsack problems using dynamic programming: 26C_knapsackDP (7.9 for computational complexity)
  • Longest path problems: 26D_longestpath
  • Links to the lecture.
• Lecture 27
  • Equipment replacement problems: 27A_equipmentreplacement
    Also available is an AMPL formulation: run file, model file, data file.
  • Equipment replacement with computationally expensive cost evaluations: 27B_equipmentreplacementLP
    Also available is an AMPL formulation: run file, model file, data file.
  • The boxes problem: 27C_boxes
  • Links to the lecture.
• Lecture 28
  • Exam 3

Handouts and supplementary material:

• Applications of Optimization
• An interactive formulation of the diet problem is one of a collection of case studies in optimization at NEOS. The link also includes the ampl code for the diet problem.
• The brewery problem formulated as an AMPL example with sets. Data files can be found in this directory.
• An example of cycling in the simplex algorithm, from Ecker and Kupferschmid.

Other Resources:

• Information about AMPL.
• The NEOS Server: state of the art solvers for numerical optimization. You can submit your optimization problems written in AMPL (or other modelling languages) to this cloud solver.
• The NEOS optimization guide.
• Fourer, Gay, and Kernighan; AMPL: A Modeling Language for Mathematical Programming. The Scientific Press, Second Edition, 2002. This is the handbook for AMPL and is used for the project. Available online at http://ampl.com/resources/the-ampl-book/
  
• Ferris, Mangasarian, and Wright: Linear Programming with MATLAB. SIAM, 2007. Electronic resource available via the library.
  
• Lee, A First Course in Linear Optimization, Reex Press, 2013–16, available online at https://github.com/jon77lee/JLee_LinearOptimizationBook/blob/master/LPBook2.95.pdf
• Myths and counterexamples in optimization. This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in linear programming.
• A list of operations research sites.
• RIOT: Baseball Playoff Races. This site uses linear programming to determine when a baseball team is eliminated from contention.