Course Announcement:
CSCI 5654:
Linear Programming, Fall 2000
-
Time
-
Tu Th 2:00 - 3:15, ECCR 1B14
-
Instructor
-
Hal Gabow, ECOT 624, X2-6862 (or 333-0072)
hal@cs.colorado.edu
-
Prerequisites
-
Undergraduate linear algebra (CSCI 2830, APPM 3310, MATH 3130) &
data structures (CSCI 2270), or their equivalents
-
Requirements
-
Written problem sets; also 1-2 programming assignments, and 1 reading
project.
-
Texts
-
-
Linear Programming
by V. Chvatal,
W.H. Freeman and Co., 1983.
-
A collection of class notes written by the instructor
-
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