CSL 865: Special Topics in Computer Applications (Optimization)

 

Instructor: Naveen Garg, Room 409, CSE

 

Midterm Exam (Exam is due on Tuesday, Oct 9, at 10am in my mailbox)

Endterm Exam (Exam is due on Wednesday, Dec 5 at 10 am in my office)

Michael Trick's course notes (endterm exercises can be found here)

 

Contents: (Preliminary)

Preliminaries

  1. Linear Algebra
  2. Functions of One Variable
    1. Derivatives
    2. Maximum and Minimum
    3. Binary Search
    4. Convexity
  3. Functions of Several Variables
    1. Gradient
    2. Maximum and Minimum
    3. Global Optima

 

Optimization with Constraints

  1. Equality Constraints (Lagrangians)
    1. Geometric Interpretation
    2. Economic Interpretation
  2. Equality and Inequality Constraints

 

Linear Programming

  1. LP modeling/Solver
  2. The Simplex Method
    1. Linear Programs in Standard Form
    2. Solution of Linear Programs by the Simplex Method
    3. Alternate Optimal Solutions, Degeneracy, Unboundedness, Infeasibility
  3. Sensitivity Analysis
    1. Cost Changes
    2. Right Hand Side Changes
    3. New Variable
  4. Solving large Linear Programs
    1. Capital Budgeting
    2. Cutting Paper
    3. Decentralized Decision Making
    4. Dantzig-Wolfe Decomposition
    5. Airline Crew Scheduling

 

Integer Programming

  1. Modeling with Integer Variables
    1. Knapsack
    2. Set Covering, packing and partitioning
    3. Traveling Salesman Problem
  2. Solving Integer Programs
    1. Relationship to Linear Programming
    2. Branch and Bound
    3. Cutting Plane Techniques

                                                               i.      General Cutting Planes

                                                              ii.      Cuts for Special Structure

  1. Heuristics

 

Dynamic Programming

  1. The Knapsack Problem.
  2. An Alternative Formulation
  3. Equipment Replacement
  4. The Traveling Salesperson Problem
  5. Non-additive Recursions
  6. Stochastic Dynamic Programming
    1. Uncertain Payoffs
    2. Uncertain States
    3. ``Linear'' decision making

 

Network Models

  1. Shortest Paths
  2. Maximum Flow
  3. Transportation Problem
  4. Assignment Problem
  5. Unifying Model: Minimum Cost Network Flows
  6. Generalized Networks

 

Decision Theory

  1. Decisions Under Risk
  2. Decision Trees

 

Game Theory

  1. Two-Person Games
    1. Pure Strategies
    2. Mixed Strategies
  2. n-Person Games

 

Data Envelopment Analysis