CS 6301-002: Linear Programming

ECSS 2.203 F: 10:00 -- 12:45

Instructor: R. Chandrasekaran

Office: ECSN 4.622 (???)

Phone: (972) 883-2032 E-mail: chandra@utdallas.edu
Office Hours: W: 2:00-4:00
URL: http://www.utdallas.edu/~chandra

Teaching Assistant :

Office Hours:

email:

Class Room: ECSS 2.203

Prerequisites: CS 6363 ; or consent of the instructor.

Grading Scheme

Homework and presentations (Schedule TBA)

Course Outline:

Linear Programmingr

Introduction
Formulations of well known problems

Linear Algebra
Linear Independence
The Simplex Algorithm and Two Phases of the Simplex Method
Simplex Algorithm in Matrix Form
Revised Simplex Method
- Explicit Inverse
- Column Generation
Sensitivity Analysis and Parametric Programming
Bounded Variables and Separable Programming

Algebra: Theory and Algorithms

Duality Theory
Algorithms Based on Duality
- Dual Simplex
- Self Dual
- Primal Dual
Linear Inequality Theory and Theorems of the Alternative
Fourier Elimination

Convexity
Adjacent Vertex Methods and Fractional Programming
- Charnes-Cooper
- Isbell-Marlowe
- Martos-Charnes
- Dinkelbach-Jagannathan

Extensions

Convex Quadratic Programs and Linear Complementarity

Special Linear Programs

Network Problems and Total Unimodularity
Large LP
- Decomposition Principle
- Generalized Upper Bounding

Polynomial Algorithms

Ellipsoid Algorithm
Interior Point Methods

Solvable Cases of Integer Programs

Unimodular Matrices
Matching and Local Unimodularity
Matroids and matroid intersection
Circular Ones and its Generalizations and Lattice Optimization
TDI Systems: Balanced Matrices, Blocking Systems and Polyhedra, Perfect Graphs
Nonnegative integer solutions to linear systems
Approximations to Knapsack and Scheduling Problems.
Hilbert Basis and its uses.
Pseudomatroids

Geometry of Numbers

Introduction
Lattice Basis Reduction Techniques
Lenstra's Algorithm
Scarf's Work
Tardos - Frank Simultaneous Approximation
Other Applications

Assignments

Click here to go back ...