Course Announcement:

CSCI 5654: Linear Programming, Fall 2000

Tu Th 2:00 - 3:15, ECCR 1B14
Hal Gabow, ECOT 624, X2-6862 (or 333-0072)
Undergraduate linear algebra (CSCI 2830, APPM 3310, MATH 3130) & data structures (CSCI 2270), or their equivalents
Written problem sets; also 1-2 programming assignments, and 1 reading project.

Course Description
This course is an introduction to the linear programming model. We define the model and show why it is useful -- its practical applications to solving real-world industrial problems, plus its theoretical applications in geometry, mathematical inequalities, game theory and economics. We develop the simplex algorithm, its refinements, and theoretical underpinnings. We also study Karmarkar's interior point algorithm.
Topical Outline
Unit A. Simplex Method
basic method, sore spots, review of linear algebra
geometric interpretation, revised simplex method
Unit B. Examples
from forestry, farming, factory scheduling, the cutting-stock problem, ...
Unit C. Duality
theorem of duality, complementary slackness
dual simplex method, economic interpretation of duality
Unit D. Refinements
sensitivity analysis, parametric programming, bounded variables
Unit E. Polynomial-time LP
ellipsoid algorithm & Karmarkar's algorithm