Algorithmic Graph Theory (Selected Topics in OR)
16:711:614, Index # 28122

Instructor: Vadim Lozin, lozin@rutcor.rutgers.edu
Time: By arrangement.
Place:  RUTCOR Building, Room 139

The core of the course is algorithmic developments for fundamental graph problems. We study general graph properties and basic graph techniques that can be used for designing algorithms. We also discuss some applications as well as relations of graph problems with other problems of combinatorial optimization. The course will have a strong research orientation.

Outline of topics:

1. Graphs: graph representations (general, optimal, dynamic); graph classes (characterization, recognition, inclusion relationship).
2. Problems: matchings with variations (induced matchings, alternating cycle-free matchings); independent sets and related problems (maximum clique, vertex cover, vertex packing); dominating sets with variations (independent domination, etc.); colorings (vertex coloring, edge coloring); paths and cycles (Hamiltonian and Eulerian paths and cycles).
3. Methods: graph decompositions (modular decomposition, clique separators, clique-width), graph transformations, augmenting graphs, robust algorithms.

Models in Insurance and Finance I - Actuarial Mathematics
16:711:531, Index # 12947

Instructor: Andras Prekopa

Topics: The economics of insurance. Individual risk models. Survival distributions and life tables. Life insurance. Life annuities. Net premiums. Multiple life functions. Multiple decrement models. Collective risk models for a single period. Collective risk models over an extended period. Applications of ristheory. Insurance models including expenses. Advanced multiple life theory.  Population theory. Theory of pension funding.

Text: Bowers, Gerber, Hickman, Jones, Nesbitt, Actuarial Mathematics, second edition. The Society of Acturaries, Ithaca, Ill., 1997.  ISBN: 0-938959-46-8

Grading: Based on the solutions of homework problems and a term project.

Case Studies in Applied Operations Research
Undergraduate Listing:  01:711:481, Index #67179
Graduate Listing: 16:711:548, Index #67267

Instructor: Professor Michael Rothkopf
Time: Mondays 5pm to 8pm
Place: RUTCOR Building, Room 139

This course aims at developing skills needed to apply operations research methods to real decision systems in business and governmental operations. The course will draw upon the experience of the instructor and of guest lecturers. In addition, groups of students will work on the analysis of actual operations. In past years the projects involved the scheduling of the Rutgers campus bus system the management of the campus mail system, modeling mobile telephone systems, matching faculty to courses in one of Rutgers' schools, the redesign of Rutgers' system for class period scheduling, modeling the worth to Merrill Lynch of a brokerage account, routing delivery trucks for Air Products and Chemical Co., and evaluating call center efficiency at AT&T.

We will undertake some modeling exercises, which will focus on the choice of equations to solve rather than solving them.  We will study a number of actual cases in which operations research analysis is appropriate.  These cases will raise issues involving model formulation and interpretation, uncertainty, financial comparisons, risk attitudes, decision trees and planning horizons. Some case studies may involve formulation of mathematical programming models.

Several operations research practitioners from industry will address the class. There is no final exam, but students will have written homework assignments and will work in teams to write a report dealing with the application of operations research to actual operations.

Prerequisites: Linear programming, probability, computer programming, a year of calculus, and a course that used calculus or permission of the instructor

Text:  S. R. Watson and D. M. Buede, Decision Synthesis, Cambridge University Press

The Cutting-Plane Method and the Traveling Salesman Problem
16:711:611, Index #67526, 3 credits

Instructor: Vasek Chvatal

Outline: Following the theoretical studies of J.B. Robinson and \H.W.  Kuhn in the late 1940s and the early 1950s, G.B. Dantzig, R. Fulkerson, and S.M. Johnson demonstrated in 1954 that large instances of the TSP could be solved by linear programming. Their approach remains the only known tool for solving TSP instances with more than several hundred cities; over the years, it has evolved further through the work of M. Grötschel, S. Hong, M. Jünger, P. Miliotis, D. Naddef, M. Padberg, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and others. We will study some of its refinements incorporated in Concorde, a computer code for solving traveling salesman problems (developed by D. Applegate, R. Bixby, V. Chvátal, and W. Cook) that solved a 13,509-city instance in May 1998 and a 15,112-city instance in April 2001.

Topics: Spotting violated subtour inequalities (parametric connectivity, shrinking heuristic, subtour cuts from tour intervals, Padberg-Rinaldi exact-separation procedure). Hypergraph templates of facet-inducing inequalities. Spotting violated blossom inequalities. Tightening and teething. Local cuts. The core LP relaxation. Cut storage. Edge pricing.

• D. Applegate, R. Bixby, V. Chvátal, and W. Cook, On the Solution of Traveling Salesman Problems
• D. Applegate, R. Bixby, V. Chvátal, and W. Cook, TSP cuts which do not conform to the template paradigm

• D. Applegate, R. Bixby, V. Chvátal, and W. Cook, Implementing the Dantzig-Fulkerson-Johnson Algorithm for Large Traveling Salesman Problems

Related web sites:

• TSP home page.
• Ivars Peterson's The Traveling Monkey and The Shoelace Problem
• Julian Lethbridge's prints

Prerequisites: Linear programming, computer programming.

Grading: Based on the solutions of homework problems and on class presentation.

Computational Projects in Operations Research
16:711:517, Index #13475, 3 credits

Instructor: Endre Boros
Time: 1^st meeting, Wed. 9/1/04, 9:50AM

Course Outline: The course will be highly interactive with individual and group assignments and with intensive computer practice. The students will be offered various problems and projects to work on during the semester. Some of the projects will involve the use of certain software packages, while some others will require coding. In addition, each of the students will be required to solve homework assignments, mostly programming tasks. Grading will be based on homeworks and projects.

The course concentrates on OR modeling and problem solving with AMPL, a mathematical modeling language. Additionally, elements of other programming environments will be described, and a few assignments will be given, in particular, in PERL to realize basic data structures and combinatorial algorithms; in C++ to develop basic routines, and interface with CPLEX; and in HTML, Javascript and CSS to develop home pages and interactive web-projects.

Some related books:

• Robert Fourer, David M. Gay, and Brian W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, (Duxbury Press/Brooks/Cole Publishing Company, 1993).
• Daniel Gilly and the staff of O'Reilly & Associates, Inc., UNIX in a nutshell, (O'Reilly & Associates, Inc., Sebastopol, CA, 1992)
• D.E. Knuth, The Art of Computer Programming: Fundamental Algorithms, (Addison Wesley, Reading, MA, 1973)
• Matematika, User's Manual, (Wolfram Research, Inc., 1990)
• Chuck Musciano and Bill Kennedy, HTML - The Definitive Guide, (O'Reilly & Associates, Inc., Sebastopol, CA, 1997)
• H. Schildt, C -- The Pocket Reference, (Osborne McGraw-Hill, Berkeley, 1989)
• Bjarne Stroustrup, C++ Programming Language, (Addison-Wesley, Reading, MA, 1997)
• Larry Wall, Tom Christiansen and Randal L. Schwartz, Programming Perl, (O'Reilly & Associates, Inc., Sebastopol, CA, 1996)

Boolean Functions
16:711:553, Index #13599, 3 Credits

Instructor: Peter L. Hammer

The course will describe the uses, the theory and the algorithmic aspects of Boolean and of pseudo-Boolean functions, using frequently occurring models from operations research, electrical engineering, and modern applied mathematics. Among the important problems to be studied, we mention the Satisfiability problem, dualization, determination of prime implicants of Boolean functions, logic minimization, quadratic 0-1 optimization, roof-duality, MAX-SAT, etc. Important classes of Boolean functions (monotonic, regular, Horn, threshold, etc.) and of pseudo-Boolean functions (super-modular, linearly separable) will be examined.

Numerous applications will be presented to computer engineering, discrete optimization, artificial intelligence, voting, game and reliability theory, etc. 

Strong connections between linear programming, graph theory, Boolean and pseudo-Boolean functions, in the development of algorithms for solving operations research problems will be emphasized.

Prerequisites: Familiarity with graph theory and linear programming is useful, but not absolutely necessary.

Discrete Optimiziation
16:711:513, Index #73268, 3 Credits

Instructor: Endre Boros (boros@rutcor.rutgers.edu)
Time: W 9:50-12:50PM
Place: RUTCOR Building, Room 139
Prerequisites: Calculus, Linear Algebra, Linear Programming

Background: Review of linear programming, the ellipsoid algorithm. Introduction of graphs, networks, Boolean and pseudo-Boolean functions, polyhedral theory and integer lattices.  Elements of complexity theory.

Models: Knapsack, set-covering, (vehicle routing, airline crew scheduling), packing, partitioning, clustering, (stability number, voting districts, cutting-stock), bin-packing, scheduling, (job-shop, flow-shop, one-machine), plant location, transportation problems.General and 0-1 Integer Programming: Formulations, LP relaxation, rounding, unimodularity. Implicit enumeration and branch-and-bound tecniques.  Polyhedral description: vertices, feasibility, valid inequalities, faces and facets.  Value function, surrogate, subadditive and Lagrangean duality. Cutting planes, Gomory’s algorithm, Chvatal cuts, Lovasz-Schrijver cutting planes. Decomposition methods. Preprocessing techniques and heuristics.

Graphs & Networks: Minimum paths, spanning trees, max flow-min cut, CPM networks, matching algorithms. Traveling salesman, Chinese postman. 

Matroids, Submodular Optimization:  Matroids, polymatroids, “greedy” algorithms, submodular functions.

References:

• G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, J. Wiley, 1988.
• A. Schrijver, Theory of Linear and Integer programming, J. Wiley, 1987.
• T. Lengauer, Combinatorial Optimization in Circuit Layout Design, J. Wiley, 1990.
• C.H. Papadimitriu and K. Stieglitz, Combinatorial Optimization: Algorithms and Complexity,Prentice-Hall, 1982.
• L.A. Wolsey, Integer Programming, J. Wiley, 1998.
• W.F. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver, Combinatorial Optimization, J. Wiley, 1998

Pseudo Boolean Functions
16:711:611, Index #22781, 3 Credits

Instructors: Endre Boros (boros@rutcor.rutgers.edu) 732-445-3235, Peter Hammer (hammer@rutcor.rutgers.edu) 732-445-4812
Time: TBA
Place: RUTCOR Building, Room 139

Course Outline:

1. Introduction, definitions and notations.
   
2. Examples.
   
3. General Pseudo-Boolean Functions - Representations of pseudo-Boolean functions, rounding procedures and derandomization, persistency, local optima, basic algorithm, reductions to quadratic optimization, posiform maximization, l₂-approximations and applications to game theory.
   
4. Quadratic Pseudo-Boolean Functions - Roof duality (majoriztion, linearization, complementation, equivalence of formulations and persistency, network flow model), hierarchy of bounds (cones of positive quadratic pseudo-Boolean functions, complementation, majorization, linearization), polyhedra, heuristics.
   
5. Special classes - Sub- and supermodular functions, half-products, hyperbolic pseudo-Boolean functions, products of linear functions
   
6. Approximation algorithms - MAX-SAT and variants, ¾-approximation of MAX-2SAT via roof-duality, ¾-approximation of MAXSAT via convex majorization.

Financial Mathematics
16:711:631:01, Index #14262

Instructor: Andras Prekopa
Time: Tuesday, Friday  9:50-11:10 AM
Place: RUTCOR Bldg., Room 166
Prerequisites: Probability Theory, Linear Programming.

Topics: Cash flow streams. Financial instruments (stocks, bonds, futures, options, cash flows). Utility functions. Arbitrage pricing theory. Application of Martingales.  Brownian motions. Ito’s lemma. Black-Scholes theory. Parabolic PDE’s and their numerical solutions.  The Feynman-Kac solution. Exotic and path-dependent options (chooser, barrier, lookback, Asian, Bermudan, etc.). Interest rate models (Vasicek, Hull-White).  Short introduction to stochastic programming models. Markowitz’s mean-variance models. Bond portfolio composition models. Term structures.  The use of goal programming. Dynamic option selection models.  Value at Risk models. 

Books: Below is a list of books which are useful to study the subject. However, only parts of them will be used in the course. A complete manuscript of the presentations will be available.

1. D. Duffie, Dynamic Asset Pricing Theory, Second Edition, Princeton University Press, 1996.
2. J. C. Hull, Options, Futures and Other Derivatives, Fourth Edition, Prentice Hall, 2000.
3. D. G. Luenberger, Investment Science. Oxford University Press, 1998.
4. T. Mikosch, Elementary Stochastic Calculus, World Scientific, 2000.
5. A. Prekopa, Stochastic Programming, Kluwer, 1995
6. P. Wilmott, S. Howison and J. Dewynne, The Mathematics of Financial Derivatives.  Cambridge University Press, 1997.

Grading:  Based on the homework problem solutions and the quality of a term project prepared by each student.

Office Hours: After class or by appointment.

Integer Programming
16:711:465, Index #67389
(Required course for the MINOR in Operations Research)

Instructor: RUTCOR Faculty
Place: Room 139, RUTCOR Building, Busch Campus
Time: Tuesday, Friday 9:50-11:10 AM

Prerequisites:  Calculus, Linear Algebra and Linear Programming

Syllabus: Overview of discrete optimization models occurring in business, engineering, industry and the sciences.

Modelling with integer variables. Specially structured problems: knapsack, covering and partitioning problems.

A quick introduction to complexity theory: problems, instances, worst-case complexity, polynomial algorithms, the classes P and NP. Linear programming relaxations, integrality of solutions, unimodularity and applications for assignment problems, shortest path and network computations. Enumerative methods: branch-and-bound, implicit enumeration, bounding techniques. Lagrangean and surrogate duality. Cutting planes, Gomory’s algorithm, lifting and projecting for binary optimization. Heuristics: greedy algorithms, local search, truncated exponential schemes.

Book to be Used:  Discrete Optimization, R. Gary Parker, Ronald L. Rardin, Academic Press, 1988 (available at Bookstore on College Avenue) and Handouts.

Grading: Homework (20%), Midterm (30%), and Final exam (50%)

Introductory Topics in OR
16:711:295, Index #11108

Instructor: Adi Ben-Israel
Office: RUTCOR Building, Room 113
Phone: (732) 445-5631
Email: bisrael@rutcor.rutgers.edu
Course Homepage: http://rutcor.rutgers.edu/~bisrael/295-Webpage.html
Syllabus: http://rutcor.rutgers.edu/~bisrael/295-Syllabus.html
Office Hrs: TBA
Time: M, W, 2:50-4:10 (5^th period)
Place:  RUTCOR Building, Room 167

Text: Operations Research, Applications and Algorithms (3^rd edition), Wayne L. Winston, Duxbury Press

Course description: This course is an introduction to the basic methods and models of Operations Research (abbreviated O.R.): linear programming, network models, integer programming, nonlinear programming, inventory control, dynamic programming

O.R. can be described as follows (see text, p. 1) : "... the term operations research (or, often, management science) means a scientific approach to decision making, which seeks to determine how to design and operate a system, usually under conditions requiring the allocation of scarce resources."

The course is computer based, using MS Excel, and Solver (an add-in to Excel).

The study of the methodology of O.R. requires a working knowledge of linear algebra and probability, and a good understanding of calculus. These are expected of the students.

Grading Policy: There will be 8-10 homework assignments (lowest grade discarded). Late homework will not be accepted. The final grade will be assigned based on 20% midterm, 40% homework, 40% final exam.

Nonlinear Programming
16:711:612, Index #48932, 3 Credits

Syllabus:

1. Unconstrained optimization:  Optimality conditions, Newton’s method, Line search and trust region methods,
2. Methods for unconstrained optimization: Steepest descent, Quasi-Newton methods, Linear conjugate gradient methods and truncated Newton methods, Nonlinear conjugate gradient methods, Limited-storage quasi-Newton methods, Nonlinear least squares methods,
3. Constrained nonlinear optimization – theory: Lagrange multipliers and optimality conditions, Duality theory,
4. Methods for nonlinear optimization: Reduced gradient methods, Sequential quadratic programming methods, Exact and inexact penalty methods and augmented Lagrangian methods,
5. Barrier Methods: Classical interior point methods, Infeasible interior point methods and merit functions, Line search and trust region methods, Advanced topics – Filters and complementarity constraints.

Queueing Theory
16:711:556, Index #73270

Instructor:  Benjamin Avi‑Itzhak

Topic Outline:

1. Elements of Stochastic Processes: Definition of a stochastic process; strict and covariance stationarity; ergodicity; discrete time Markov chains; semi‑Markov processes and chains; embedded Markov chains; continuous time Markov chains; birth‑and‑death processes; Poisson processes; diffusion processes; Markovian queueing processes and Jackson type networks.
2. Definition of a queueing system; Little's theorem; DAASSP (departures and arrivals see same picture) theorem; the random observer; ROSTA (random observer sees time averages), PASTA and ASTA theorems; the work in the system; the random modification (remaining work in service); work conserving schemes (disciplines) and the work conservation theorem.
3. Applications:  the relation between queueing time and queue size in M/G/1 type queues; busy period characteristics in conservative M/G/1 type queues; non‑preemptive priorities; optimal priority schemes; SRPF schemes.
4. Generalized M/G/1 queues: The generic model; M/G/1; a sequence of two servers in tandem with no intermediate queue; server's breakdowns and vacations; preemptive repeat and resume priorities; Takacs integro‑differential equation approach.  A busy period approach; Gated queues with limited batch sizes, unlimited batch sizes, processor sharing, FIFO, LIFO and random selection for service.
5. Lindley's GI/G/1 model; the Wiener‑Hopf type integral equation and its solution; bounds on the expected equilibrium waiting time; Kingmans's heavy traffic approximation; GI/M/1 example; Kendal's and Smith's theorems for the conditional equilibrium distributions of waiting times and lines in GI/M/r queues.
6. Comparison methods for queues:  Stochastic ordering; convex and concave ordering; classes of distribution functions (IFR/DFR, etc.); montonicity and comparability of stochastic processes; monotonicity properties and bounds and approximations for queueing processes.
7. Tandem queues:  Avi‑Itzhak's theorem for deterministic service times; bounding and approximations; optimal servers ordering; just‑in‑time systems and throughput approximations; strategies for deployment of flexible servers; schemes for fork‑join (split and match) systems; correlated service times.
8. Networks: Reversibility, quasi‑reversibility, symmetric queues and product form (kelly type) networks; nonproduct‑form networks; approximations and bounds; decomposition and aggregation methods, numerical methods.
9. Applications of queueing models: Service systems; traffic and transportation; computer systems; voice and data communications; production and logistics. * It is not possible to cover all the listed topics in depth in a one semester course.  Some of the topics will only be surveyed.

Prerequisites:  Probability and elementary knowledge of Stochastic Processes or Stochastic Models.

Grading:  Home assignments, class presentations and midterm(s) (take home) ‑ 50 points, Final exam (possibly take home) ‑ 50 points

Reading: Home assignments include reading of a  number of journal publications in addition to specific sections in the reference books.

Reference Books:

1. L. Kleinrock, Queueing Systems, Vol. 1: Theory, Wiley & Sons, 1975. (* Major reference book.)
2. L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, Wiley & Sons, 1976.
3. J.W. Cohen, The Single Server Queue, North‑Holland, 1982.
4. F.P. Kelly, Reversibility and Stochastic Networks, Wiley & Sons, 1979.
5. D.R. Cox and W.L. Smith, Queues, Wiley & Sons, 1961.
6. L. Takacs, Introduction to the Theory of Queues, Oxford University Press, 1962.
7. D. Stoyan, Comparison Methods for Queues and Other Stochastic Models, Wiley & Sons, 1985.
8. J. Walrand, An Introduction to Queueing Networks, Prentice Hall, 1988.
9. A.E. Conway and N.D. Georganas, Queueing Networks‑Exact Computational Algorithms, MIT Press, 1989.
10. R.W. Conway, W. L. Maxwell and L.W. Miller, Theory of Scheduling, Addison‑Wesley, 1967.
11. D. Gross and C.M. Harris, Fundamentals of Queueing Theory, Wiley & Sons, 1974.
12. D.P. Heyman and M.J. Sobel, Stochastic Models in Operations Research (two volumes). McGraw‑Hill, 1982.
13. J. Riordan, Stochastic Service Systems, Wiley & Sons, 1962.
14. R.W. Wolf, Stochastic Modeling and the Theory of Queues, Prentice Hall, 1989.

Game Theory
16:711:612, Index #10067, 3 credits

Instructor: Vladimir Gurvich (gurvich@rutcor.rutgers.edu)

Course Outline: Matrix games, max min , min max and saddle point. Pure and mixed strategies. Solvability in mixed strategies. Von Neumann's Theorem for matrix games. Bimatrix and n-matrix games. Nash equilibria and Nash solvability. Perfect equilibria and perfect solvability.  Sophisticated equilibria and dominance solvability. Games in extensive, positional and normal form. Perfect information and solvability in pure strategies. Nash solvability of the cyclic games. Domination and dominance solvability. Backward induction. Dominance solvable extensive and secret veto voting schemes. Cooperative games. Coalitions.  Transferable and non-transferable utilities, TU- and NTU-games.  Cores and core-solvability.  Bondareva-Shapley's Theorem and Scarf's Theorem. Effectivity functions and game forms, Moulin-Peleg's Theorem.  Cooperative games in effectivity function form, Keiding's Theorem. Stable effectivity functions and stable families of coalitions. Intrduction to Social Choice Theory. Paradox Arrow. Social choice functions and correspondences. Boolean functions and graphs in game theory: Boolean duality and Nash solvability. Read-once Boolean functions, P4-free graphs and normal form of the positional games with perfect information.  Stable effectivity functions and Berge's perfect graphs. Stable families of coalitions and normal hypergraphs. The Shapley value and the Banzhaf power index for cooperative games and approximation of pseudo-Boolean functions.

No Prerequisites, graph theory and linear programming would be useful but not necessary.

Simulation
16:711:613, Index #10068, 3 Credits

Detailed Outline:  

1	Introduction to discrete event simulation	1, 2
2	Random number generation, Intro. To ARENA	4, 5.1-5.3
3	ARENA basics	5.4--5.8
4	Model testing and debugging	6
5	Input analysis	7
6	Model verification and validation	8
7	Output analysis	9
8	Advanced ARENA modeling-production models 1	11
9	Advanced ARENA modeling-production models 2	11
10	Advanced ARENA modeling-transportation models 1	12
11	Advanced ARENA modeling-transportation models 2	12
12	Advanced ARENA modeling-information systems 1	13
13	Advanced ARENA modeling-information systems 2	13
14	Advanced ARENA modeling-other topics

Semidefinite and Second Order cone Programming
16:711:613, Index #30902

Instructor: Farid Alizadeh
First organizational class meets: Wednesday September 3^rd., 1:00-3:30 PM at RUTCOR room 139.
(Class day and time may change depending on teaching schedule.)
Course home-page: http://rutcor.rutgers.edu/~alizadeh/CLASSES/03fallSDP/
(All up-to-date information including class date and location will be posted in this page.)

Semidefinite programming (SDP) is a relatively new topic in optimization theory that emerged in early nineties. It has attracted considerable attention for several reasons. First it is a natural model that pops up in diverse application areas from combinatorial optimization and graph theory, to statistics, to many areas of engineering. Second the underlying problem is now fairly well-understood and it is possible to come up with both theoretically and pragmatically efficient algorithms. Third, the subject has intellectual appeal in that methods from several areas of mathematics come together to form an elegant theory.

In this course we present a rather comprehensive survey of the subject. We will overview semidefinite programming, study duality and complementarity conditions, and cover at least one class of interior point algorithms. We will survey several areas of applications. For instance in combinatorial optimization we study Lovasz theta function and Goemans-Williamson approximation algorithm to the MAXCUT and related problems. We will study one or two applications in statistics and finance. For instance we study the connection to Markowitz portfolio selection theory and to statistical optimal experiment design. We will also study the connection to positive polynomials and moment problems and theory implications in shape constrained approximation and regression. Our coverage will be mathematically deep, though almost all preliminary material will be reviewed. In particular we shall cover the theory of Euclidean Jordan algebras and their relevance to the most elegant formulation of SDP and its generalization.

Prerequisites: Ph.D. standing and the proverbial "mathematical maturity" are the only prerequisites. Knowledge of linear programming will be quite helpful though strictly speaking not required. Good understanding of linear algebra is essential.

Student Requirements: Each student is required to take turn and jot down notes during the lectures and then transcribe them into LaTeX. The notes will then be posted in the course web page. In addition each student is required to prepare a 30-40 minute talk which can be either presentation of a research paper by others or it can be a project that he/she has conducted in the course.

Reading: There is no official textbook. Relevant papers will be made available in the course home page.

Stochastic Models of Operations Research
16:640:424, Index #07250, 3 Credits

Instructor: Andras Prekopa, prekopa@rutcor.rutgers.edu, 732-445-3184
Time: M, Th, 9:50-11:10am
Place: RUTCOR Building, Room 139
Office Hourse: M, Th, 2-3pm or arrangement

Topics: Markov chains: definition, transition probabilities, special Markov chains (random walks, dams and inventories, branching processes), classification of states, limit theorems. Poisson processes: derivations, homogeneous, non-homogeneous processes, spacial and marked Poisson processes. Continuous time Markov chains: the Chapman-Kolmogorev equation, birth and death processes, the case of a finite state space, special cases, limiting behavior. Renewal processes: definition, the renewal function, replacement models, renewal theorems, inspection paradox, applications. Brownian motions: definition, processes with independent increments, the maximum variable and the reflection principle, Brownian bridge, geometric Brownian motion, applications in modern financial theory. Queueing theory: queueing systems, Little’s formula, Poisson arrivals and exponential and general service times, the case of an infinite number of servers, priority queues, queueing systems.

Prerequisites:  Probability Theory

Book:  H. M. Taylor and S. Karlin, An Introduction to Stochastic Modeling, 3^rd edition, Academic Press, 1998.  ISBN: 0-12-684887-4.

Grading: based on the homework problem solutions and the results of two exams; one midterm and one final.

Stochastic Models in Operations Research
16:711:525, Index #29553

Topics:

1. Review of basics in the axiomatic theory of probability.
2. Definition of a stochastic process. Classification of stochastic processes.
3. Discrete time Markov Chains. Transition probabilities. Classification of states. Limit theorems. Applications. Markov decision processes. Applications.
4. Poisson processes. Derivations of the process from postulates. Properties of the exponential distribution.  Planar and special random point distributions. Applications.
5. Continuous time Markov chains. Kohmogorov equations. Birth and death processes. Stationary distributions. Applications.
6. Renewal theory. Elementary renewal theorem. Renewal equation. Renewal-reward processes.
7. Brownian motion process. Refection principle and distribution of a maximum. Valuation of financial derivatives.
8. Queueing systems. Basic notions.  The M/M/s system with finite and infinite capacities. Elements of queueing networks.

Book:  Taylor, Karlin, “An Introduction to Stochastic Modeling”, 3^rd edition, Academic Press, 1998.

Grading: Based on the solutions of the homework problems and the results of the written midterm and final exams.

Stochastic Programming
16:711:555, Index #73269, 3 Credits

Instructor: Andras Prekopa
Time: M, Th, 9:50-11:10AM
Place: RUTCOR Building, Room 139

Stochastic programming is a rapidly developing area.  It is on the border line of statistics and probability theory on the one hand and mathematical programming on the other hand.  It can be defined as a methodology to optimize the design and operation of stochastic systems by the use of mathematical programming tools.

Topics: Overview of statistical decision principles. Overview of stochastic programming model constructions: reliability type models, penalty type models, mixed models, static and dynamic type models.  The simple recourse model and its numerical solution techniques.  Convexity theory of probabilistic constrained models. Bounding and approximation of probabilities.  Numerical solution of probabilistic constrained models.  Two-stage programming under uncertainty and the solution of the relevant problem by Benders' decomposition.  Multi-stage stochastic programming models.  Scenario aggregation.  Distribution theory of stochastic programming.  Applications to production, inventory control, water resources, finance, power and communication systems.

Prerequisites: Probability theory, linear programming

Book: A. Prekopa, Stochastic Programming, Academic Publishers 1995. (The instructor will make available a few printed copies for the audience.)

Grading: Based on the solutions of the homework problems and the quality of a term project work.  Each student will have his/her own course-work subject following an agreement with the instructor.

Theory of Linear Optimization
16:711:453, Index #07249, 3 Credits
Master student’s register under 16:711:614, Index #07652, 3 Credits

Instructor: Endre Boros
Time: T, F, 9:50-11:10AM
Place: RUTCOR Building, Room 166

Topics include convex sets, polyhedra, Farkas lemma, canonical forms, simplex algorithm, duality theory, revised simplex method, primal-dual methods, complementary slackness theorem, maximal flows, transportation problems, 2-person game theory.

Prerequisite:  01:640:250 Introductory Linear Algebra

Book to be used: Linear Programming, Vasek Chvatal, W. H. Freeman and Company 1980. Available at the Bookstore on College Avenue.

Back to RUTCOR page.