Course Announcement:
CSCI 5654:
Linear Programming, Fall 2000

Time

Tu Th 2:00  3:15, ECCR 1B14

Instructor

Hal Gabow, ECOT 624, X26862 (or 3330072)
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 12 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 realworld 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 cuttingstock 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. Polynomialtime LP

ellipsoid algorithm &
Karmarkar's algorithm