UAIC
Computer Science Department

Operations Research

Olariu Emanuel Florentin

Autumn/Winter 2019-2020


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 e-mail 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 Urbana-Champaign, 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: