WILLIAM PATERSON UNIVERSITY OF NEW JERSEY
COLLEGE OF SCIENCE AND HEALTH
Department of Computer Science Syllabus and Outline
Course: CS330-60, Linear Programming and Operations Research
Tuesday & Thursday 5:00AM - 6:15AM, Hunziger 209
Instructor: Dr. John Najarian, Assoc. Prof. of Computer Science
Office: Coach House 205, Tele. (973)-720-2952
Office Hours: Tuesday & Thursday 12:30PM-3:15PM
Wednesday 6:00PM-6:45PM & also by appointment.
Last day for course withdrawal 3/3/99. Classes: 1/11/99-4/30/99.
Holidays: 1/18/99 MLK, 2/15/99 GW, 3/8/99-3/13/99 SB, 4/2/99 GF,
Tuesday 2/16/99 is a Monday schedule.
Final Exam. Period: Tuesday, 5/4/99, at 5:00PM-7:30PM
Class Rules:
1. Attendance will be recorded. Departmental guidelines require
that: 3 absences (2 for night)--> departmental warning letter
7 absences (4 for night)--> automatic failure in course
Only valid excuses (in writing) allay these consequences.
Attendance and success coincide.
2. Projects will be collected as scheduled.
3. All quizzes will be announced at least 1 full week in advance.
If you are absent on the day a quiz is announced, you are
responsible for finding out about it from a fellow student or
the professor. No make-up exams will be given except for
extraordinary circumstances.
4. Bring the specified textbook to each class session.
5. Before lab sessions, read relevant text; optimize productivity.
6. Final Grade = Projects (40%) + Average of 3-5 Quizzes (60%)
Objective of Course:
To introduce the concepts of operations research & optimization
techniques as applied to decision-problems. Primary areas are linear-
programming (LP) and basic non-linear-programming (NLP), followed
by dynamic- and combinatorial-programming, subset algorithms,
game theory, Markov chains, and stochastic optimization.
These methods are applied in the modelling & solution of realistic
problems in engineering systems, the sciences, and other diverse fields,
such as in farm-land usage, manufacturing, resevoir management, network
throughput, circuitry, OS performance, caches, industries, engineering
designs, gambling, optimal stochastic investments, transportation,
assignment, resource allocation, scheduling problems, etc.
Topics include: Search procedures, middle-level complexity,
objective functions, optimality conditions, feasibility, constraints,
matrix theory, Simplex Methods (classical and several variants),
convexity, pathological conditions, and non-linear systems
theory are developed as foundations for algorithm design and analysis.
Fast subclass-algorithms for special problems like transshipment are
covered. Geometric interpretations are considered. Term papers review
recent results (eg. Karmarkar's polynomial-time interior methods).
C/C++ will be used as the programming language. Important
data structures and programming methodologies are assessed. Efficiency
and trade-offs are evaluated. Programming and debugging experience is
reinforced by hands-on sessions and programming projects. The INTERNET
will be used to access some specialized optimization programs. TORA,
under Windows NT 4 experiments will provide pedagogical support.
2 sessions = 1 week
Session & Topic (Tentative Schedule) Chapter
------------------------------------ -------
1 Introduction: Overview, What is Profit and can we Taha 1
make it without constraints? Optimization. $$$
(Definitions: Vector, Review of Matrices) Taha App A.1
2 Matrix Review, Inverses, Gauss-Jordan, Rank, Indep Taha 1&App A.2
3 Applications: Setting-Up Systems and Modelling; Taha 2
4 Further Exploits in Setting-Up Models: Word Prob. Taha 2
Interpretting Subset Problems as L.P.'s, Graphing
5 Linear Programming (LP): Set-up, Slack Variables, Taha 2
Standard Forms (= vs <>=), Init. Feasible Sol.
6 LP: Theory of Solutions, Change of Basis, TORA, Taha 2
Walking on the Edge, Basic vs Feasible My dandy demo
7 The SIMPLEX METHOD: More of Life on the Edge, Taha 3
Geometric Interpretation, Polytopes
8 Computing with the SIMPLEX METHOD: Examples Taha 3
Time Complexity Issues of LP & Recent Results Lab Handouts
9 Quiz # 1 (Zoology, Set-Up, LP, Simplex)
10 Subset Algorithms: Transportation in a Network Taha 5
11 Subset Algorithms: Scheduling (i.e. Production, Taha 5
Assignment, Traveling Salesmen) except 5.5
12 Subset Algorithm Review Taha 6
13 Network Models: Introduction Taha 6
14 Network Models: Shortest Path, Max Flow Taha 8
15 Network Models: CPM and PERT, Min Span Tree Taha 8
16 Review
17 Quiz # 2 (Subset Algorithms,)
18 Non-Linear Programming: NLP (1d Search), Yippie Taha 20,
Unconstrained NLP, 3-Way Bisection, Golden Section
19 NLP: (2d & Up Greedy Search); Surface Life Taha 20, 21
(Bisection is exponential time in num of dim)
Conditions, and Definitions
20 NLP: Gradients and Steepest Ascent Taha 21
21 NLP: More Steepest Ascent Taha 21
22 Lagrange Multipliers Taha 21
Summary Review
23 Quiz # 3 (NLP)
24 Deterministic Dynamic Programming & Reductions Taha 10
25 Dynamic Programming and Basics of Combinat. Prog. Taha 10
26 Decision/Uncert: Proc., Criteria, Trees, Utility Taha 12, 14
27 Decision/Uncert: More Decision Trees, Intro. Games Taha 12, 14
28 Markov Chains Taha 19
29 Markov Chains Taha 19
30 Review
31 Quiz # 4 (Staged Decisions (DP) & Probabilistic Models)
Required Text:
Taha, Hamdy A. [1997] "Operations Research: An Introduction",
Sixth Edition, Prentice-Hall
Diskettes (provided by the Computer Science Dept.) will be distributed.