Courses

• List of Courses
• Detailed Description

Graduate Studies

• Admission
• Masters Program
• Doctoral Program
• Financial Support
• Ph.D. Requirements
• Ph.D. Examination
• Research Proposal
• Student Research
• Thesis Defense
• Transfer of Credit
• Additional Information

Undergraduate Studies

• General Information
• Minor Requirements

 

Course Details

Integer Programming

Prerequisites: Calculus, Linear Algebra and Linear Programming

Course Outline:
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 ofsolutions, 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: Integer Programming, Laurence A. Wolsey John Wiley & Sons, Inc. 1998 ISBN: 0-471-28366-5 (Amazon.com)
Grading: Homework (20%), Midterm (30%), and Final exam (50%).

* Required course for the Minor in Operations Research

Theory of Boolean Functions

Course Outline:
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.

Computational Methods of Operations Research

Instructor: Endre Boros

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/or XPressMP; and on HTML, Javascript and CSS to develop home pages and interactive web-projects.

A sample of 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)
MOSEL/XPressMP (Dash Optimization)
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)
A. Thesen, Computer Methods in Operations Research (Adademic Press 1978)
Larry Wall, Tom Christiansen and Randal L. Schwartz, Programming Perl, (O'Reilly & Associates, Inc., Sebastopol, CA, 1996)

Stochastic Models in Operations Research

Instructor: Michael Tortorella, Ph. D.
Office Location: RUTCOR 148
Contact: If you need to contact me, please do so by email.
E-mail Address: mtortore@rutcor.rutgers.edu
Office Hours: Mondays and Thursdays 2-3 PM and by appointment.
Professor's Web Page: Under construction.
Course Web Page: The course is supported by Sakai. Please consult the Sakai page frequently.
Assignments will also be posted on the course page in addition to being given in class.

Prerequisite: Knowledge of probability theory (640:477, 640:580, or equivalent)

Course Goals: The major purpose of this course is to give you a sound foundation in the stochastic processes that underlie the major applications in operations research: queues, inventory, reliability, networks, and finance. When you complete this course, you will:
1. Gain an understanding of basic facts about mathematical modeling for stochastic systems.
2. Learn the fundamentals of these stochastic processes: a. Markov processes b. Random walks and renewal processes c. Stationary processes d. Martingales.
3. Have a solid foundation for learning more about mathematical modeling in operations research.
4. Be prepared to carry out research in this area.

Class Schedule: Mondays and Thursdays, period 2 (10:20 to 11:40 PM. Class meets in RUTCOR 139. First class: Thursday, January 24th. Last class: Monday, May 6th.

Required Text:
1. S. M. Ross, Applied Probability Models with Optimization Applications. Dover Publications (1992).

Optional Reading:
1. S. Karlin and H. M. Taylor (1975), A First Course in Stochastic Processes. New York: Academic Press.
2. D. R. Cox and S. D. Miller (1965), The Theory of Stochastic Processes. New York: John Wiley and Sons.
3. H. M. Taylor and S. Karlin (1984), An Introduction to Stochastic Modeling. New York: Academic Press.
4. D. P. Heyman and M. Sobel (1982), Stochastic Models in Operations Research. New York: McGraw-Hill.
5. F. S. Hillier and G. J. Lieberman (1967), Introduction to Operations Research. San Francisco: Holden-Day.

Course Requirements: Homework assignments, midterm exam, final exam, class participation.

Methods of Evaluation and Grading Policy: Grades are assigned as follows:
Homework assignments 30%
Midtern exam 30%
Final exam 30%
Class participation 10%

Attendance requirement: Standard Rutgers University attendance policies prevail. In cases where your numericl grade is on the borderline between two (final) letter grades, I reserve the right to round up or down depending on yur attendance and participation in class.

Dynamic Programming

Instructor: Andrzej Ruszczyński
E-Mail: rusz@business.rutgers.edu
Web: http://www.rusz.rutgers.edu/

Topics:
The shortest path problem.The principle of optimality. Examples
Label correcting algorithms
Controlled Markov chains. Finite horizon stochastic problems
Dynamic programming equations. Applications
Discounted infinite horizon problems
Value and policy iteration methods. Linear programming approach
Applications in inventory control, scheduling, logistics
The multiarmed bandit problem
Undiscounted infinite horizon problems. Stochastic shortest paths
Methods for solving undiscounted problems
Optimal stopping; asset pricing
Average cost problems
Methods for solving average cost problems
Controlled continuous time Markov chains
Introduction to approximate dynamic programming

Textbooks
Main:
1. M.L. Puterman, Markov Decision Processes, John Wiley & Sons, 2005

Supplementary:
2. D.P. Bertsekas, Dynamic Programming and Optimal Control, Athena, 1995 or 2001 vol. I and II.
3. W. B. Powell, Approximate Dynamic Programming, John Wiley & Sons, 2007.

Grading
The course grade will be based on the following components:
1. Homework assignments (30%)
2. Computational projects (20%)
3. Midterm exam (20%)
4. Final exam (30%)

Discrete Optimization

Instructor:

Prerequisites: Calculus, Linear Algebra and Linear Programming

Syllabus:

• Review of linear programming, duality theorem, Farkas' lemma, ellipsoid algorithm; complexity theory; a sample combinatorial problem and its analysis.
• Introduction to integer programming, pseudo-Boolean programming, overview of basic algorithms. Introduction to polyhedral combinatorics, analysis of spanning tree problems.
• Greedy algorithms, independence systems, matroids, submodular optimization.
• Short review of network optimization, and shortest path algorithms.
• Matching theory, theorems by Petersen, Berge, König-Egerváry, Frobenius, and Hall. Algebraic and polyhedral descriptions, theorems by Tutte, Berge, Lovász, Gallai, Edmonds, Hoffman and Kruskal, Balinski, Nemhauser and Trotter; the Hungarian method, Edmonds' blossom-shrinking algorithm, and Lovász's algorithm.
• Applications of matchings: chain covers and anti chains and Dilworth theorem; bi-stochastic matrices, theorem by Birkhoff and von Neumann; Euclidean TSP and Christofides' heuristic; maximum cuts in planar graphs.
• Stable matchings, Gale-Shapley theorem, polyhedral results.
• Knapsack problem, dynamic programming and approximation algorithms.
• Cutting-stock problems, Gilmore-Gomory algorithm, bin-packing problems and approximations, theorems by de la Vega and Lueker, Garey, Graham, Johnson and Yao, and Karmarkar and Karp.
• Set covering problems, exact and approximation algorithms, theorems by Lovász and Stein, Chvátal, Johnson, and Papadimotriou and Steiglitz.
• General and binary integer programming, LP relaxation, rounding. Implicit enumeration and branch-and-bound tecniques.
• Unimodularity, total unimodularity, TDI systems; theorems of Hoffman and Kruskal, Veinott and Dantzig, Ghouila-Houri, and Edmonds and Giles.
• Hilbert bases, integer version of Helly's and Caratheodory's theorems; results by Gordan, Doignon, Bell and Scarf, and Cook, Fonlupt and Schrijver.
• Value function, subadditive, surrogate and Lagrangean duality.
• Valid inequalities, cutting planes, Gomory's algorithm, Chvátal cuts, lift-and-project algorithms by Lovász and Schrijver, and by Balas and Ceria.

Books about discrete optimization:

• W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver: Combinatorial Optimization (Wiley, 1998)
• G. Cornuéjols: Combinatorial Optimization: Packing and Covering (SIAM, 2001)
• B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms (Springer, 2000)
• T. Lengauer: Combinatorial Optimization in Circuit Layout Design (Wiley, 1990)
• G.L. Nemhauser and L.A. Wolsey: Integer and Combinatorial Optimization (Wiley, 1988)
• C.H. Papadimitriu and K. Steiglitz: Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, 1982)
• A. Schrijver: Combinatorial Optimization (vols. I-III) (Springer, 2002)
• A. Schrijver: Theory of Linear and Integer Programming (Wiley, 1986, reprinted 1999)
• L.A. Wolsey: Integer Programming (Wiley, 1998)

Stochastic Programming

Instructor: Andras Prekopa

Prerequisites: Probability theory, linear programming

Course Outline:
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.
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.

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.

Pseudo Boolean Functions

Instructors: Endre Boros

Course Outline:
Introduction, definitions and notations.
Examples:
General Pseudo-Boolean Functions - Representations of pseudo-Boolean functions, rounding procedures and derandomization, persistency, local optima, basic algorithm, reductions to quadratic optimization, posiform maximization, l2-approximations and applications to game theory.
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.
Special classes - Sub- and supermodular functions, half-products, hyperbolic pseudo-Boolean functions, products of linear functions.
Approximation algorithms - MAX-SAT and variants, -approximation of MAX-2SAT via roof-duality, -approximation of MAXSAT via convex majorization.

Stochastic Models of Operations Research

Instructor: Prerequisites: Probability Theory (640:477 or equivalent)

Topics:
1. Review of basics in the 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. Kolmogorov equations. Birth and death processes. Stationary distributions. Applications.
6. Renewal theory. Elementary renewal theorem. Renewal equation. Renewal-reward processes.
7. Brownian motion process. Reflection 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: Sheldon Ross, Probability Models, 7th Edition

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

Office hours: After class or by appointment.

Algorithmic Graph Theory and Its Applications

Instructor: Martin Charles Golumbic

Prerequisites: This is a graduate elective course. Students are expected to have mastered basic undergraduate knowledge of algorithms, complexity analysis and discrete mathematics.

Course Outline:
This course will be a self-contained continuation of the course (Part I) given last year. We present classical and more recent theory and algorithms in graph theory, in particular, related to intersection graphs and other related families of graphs. Intersection graphs are an extremely useful mathematical model for many applications in computer science, operations research, and even molecular biology. We begin by explaining and motivating the concept, and provide examples from the literature. The graph coloring problem on special families of these intersection graphs will be studied. Many of these techniques can be applied to scheduling classrooms or airplanes, allocating machines or personnel to jobs, or designing circuits. Rich mathematical problems also arise in the study of intersection graphs. We will present spectrum research results, from simple to sophisticated, which should interest both students and professors. Lectures will be chosen from the following list of topics.
Introduction to Intersection Graphs - [Go1, Mc21]
Review of Basic Graph Algorithms and Complexity Analysis - [Go2, CLR]
Chordal Graphs and their Applications - [Go4, Mc22]
Transitively Orderable Graphs - [Go5, Mc27.6]
Permutation Graphs - [Go7, Mc27.4]
Weakly Chordal Graphs and Strongly Chordal Graphs - [Mc27.3, Mc27.12, Go13]
Split Graphs, Threshold Graphs and CoGraphs - [Go6, Mc2 2.5, Go10 Mc25, Mc27.9]
Interval Graphs - [Go8, Mc23]
Tolerance Graphs - [GT1, GT2]
Interval Probe Graphs - [GT4, Mc23.4.1]
Intersection Graphs on Trees - [GT10, Mc22.3]

Texts:
Go: M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, second edition Elsevier (2004).
Chapters 1; 2; 4:1-4,6; 5:1,4,6-7; 6:1-2; 7:1-2,4-5; 8:1-4; 10*; 13
GT: M.C. Golumbic & A.N. Trenk, Tolerance Graphs, Cambridge University Press (2004).
Chapters 1; 2:1-3,6-7; 4:1-4,7-8; 10* (*optional)

Other references:
MP : Mahadev & Peled, Threshold Graphs and Related Topics
BLS: Brandstadt, Le & Spinrad, Graph Classes: A Survey
Mc2: T.A. McKee & F.R. McMorris, Topics in Intersection Graph Theory
Misc. papers from the literature

Students are responsible for reading all assigned material. Exercises are to be presented in class. Each student will also be expected to concentrate on a paper from the literature to be assigned in class and do a course project or presentation. The exam will be open book, covering the material discussed in the lectures.

Topics in Applied Operations Research

Instructor: Adi Ben-Israel, RUTCOR Bldg., Room 113

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

Desirable background: Nonlinear programming. Some experience in simulation (for example,YASAI).

Course webpage:http://ben-israel.rutgers.edu/711/Course.htm
E-mail:adi.benisrael@gmail.com
Tel: 732-445-5631
Webpage: http://ben-israel.rutgers.edu/index.htm

General: The objectives of the course are (a) to introduce selected models and applications of Operations Research (O.R.), (b) establish (review, and if necessary cover) the theory needed for these applications, and (c) study the human issues (political, cultural, sociological etc.) relevant for implementing and validating a policy.

O.R. is used here in the wide sense, borrowing as needed from Optimization, Probability, Statistics and Computing. Applications are selected because they are representative, important, and/or not covered by other courses offered by our program.

Possible topics and applications:
1. Paradoxes and weird phenomena in probability, statistics and O.R.
2. Location problems, single and multiple facilities.
3. Search engines. The page rank algorithm.
4. Models of risk and uncertainty.
5. Forecasting. Political elections.
6. Trends. Demographics.
7. Systematic climate changes. Policy implications.
8. Nonrenewable natural resources. Optimal rate of extraction. Oil. Coal.
9. Renewable natural resources. Forestry. Fisheries. Agriculture. Solar and wind energy.
10. Health care. Insurance.
11. Epidemics and vaccination models.
12. Dynamic pricing.
13. Traffic systems. Flow. Congestion.
14. Clustering and classification.
15. Bayesian analysis.
16. Statistics and law.
17. Maintenance and replacement policies.

These topics will be studied and illustrated using appropriate case studies and histories (e.g., FEDEX for topic 2, GOOGLE for topic 3, etc.), and selected readings from the research literature.

Course work: Students will choose topics, search the literature, prepare lectures, and present them in a seminar setting starting from the 3rd week of the course.

There will be projects, where groups of students work on actual or hypothetical applications and present their reports. The projects must be finished and presented by the last day of classes.

The grade in the course will be based on the student's participation in class, the seminar presentation, and the project.

Introductory Topics in OR

Course Outline: 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.

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

Nonlinear Optimization

Instructor: Jonathan Eckstein

This course covers numerical optimization problems with nonlinear objective functions or constraints, including necessary conditions for an optimal solution, sufficient conditions for an optimal solution, duality, and numerical solution methods.

Homework problems will be a mixture of theoretical and computer programming (using MATLAB). They will be assigned every one or two weeks. There will be two take-home exams.

Textbook: to be determined

Topics (elements of real analysis will be reviewed as necessary throughout the course)

1. Unconstrained optimization
a. Elements of convex analysis: i. Convex sets; ii. Convex functions
b. Local optimality conditions for differentiable unconstrained problems
c. Line search algorithms
d. Gradient and related methods
e. Algorithm rates of convergence
f. Newton methods
g. Conjugate gradient / quasi-Newton methods

2. Optimality conditions for constrained optimization problems
a. More elements of convex analysis: i. Projection and separation; ii. Cones, polars, and duals;
iii. Recession, feasible direction, tangent, and normal cones
b. Simple abstract optimality conditions for functions and sets
c. Constraint qualifications, metric regularity, and separation
d. Lagrange necessary condition, Lagrangians

3. Langrangian duality for nonlinear optimization

4. Constrained optimization methods
a. Gradient projection methods (possibly expanding on AR:NO)
b. Reduced gradient / feasible direction methods
c. Penalty methods
d. Newton / SQP methods
e. Barrier methods
f. Augmented Lagrangian methods

Queueing Theory

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

Course Outline:
Elements of Stochastic Processes: Definition of a stochastic process; strict and covariance stationarity; ergodicity; discrete time Markov chains; semiMarkov 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.
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.
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; nonpreemptive priorities; optimal priority schemes; SRPF schemes.
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.
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.
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.
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.
Networks:Reversibility, quasi reversibility, symmetric queues and product form (kelly type) networks; nonproduct form networks; approximations and bounds; decomposition and aggregation methods, numerical methods.
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.

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

Game Theory

Instructor: Vladimir Gurvich
Email: gurvich@rutcor.rutgers.edu

Prerequisites: None. Graph theory and linear programming would be useful but not necessary.

Course Outline:
1. Matrix games, max min , min max and saddle point. Pure and mixed strategies. Solvability in mixed strategies. Von Neumann's Theorem for matrix games.
2. Bimatrix and n-matrix games. Nash equilibria and Nash solvability. Perfect equilibria and perfect solvability. Sophisticated equilibria and dominance solvability.
3. Games in extensive, positional and normal form. Perfect information and solvability in pure strategies. Nash solvability of the cyclic games.
4. Domination and dominance solvability. Backward induction. Dominance solvable extensive and secret veto voting schemes.
5. Cooperative games. Coalitions. Transferable and non-transferable utilities, TU- and NTU-games. Cores and core-solvability. Bondareva-Shapley's Theorem and Scarf's Theorem.
6. 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.
7. Intrduction to Social Choice Theory. Paradox Arrow. Social choice functions and correspondences.
8. 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.

Simulation

Course 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

Text: Simulation with Arena (2nd edition), W. David Kelton, Randall P. Sadowski, Deborah A. Sadowski, McGraw-Hill 2002

Semidefinite and Second Order cone Programming

Instructor: Farid Alizadeh

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.

Course Outline:
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.

Student Requirements: Each student is required to take a 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.

Convex Analysis and Optimization

Instructor: Jonathan Eckstein

Office hours: Tuesdays 2:00 - 3:30 PM and by appointment.

Prerequisites: "Basic knowledge of finite-dimensional real analysis: open sets, closed sets, and convergence of sequences."

Course Outline:
Fundamentals of finite-dimensional convex sets and functions. Subgradient mappings, optimality conditions, and Lagrange multipliers. Set-valued monotone operators, conjugate functions, and optimization duality theory. Convex-analytic optimization algorithms such as subgradient, proximal, and bundle methods, including applications to nonconvex/discrete optimization.

Book: "Convex Analysis and Optimization", by Bertsekas, Nedic, and Ozdaglar, details at http://www.athenasc.com/convexity.html

Grading: Grades will be based on two take-home exams and homework assignments given out every one or two weeks.

Linear Programming

Instructor: Andras Prekopa, prekopa@rutcor.rutgers.edu (732-445-5432)
Place and Time: RUTCOR Bld., Room 166, Mon., Thurs., 10:20-11:40AM

Prerequisites: Advanced linear algebra

Topics:
The n-dimensional Euclidean space, convex polyhedra. The problem of linear programming, bases, basic solutions, characterization of vertices. The simplex method. Duality theory. Linear programming proofs of von Neumann's game theoretical minimax theorem and linear inequalities theorems: Farkas, Haar, Gordan, Stiemke. The dual method. Solutions of special linear programming problems: Dantzig-Wolfe decomposition, Benders' decomposition, Gomory's all integer algorithm, assignment problem, transportation problem.

Grading: Will be based on the results of one midterm exam (30%), one final exam (40%) and 5 sets of homework problems (30%).

Lecture notes: Copies of the slides will be available for the students.

Office hours: After classes or by appointment.

Financial Mathematics

Instructor: Andras Prekopa

Prerequisites: Probability Theory, Linear Programming.

Course Outline: 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 PDEs 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. A. Prekopa, Stochastic Programming, Kluwer, 1995.
3. 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.

Theory of Linear Optimization

Instructor: Jinwook Lee
Office Hours: BA, or after class (room 143, RUTCOR building)

Prerequisite: 01:640:250 Introductory Linear Algebra

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.

Students will have the chance to apply the methods to real life problems. One of the aims of the course will be to teach the students the path: from real life problem to abstraction, to mathematical formulation, to solving the mathematical problem, to applying this solution in the real life framework.

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

Data Mining and Modeling and Its Applications in Engineering and Operations Research

Course 16:540:694 (CRN: 76385)
Instructor: Dr. Myong K. (MK) Jeong (mjeong@rci.rutgers.edu;www.rci.rutgers.edu/~mjeong)
Class time and place: Fri 1:40 –4:40 pm, SEC 207

Prerequisites: Linear programming, introductory statistics
Textbooks: No textbook is required and class materials will be provided by the instructor.
Grading: Homeworks and class project

Topics (The topics and level of their coverage will be determined based on the background and interests of the audience)

Data Mining Overview: Concepts, overview of main data mining tools, applications of data mining

Classification: Bayesian decision theory, Bayesian classifier; Linear (quadratic, flexible, regularized) discriminant analysis; Logistic regression model; Regularization (ridge regression, Lasso, and others); Mathematical programming for classification

Regression: Loss functions; Regularization (penalization), bias, variance, and model complexity; Ridge regression, Lasso, and others); Variable selection in regression, AIC, BIC, ICOMP; Robust regression

Clustering: Similarity measures; K-means, K-medois, Kernel K-means; Spherical K-means; Gaussian mixture models; Probabilistic clustering; Assessment of clustering results (validity index, internal/external criteria); Fuzzy clustering; Mathematical programming for clustering

Anomaly Detection (or Novelty Detection): One-class classification problem; Support vector data description; PCA data description

Feature Selection: Metrics and distance functions depending on data types (numeric, text, …); dynamic time warping (DTW); Distance between probability distributions (e.g., divergence); separability measures; Optimization methods for feature selection: branch and bound method, floating search, genetic algorithms; Other research issues: SVM-based feature selection, huge-scale feature selection

Kernel-based Methods for Classification, Regression, and Anomaly Detection: Support vector machines for classification; Kernel trick; Mercer’s theorems; Convex optimization; Gaussian processes; Relevance vector machine; Extension of kernel-based approaches to PCA, PLS, CCA, and others

Logical Analysis of Data (LAD) for Classification: Introduction of LAD and optimization models for LAD; Current research issues in LAD; Logical Analysis of Data (LAD) for Regression

Tree-based Methods: Classification and regression trees (CARTs); Variants of CARTs; Comparison between LAD and CARTs

Function approximation: Basis expansions; Splines; Wavelets

Transformation for Feature Extraction, Dimensionality Reduction: Principal component analysis (PCA), probabilistic PCA, principal curves and surfaces; Partial least squares (PLS), independent component analysis (ICA); Latent variables and factor analysis; Multidimensional scaling; Kernel-PCA, Kernel-PLS

Chemometrics: Spectra (or time series) data analysis; Preprocessing of data and dimensionality reduction; Feature extraction and selection with spectra data

Ensemble Methods: General idea; Bagging; Boosting (AdaBoost)

Image Data Mining: Introduction of hyperspectra image data, band selection and other research issues; fMRI data analysis and applications

Spatial Data Mining: Join counts; Spatial correlogram; Kriging; Markov random field

Other topics: Reinforcement Learning; Graphical models (Bayseian networks); Association rule, Recommendation systems; Sampling methods (MCMC, Importance sampling); Hidden Makov models; Neural networks;

Monte Carlo Simulation

Instructor: Istvan Deak, Room 103 (Email: istvan.deak@uni-corvinus.hu)
Place & Time: RUTCOR bld., Room 139, Wed., 9:00 - 12:00 Noon

Prerequisites: Probability Theory (640:477 or equivalent)

Topics: This course contains materials from three areas: random number generation, Monte Carlo methods and some problems, where the use of Monte Carlo methods is required.

Part A. Random number generation
1. Summary of probability theory.
2. Concepts of randomness, natural, quasi and pseudorandom numbers and generators.
3. Methods for generating uniform random numbers.
4. General methods for sampling from arbitrary distributions (discrete and continuous).
5. Methods for specific distributions (power distributions, normal, exponential, gamma).
6. Methods for generating vectors.

Part B. Monte Carlo methods
7. Crude method, and acceptance rejection.
8. Errors and comparison of methods, efficiency.
9. Variance reduction: importance sampling, stratification, control and antithetic variates

Part C. Case studies
10. Computing the multidimensional normal distribution function and related probabilities (Deak, Szantai).
11. Simulational techniques in optimization (random search, evolutionary techniques, simulated annealing, system simulation).
12. Computing the volume of convex bodies (Lovasz, Vempala).
13. Successive regression approximations for solving stochastic programming problems (Deak).

Books:
1. I. Deak: Random number generators and simulation, in: Mathematical Methods of Operations Research (series editor A.Prekopa), Akademiai Kiado (Publishing House of the Hungarian Academy of Sciences), Budapest, 1990.
2. J.M. Hammersley, D.C. Handscomb: Monte Carlo methods, Methuen, London, 1964.
(A list of relevant papers will be given to the students.)

Grading: Based on the homework, a presentation, and an oral exam.

Office hours: After class or by appointment.

Design & Analysis of Computer Algorithms

Instructor: Michael D. Grigoriadis, Department of Computer Science, CoRE 308;
(732) 445-2001, Ext 2898; Off.Hrs: TBA & by appointment. Email:grigoriadis@cs.rutgers.edu

Lectures: T 12-3 at SEC-218. Recitations: -Th 1:55-2:50 at Hill-005.
- Lectures & recitations: Attendance is required, with all personal electronics turned off.
- Student Absences are tracked by the SAS Dean's Office: If you expect to miss one or two classes, use this secure University Self-Reporting App to report the date and the reason for your absence.
An email is then sent to me by the Dean's Office.

Course Objectives: Fundamental techniques for designing efficient combinatorial algorithms.
Mathematical methods for analyzing their correctness and complexity. Applications.

Prerequisites: 198-112, and 198-206 (or 01:640-477), (and thus Calc II). We also assume elements of discrete mathematics, such as logarithms, proofs by induction, series and sums, permutations, asymptotics (big-Oh, big-Omega notation), basics of solving recurrences, as well as concepts of programming and data structures, e.g., linked lists, stacks, queues, trees, binary search, recursion, hashing, priority queues, graph algorithms, sorting.

Topics: We will cover a large subset of the following and possibly some new algorithmic topics and applications, as time permits:
Mathematical tools. Review of mathematical background, concepts of algorithm design, complexity, asymptotics, induction, and randomization. Fibonacci numbers. Euclidean gcd algorithms. Universal hashing.
Graph search. Graph classes and representations; depth first search in undirected and directed graphs; topological search; strongly connected components. Breadth first search and layered DAGs.
Shortest Paths (SPs) in digraphs. Single-source SPs for nonnegative edge weights; priority queues and Dijkstra; SPs in DAGs; single-source SPs for general edge weights. Maximum adjacency search.
Greedy algorithms. Spanning trees and cuts, analysis of union-find and path compression; MST algorithms; randomized algorithm for global minimum cuts; approximate set cover.
Network flows. Max flow min cut theorem and integrality; fast algorithms; disjoint (s,t)-dipaths; maximum bipartite matching & minimum vertex cover. Global minimum cuts.
Divide and conquer. Fast integer multiplication; recurrences; the master theorem; mergesort; randomized median and selection algorithms; quicksort; fast matrix multiplication.
Sorting. Lower bounds for comparison-based sorting; binsort and radix sort.
Dynamic programming; Paradigm of SPs in DAGs; longest increasing subsequence; approximate string matching; integer and (0,1) knapsack problems; chain matrix multiplication; single-pair reliable SPs, all-pairs SPs; independent sets.
Elements of NP-completeness & problem reductions.
NP-hard problems. Search and selected approximation algorithms.

Textbook: Algorithms, Dasgupta, Papadimitriou & Vazirani, McGraw Hill, 2008 (paperback or download for kindl, etc.), supplemented by class notes and handouts. The book in now at RU bookstore. Errata here!. (Read the Prologue chapter before the first class from the author's public draft.)
Reference: Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein, McGraw Hill. The second edition (2001) will be on reserve at SERC, with errata here. The 3rd (2009), is optional for this course.

Required work: Assigned reading; working on handouts and exercises suggested in lectures; keeping your own class notes; weekly or biweekly homework problem sets and pop quizzes, two midterms and a final exam. Come to lectures prepared to participate in class. HW assignments are mathematically oriented and involve derivations of mathematical equations, proofs, and running time analyses of algorithms. HW submissions are by these HW rules, and require individual work.

N.B.: Experience shows that students who stay engaged, keep up with the suggested or assigned reading, follow up on the practice problems suggested in lectures, participate in class, and diligently do the assigned homework spread over a few days, do quite well in this course. Remember: Cramming for tests is a losing strategy!

Resource Allocation: Models, Algorithms, and Applications

Instructor: Hanan Luss
Location: Room 139 or 166, RUTCOR Building

Prerequisites: Linear Programming, basic knowledge of nonlinear and integer programming. Course Outline: This graduate course (for PhD and qualified MS students) examines diverse resource allocation problems, where a limited amount of resources are allocated among competing activities. We focus on models with significant special mathematical structures, where the corresponding formulations can be exploited and solved by elegant, computationally efficient algorithms. Most of the course will emphasize diverse equitable resource allocation models, where numerous resources are allocated fairly among competing activities.

Sample of topics that will be covered include: (i) Framework of resource allocation models and, in particular, of equitable resource allocation. (ii) Allocation of a single resource among competing activities while maximizing the sum of concave return functions; (iii) Equitable allocation of multiple resources among competing activities (lexicographic minimax/maximin optimization); (iv) Extensions to allocation of substitutable resources; (v) Extensions to multi-period resource allocation; (vi) Equitable allocation of resources in multi-commodity network flows; (vii) Equitable content distribution in networks (e.g., video-on-demand); and (viii) Equitable resource allocation with discrete decision variables. We will explore the use of these models and algorithms in the context of various application areas, including logistics, communication networks, and facility location.

References: H. Luss, Equitable Resource Allocation: Models, Algorithms, and Applications, under preparation 2012 (book draft). T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches, The MIT Press, 1988. N. Katoh and T. Ibaraki, Resource Allocation Problems, in D-Z. Du and P. M. Pardalos (Editors), Handbook of Combinatorial Optimization, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998 (survey). H. Luss, On Equitable Resource Allocation Problems: A Lexicographic Minimax approach, Operations Research 47, 361-378, 1999 (survey). M. Patriksson, A Survey on the Continuous Nonlinear Resource Allocation Problem, European Journal of Operational Research 185, 1-46, 2008 (survey). A variety of published papers.

Stochastic Networks

Instructor: Michael Tortorella(mtortore@rci.rutgers.edu) Room 148, RUTCOR Bldg.

Office Hours: Thursdays 2-3 PM or by arrangement.

Synopsis: Networks underlie almost every facet of modern life. Telecommunications, electricity, oil and gas and water distribution, and logistics networks are but the most obvious examples. Network theory has also been fruitfully applied in biology, sociology, and finance. When demands on the network are random and/or elements of the network are unreliable, network design and performance analysis techniques need to be expanded to incorporate these essential features. This course provides an introduction to network design and performance analysis problems and solutions in stochastic networks.

Topics: Foundations, review of graph theory and stochastic processes. Survey of random graph theory. Network design and optimization. Flows in networks with unreliable elements. Queueing network models. Heavy traffic limit theorems. Incorporating unreliable network elements. Cross-network delay models. Path set and cut set models for capacitated stochastic networks. Network resiliency. Service reliability.

Prerequisites: Working knowledge of graph theory and stochastic processes

Books: R. F. Serfozo , Stochastic Networks. Springer 1999. (tentative) L. Kleinrock, Communication Nets. Dover 2007.

Grading: Based on a presentation made by the student on a paper or book chapter relevant to the course. Each student will choose his/her own material with consent of the instructor.