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