UAIC
Computer Science Department

Operations Research

Olariu Emanuel Florentin

Autumn/Winter 2024-2025

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.

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. Each homework can be solved by teams of 1-3 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 basic matrix algebra and some combinatorics optimization would be required.

Course information sheet.

Results for the 19th of February exam.

Bibliography:

  • Bertsimas, D., J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Belmont, Massachusetts, 1997.
  • Chekuri, C., Topics in Combinatorial Optimization, University of Illinois Urbana-Champaign, Lecture Notes, 2010.
  • Conforti, M., G. Cornuejols, G. Zambelli, Integer Programming, Graduate Texts in Mathematics, Springer, 2014.
  • Griva, F. S., G. J. Lieberman, , Introduction 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 1).
  • Geometric Linear Programming (week 1).
  • Basic Feasible Solutions and Extreme Points (week 2).
  • Algebra of Simplex and Simplex Algorithm (week 3).
  • Degeneracy, Unboundedness, Anticycling (week 4).
  • Finding an Initial Basic Feasible Solution (week 4).
  • Dual Problem. Weak and Strong Duality, Complementary Slackness (week 5).
  • Algebra of Dual Simplex and Dual Simplex Algorithm (week 5).
  • Integer Programming Models (ILP, MILP, BILP) (week 6).
  • Totally Unimodular Matrices (week 6).
  • Branch and Bound Algorithm for ILP (week 7).
  • Cutting Plane Method for ILP (week 7).
  • Column Generation. Restricted master problem and the subproblem (week 9).
  • Primal-Dual Interior Point Methods (week 10).
  • Predictor-Corrector Algorithm (week 10).
  • Total Unimodularity Revisited. Unimodular Matrices (week 11).
  • Total Dual Integrality. The Submodular Polyhedron. The Matching Polytope (week 11).
  • Decision with/without Experimentation (week 12).
  • The Value of Experimentation. Decision Trees (week 12).
  • Non-cooperative Zero-Sum Game Theory. Solving Games by Pure and Mixed Strategies (week 13).
  • Cooperative Game Theory. The Core, the Shapley Value, and the Nucleolus (week 13).

 

Lectures:

Reading projects topics (contact me for other subjects):

E-mail me for any question regarding your chosen topic.