
Operations Research

Autumn/Winter 20232024

Summary
The lectures will cover basic topics in Operations Research. Emphasis will be on Linear Programming.
Administrative
Lectures: weekly
in C411
Lecturer: Olariu E. Florentin C212, C building,
phone: 0232 20 15 46, fe dot olariu at gmail dot com
Office Hours: weekly, better by email appointment
Grading:
 First Part. There will be a number of three homeworks (25 points each) and a reading project (25 points)  giving a total of 100 points. Each homework can be solved by teams of 13 students. (Reading projects may require a survey of a scientific papers on a designated topic.)
 Second Part. A final written exam will give another 100 points.
 Both parts worth 50% of the total grade, but 50 points is the minimum required on each of both parts.
Prerequisites: Knowledge of basics matrix algebra and some combinatorics optimization would be required.
Course information sheet.
Seminar/laboratory.
Bibliography:
 Bertsimas, D., J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Belmont, Massachusetts, 1997.
 Chekuri, C., Topics in Research Combinatorial, University of Illinois UrbanaChampaign, Lecture Notes, 2010.
 Conforti, M., G. Cornuejols, G. Zambelli, Integer Programming, Graduate Texts in Mathematics, Springer, 2014.
 Griva, F. S., G. J. Lieberman, , Intorduction to Operations Research, McGraw Hill, 7th edition, 2001.
 Hillier, I., S. G. Nash, A. Sofer, Linear and Nonlinear Optimization, 2nd edition, SIAM, 2009.
 Kolman, B., R. E. Deck, Elementary Linear Programming with Applications, Elsevier Science and Technology Books, 1995.
 Schrijver, A., Theory of Linear and Integer Programming, Wiley & Sons, New York, 1999.
 Schrijver, A., A Course in Combinatorial Optimization, Electronic Edition, 2013.
 Taha, H. A., Operations Research: An Introduction, Prentice Hall
International, 8th edition, 2007.
 Vanderbei, R. J., Linear Programming  Foundations and Extensions, International Series in Operations Research & Management Science, Springer Science, 4th edition, 2014.
 Yang, X.S., Introduction to Mathematical Optimization  From
Linear Programming to Metaheuristics, Cambridge International
Science Publishing, 2008.
List of Topics (weekly updated):
 Introduction, Motivation, and Examples (week 2).
 Geometric Linear Programming (week 2).
 Basic Feasible Solutions and Extreme Points (week 3).
 Algebra of Simplex and Simplex Algorithm (week 4).
 Degeneracy, Unboundedness, Anticycling (week 5).
 Finding an Initial Basic Feasible Solution (week 5).
 Dual Problem. Weak and Strong Duality, Complementary Slackness (week 6).
 Algebra of Dual Simplex and Dual Simplex Algorithm (week 6).
 Integer Programming Models (ILP, MILP, BILP) (week 7).
 Totally Unimodular Matrices (week 7).
 Branch and Bound Algorithm for ILP (week 9).
 Cutting Plane Method for ILP (week 9).
 PrimalDual Interior Point Methods (week 10).
 PredictorCorrector Algorithm (week 10).
 Decision with/without Experimentation (week 11).
 The Value of Experimentation. Decision Trees (week 11).
 Column Generation. Restricted master problem and the subproblem (week 12).
 DantzigWolfe decomposition. (week 12)
Final situations
Lectures:
 Lecture 1 on October 9, 2023 (week 2): Introduction, Motivation, Examples, Geometric Linear Programming.
 Lecture 2 on October 16, 2023 (week 3): Algebraic Approach, Basic Feasible Solutions, Extreme Points.
 Lecture 3 on October 23, 2023 (week 4): Algebra of Simplex, Simplex Algorithm, Tableau Implementation.
 Lecture 4 on October 30, 2023 (week 5): Simplex Special Situations, Two Phase Method, Big M Method.
 Lecture 5 on November 6, 2023 (week 6): Dual Problem, Duality Theory, Dual Simplex Algorithm.
 Lecture 6 on November 13, 2023 (week 7): Integer Programming. Models. Totally Unimodular Matrices.
 Lecture 7 on November 27, 2023 (week 9): Branch and Bound Algorithm. Cutting Plane Method.
 Lecture 8 on December 4, 2023 (week 10): Interior Point Methods.
 Lecture 9 on December 11, 2023 (week 11): Decision Analysis.
 Lecture 10 on December 18, 2023 (week 12): Column Generation.
 Lecture 11 on January 8, 2024 (week 13): Perfect Formulations of Discrete Optimization Problems.
 Lecture 12 on January 15, 2024 (week 14): Game Theory: Cooperative and Noncooperative Games.