# 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.