Math Models of OR, Fall 2022.
MATP4700.
Contents of this page:
Course basics 
Grades 
Homeworks 
Exams 
Project 
Notes 
Handouts 
Other resources
 Course outline.
 Grades, software, notes, and other material will be posted on
LMS.
 Lecture notes are also available on
rpi.app.box.com.
Instructions to set up your box account are here:
RPI Box account information.
 We’ll be conducting all classrelated 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:
 Old exams are available on
LMS.

Exam 1 will be in class on Tuesday, October 4.
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.
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 minmax 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
 Equivalence of extreme points and basic feasible solutions:
07A_bfsextreme
 Multiple optimal solutions: 07B_multipleoptima
(3.4)
 Links to the
lecture.
 Lecture 8
 Convexity: 08A_convexity
(3.5)
 Handling upper bounds: 08B_upperbounds
 The KleeMinty cube: 09A_kleeminty
 Links to the
lecture.
 Lecture 9
 Implementing simplex: 09B_simplex
(4.1,4.4)
 Introduction to AMPL: 09C_ampl. You don't need to look at AMPL until after
Exam 1.
 Links to the
lecture.
 Lecture 10
Duality in linear optimization
 Lecture 11
 Motivations for the dual problem: 11A_duality_motivation
 Relations between primal and dual problems: 12A_dualityrelations
(5.1)
 Constructing a dual problem: 12B_dual_construction
(5.2)
 Links to the
lecture.
 Lecture 12
 Strong duality: 12C_strongduality
(5.1)
 Complementary slackness: 13B_complementaryslackness
(5.1.5)
 Links to the
lecture.
 Lecture 13
 Economic interpretation of dual variables: 13A_shadowprices
(5.1.4)
 Constructing dual solutions using complementary slackness: 13C_dualcs
 The dual simplex algorithm: 14A_dualsimplex
(5.3)
 Links to the
lecture.
 Lecture 14
 Sensitivity analysis: 14C_sensitivityanalysis
(5.4)
 Links to the
lecture.
 Lecture 15
 Theorems of the alternative: 15A_farkas
(Exercise 5.5.29)
 Dual simplex and simplex applied to the dual: 14B_dualsimplexindual
(5.3.2)
 Exploiting complementary slackness: 13D_f94cs
 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
Integer optimization problems
 Lecture 21
 Solving integer optimization problems: 21A_branching
(7.1, 7.2)
 Branchandbound: 21B_bandb
(7.3)
 Cutting planes for knapsack problems: 21C_knapsack
(7.7.2)
 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)
 Branchandcut:
(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
 Primaldual 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
 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/theamplbook/

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.
John Mitchell's homepage.