
Operations Research

Autumn/Winter 20192020

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, olariu at info dot uaic dot ro
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. (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.
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, 2004.
 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:
 Introduction, Motivation, and Examples.
 Geometric Linear Programming.
 Basic Feasible Solutions and Extreme Points.
 Algebra of Simplex and Simplex Algorithm.
 Degeneracy, Unboundedness, Anticycling.
 Finding an Initial Basic Feasible Solution.
 Dual Problem. Weak and Strong Duality, Complementary Slackness.
 Algebra of Dual Simplex and Dual Simplex Algorithm.
 Integer Programming Models (ILP, MILP, BILP). Examples.
 Totally Unimodular Matrices, Examples.
 Branch and Bound Algorithm for ILP.
 Cutting Plane Method for ILP.
Seminar/lab situations
Lectures:
 Lecture 1 on October 2, 2019: Introduction, Motivation, Examples, Geometric Linear Programming.
 Lecture 2 on October 9, 2019: Algebraic Approach, Basic Feasible Solutions, Extreme Points.
 Lecture 3 on October 16, 2019: Algebra of Simplex, Simplex Algorithm, Tableau Implementation.
 Lecture 4 on October 23, 2019: Simplex Special Situations, Two Phase Method, Big M Method.
 Lecture 5 on October 30, 2019: Dual Problem, Duality Theory, Dual Simplex Algorithm.
 Lecture 6 on November 6, 2018: Integer Programming, Models. Totally Unimodular Matrices.
 Lecture 7 on November 13, 2018: Branch and Bound Algorithm. Cutting Plane Method.