| 16:198:521
|
LINEAR PROGRAMMING Fall 2011 (3 cr; DCS Cat. A course)
|
|
|
(Detailed class syllabus)
|
| Instructor
|
Michael D. Grigoriadis, CoRE 308,
(732) 445-2001, Ext 2898;
Off.Hrs: MW 12-1, W 3:15-4 & by appointment.
|
| TA:
|
Saehoon Yi, CBIM cubicle J, (732) 445-2001 Ext 9690;
Off Hrs at Hill 403: Tue&Thu 12:30-1:30 and
by appointment; shyi [at] cs.rutgers.edu
|
|
Lectures:
|
M&W 1:40-3:00 pm at Hill 254.
|
| Prereqs
| DCS graduate study admission requirements
(¶ 3.1), or permission of Instructor.
(Elementary material from Linear algebra such as
Math250,
from multivariable calculus, and
from analysis of algorithms such as
CS344.)
|
| Topics
|
•
Introduction:
Systems of linear inequalities (LI) and linear
programming (LP). LP forms.
Size of an instance and complexity.
LP models: 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; complexity analysis.
Farkas' lemma and other 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 and 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,
extreme points and directions.
Representation theorem. Theorems of Minkowski, Weyl,
Caratheodory and Helly.
|
|
•
Simplex:
The (revised) simplex method: monotonicity, degeneracy, cycling;
finite termination, lexicographic and Bland's pivoting rules.
Worst-case performance, Klee-Minty instances. The Hirsh conjecture.
Sensitivity and parametric programming. (Revised) dual and
primal-dual simplex methods. Total unimodularity.
Network simplex.
|
|
•
Large-scale programming:
Column and row generation; cutting stock;
Lagrangian relaxation and potential reduction approximation
schemes. Fractional packing and covering.
|
|
• Polynomial algorithms: The ellipsoid
method; complexity and precision; theoretical significance; the
separation problem; combinatorial problems with exponentially
many constraints such as TSP; applications. Overview of interior-point methods:
Karmarkar's projective scaling algorithm; 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
|
Lectures draw material from various cited sources and class handouts.
Textbook: Introduction to Linear Optimization by Bertsimas
& Tsitsiklis, Athena Scientific (1997), at RU bookstore
(errata here);
Additional sources:
Linear Programming by Chvátal, Freeman & Co (1983, paperback),
Theory of Linear and Integer Programming
by Schrijver, Wiley-Interscience (1986, paperback); also parts of his Combinatorial Optimization- Vol. A, Springer (2003);
Primal-Dual Interior-Point Methods, S.J. Wright, SIAM Pubs,
(1997, paperback);
Linear Programming and Network Flows by Bazarra, Jarvis & Sherali, Wiley (1990);
LP Review by Goldfarb & Todd, Chapter 2 in
Handbooks in OR/MS, Vol. 1 (Nemhauser et al. Eds.)
Elsevier-North Holland (1989). Papers from the literature.
These and other sources will be
placed on reserve at MSL, Hill Center, or accessed online.
|
|
Expected work
|
Suggested reading and class participation.
Four HW problem sets.
One midterm and a (cumulative) final exam.
Optional computational miniproject.
|
|
Grading
|
We use this as a guideline: 0.15HW + 0.35MT + 0.50FIN.
|
| Policies
|
HOW TO EFFICIENTLY RESOLVE ANY
AND ALL GRADING ISSUES
•
Attendance is required and class participation is expected.
•
Please be sure to power down all your electronics during lectures and exams..
•
About academic integrity at Rutgers.
•
About Homework.
|
|
Dates
|
Classes:
Sep 7,8,12,14,19,21,26,28;
Oct 3,5,10,12,17,19(MT),24,26,31;
Nov 2,7,9,14,16,21,28,30;
Dec 5,7,12;
Midterm (80 mins): Nov. 2, 1:30pm at CoRE 301.
Closed book/notes.
(Optional: One side of an 8.5x11" sheet of paper of your own handwritten
notes (aka cheat sheet). No makeups.
Final (cumulative, 3 hrs): Dec 14, 1:40pm at CoRE 301.
Closed book/notes.
(Optional: Both sides of your cheat sheet). No makeups.
|
|
|
|
FAQ on LP
|
NEOS wiki
|
|
Practice computing
|
One or two optional hands-on exercises/miniprojects
would introduce you to aspects of LP modeling and computation.
You may sign up with the Instructor by Lecture #5.
Every CS521 student has account privileges on our
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)
A less efficient
but simple alternative matlab-based
access is our lp521
Linking details for lp521 will be posted in
Announcements.
You may also use other packages to experiment in a similar manner.
|
|
RU links
|
Academic Calendar,
Standard
periods,
Misc.Registrar's_Links
& NB campus operating status.
|