CS 7301: Optimization: Linear
and Integer Programming
Instructor: R. Chandrasekaran
Office: ECSN 4.622 (Please Note: This is in the "old" building!!
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:
email:
Class Room: ECSS 2.201: TR 11:00 -- 12:15
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
Geometry
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 ...