| 16:198:521
|
LINEAR PROGRAMMING Fall 2008 (3 cr; DCS Cat. A course)
|
|
|
(Detailed class syllabus)
|
| Instructor
|
Michael D. Grigoriadis, CoRE 308, 445-2001 Ext 2898; Off Hrs: 5-7pm
(tentative); 
|
| TA
|
Jihui Zhao: Hill 403, (732) 445-2001 Ext 9565; Off Hrs: M and
W 3-4 pm; email: zhaojih (at) cs (dot) rutgers (dot) edu.
|
|
Schedule
|
M 1:40-4:40 pm at Hill 254.
|
| Prereqs
| DCS graduate study admission requirements or permission of
Instructor.
(Desirable math background: Undergraduate linear algebra
(important!), roughly equivalent to our Math 01:640:250 or
Professor Strang's LA course);
elements of multivariable calculus, such as partial derivatives and
Taylor series.)
|
| Topics
|
•
Introduction:
Systems of linear inequalities (LI) and linear
programming (LP). Canonical and standard LP forms.
Size of an instance and complexity.
Examples: Production mix, data fitting,
shortest paths, mean cycles, max flows, bipartite matching, min-cost
flows, multicommodity flows; LP's of exponential size: minimum
spanning trees, general weighted matching, TSP.
|
|
|
•
Duality:
Fourier-Motzkin elimination for LI and LP; worst-case
performance. Farkas' lemma and variants; theorems of the
alternative. Karush-Kuhn-Tucker optimality conditions; geometric
interpretation. Duality theory; von Neumann's min-max theorem.
Matrix games.
Applications in data fitting. Binary classification in
pattern recognition. The primal-dual schema and approximation
algorithms.
|
|
•
Geometry of polyhedra.
Fundamental theorem of LP. Polyhedra and polyhedral cones; vertices,
edges, facets; recessive directions; basic feasible solutions and
extreme points. Representation theorem. Theorems of Minkowski, Weyl,
Caratheodory and Helly.
|
|
•
Simplex:
The (revised) simplex method: monotonicity, degeneracy, cycling;
lexicogrsaphic and Bland's pivoting rules for finite termination.
Worst-case performance, Klee-Minty instances. The Hirsh conjecture.
Sensitivity and parametric programming. The (revised) dual and
primal-dual simplex methods. Total unimodularity and
network simplex algorithms.
|
|
•
Large-scale programming:
Column and row generation; cutting stock;
Lagrangian relaxation and potential reduction approximation
schemes. Fractional packing and covering models.
|
|
• Polynomial algorithms: The ellipsoid
method; complexity and precision; theoretical significance; the
separation problem; combinatorial problems with exponentially
many constraints; applications. Overview of interior-point methods:
Karmarkar's projective scaling; logarithmic barrier reduction and
primal-dual path-following Newton methods; complexity and
precision. Computational issues.
|
|
•
Note: Emphasis on some topics varies somewhat from semester to
semester.
|
|
Sources
|
1) Book: Introduction to Linear
Optimization by D.Bertsimas
& J.N.Tsitsiklis,
Athena Scientific (1997), at RU bookstore
(check
errata here);
2) Class notes,
3) Advanced reference:
Theory of Linear and Integer Programming
A. Schrijver, Wiley-Interscience (1986, paperback), and
4) papers from the literature.
|
|
Add'l sources
|
Linear Programming by V. Chvatal, W.H. Freeman & Co.(1983);
Primal-Dual Interior-Point Methods, S.J. Wright, SIAM Pubs,
(1997, paperback), LP Review by Goldfarb and Todd, Chapter 2 in
Handbooks in OR/MS, Vol. 1 (Nemhauser et al. Eds.)
Elsevier-North Holland (1989), and other material
posted or placed on reserve at MSL, Hill Center.
|
|
Expected work
|
Suggested reading. Five problem sets.
One midterm and a (cumulative) final exam.
Optional computational miniproject.
|
|
Grading
|
Guideline: 0.15HW + 0.35MT + 0.50FIN
|
| Policies
|
•
About academic integrity.
•
Attendance is required and class participation is expected.
•
About Homework.
HOW TO EFFICIENTLY RESOLVE ANY
AND ALL GRADING ISSUES
|
|
Dates
|
Classes: Mondays 1:40-4:40 pm. at Hill 254
80-minute Midterm: NOV 2, 1:40pm at Hill 254. No makeups.
Three hour (cumulative) Final: Dec 15, 1:40pm at Hill 254. No makeups.
|
|
|
|
FAQ on LP
|
here
|
|
Practice computing
|
One or two optional hands-on exercises/miniprojects
will introduce you to aspects of LP modeling and computation.
Sign up with the Instructor by Lecture #3.
Every CS521 student has account privileges on our Sun Solaris-based
grad machines cluster
(open account here).
The relevant tools on this platform are:
1) matlab (e.g., see primers pr1,
pr2,
pr3),
2) the popular commercial-grade optimization software cplex
(for interactive cplex, type "cplex" and then "help" at the unix prompt,
also see overview;
for more sophisticated usage, see e.g.,
callable subroutine library reference), and 3) our CS521 easy-to use
MATLAB-CPLEX interface cpx521. An less efficient
but simple alternative matlab-based
access is our lp521
Linking details will be posted in
Announcements.
Note: It is best to use our grad machines
for miniprojects so that we may be able assist you.
/TD> |
|
RU links
|
Academic Calendar,
Registrar's Calendar,
Final Exams Schedules, Closings
& Status.
|