This course will cover the very basic ideas in optimization. Topics include the basic theory and algorithms behind linear and integer linear programming along with some of the important applications. We will also explore the theory of convex polyhedra using linear programming.

Linear Programming (LP) is arguably one of the most important optimization problems in applied mathematics and engineering. The Simplex algorithm to solve linear programs is widely regarded as one among the "top ten" algorithms of the 20th century. Linear Programs arise in almost all fields of engineering including operations research, statistics, machine learning, control system design, scheduling, formal verification and computer vision. It forms the basis for numerous approaches to solving hard combinatorial optimization problems through randomization and approximation.

The primary goals of this course will be to:

1. Understand the basic theory behind LP, algorithms to solve LPs, and the basics of (mixed) integer programs (ILP).

2. Understand important and emerging applications of LP and ILPs to economic problems (optimal resource allocation, scheduling problems), machine learning (SVM), and combinatorial optimization problems.

At the end of the course, the successful student will be able to cast various problems that may arise in her research as optimization problems, understand the cases where the optimization problem will be linear, choose appropriate solution methods and interpret results appropriately.* This is generally considered a useful ability in many research areas.*

**Introductory Material **

- Introduction to Linear Programming.

- The Diet Problem.
- Linear Programming Formulations.
- Tutorials on using GLPK (AMPL), Matlab, CVX and Microsft Excel.
- The Simplex Algorithm (basics).

- Handling unbounded problems
- Degeneracy
- Geometry of Simplex
- Initializing Simplex.
- Cycling and the Use of Bland's rule.

- Duality: dual variables and dual linear program.
- Strong duality theorem.
- Complementary Slackness.
- KKT conditions for Linear Programs.
- Understanding the dual problem: shadow costs.
*Extra:*The revised simplex method.

- Advanced LP formulations: norm optimization.
- Least squares, and quadratic programming.
- Applications #1: Signal reconstruction and De-noising.
- Applications #2: Regression.

- Integer Linear Programming.
- Integer vs. Real-valued variables.
- NP-completeness: basic introduction.
- Reductions from Combinatorial Problems (SAT, TSP and Vertex Cover).
- Approximation Algorithms: Introduction.

- Branch and Bound Method
- Cutting Plane Method

- Applications: solving puzzles (Sudoku), reasoning about systems and other applications.
- Classification and Machine Learning

Mathematical Maturity (undergraduate algorithms or CS theory) and basic programming ability.

A background in engineering or applied sciences could be useful, as well.

The prerequisites for this class include:

**Basic College Level mathematics:**calculus and some linear algebra: matrices, matrix operations and solving linear equations.**Programming skills:**

**Textbook:** Linear Programming by Robert J. Vanderbei (available online from author's webpage).

**Alternative:** Linear Programming by Vasek Chvatal, W.H. Freeman published, 1983. This book still remains a very clear and concise presentation.

**Other texts: **We may borrow material that is covered in some of the** **texts below. As you go down this list, the texts become less relevant for this class but remain very important for the broader field of optimization that we seek to introduce through this class.

- Combinatorial optimization: Algorithms & Complexity, by Christos Papadimitrou and Ken Steglitz.
- Linear Programming series of two books by G.B. Danzig and M.K. Thapa.
- Schrijver's book on the
*Theory of Integer Linear Programming and Integer, Integer and Combinatoral Optimization*book by Wolsey and Nemhauser are also good references. *Convex Optimization*by Boyd and Vandenbreghe is a good reference for the more general area of convex optimization.*Numerical Optimization*by Nocedal and Wright is a great reference for solving non-linear optimization problems.

Each class will consist of many short lecture videos between 10-15 minutes in length with nearly 1.5-2 hours of lectures each week. We will have weekly assignments involving 5-10 problems each week. These assignments will either be multiple choice or ask you to compute something and enter the answer. We will have four programming assignments (one every two weeks) that will incrementally help you build an ILP solver. Programming assignments can be done in virtually any general purpose language.

The course will be structured with two interactive tracks: algorithms/theory for linear optimization problems and applications. The applications will include ideas on modeling real-life optimization problems as linear programs and the appropriate use of concepts like duality in finding and interpreting solutions.

- Will I get a statement of accomplishment after completing this class?

- What textbooks will I need for this class?

We recommend a great textbook by Prof. Vanderbei (see http://www.princeton.edu/~rvdb/LPbook/). It is available as a free download.

The classic book by Chvatal is an excellent textbook but sadly out-of-print.

- What are the pre-requisites?

**Basic College Level mathematics:**calculus and some knowledge of linear algebra.**Some programming skills:**H**owever, students without a programming background can pass the course by solving the weekly assignments**.

- What will the level of the class be?

- What skills will I learn?

what optimization problems are, what are linear optimization problems, what are the applications, what are the algorithms used for solving LPs, and how do they work?

In addition, we found through our previous offering in 2013 that the course helps many students think mathematically and improve the programming skills. We were proud of the many students from last year who took on some of the challenging programming assignments and reported a big confidence boost in their skills.

- Can I get university course credits for this class?

However, Prof. Sankaranarayanan teaches an on-campus class (CSCI 5654) at the University of Colorado, Boulder, and it will be available simultaneously on-line for credit through CAETE (see http://cuengineeringonline.colorado.edu/ ). You can enroll for our class CSCI 5654 through CAETE from anywhere in the world.

- Are we going to do rigorous mathematical proofs? How much programming do you expect to do?

Assignments will test the conceptual ideas in the class including algorithms, and many assignments may ask you to use an existing LP solver (open source or commercial) to solve a LP/ILP and interpret its answer. We do not consider this part as programming: any computer user should be able to manage this.

We will have programming assignments: in fact, students will get to build their own LP and later ILP solver in stages

- Is there a particular programming language that you expect for the assignments?

- What will the coursework involve?

- How do I pass? How does distinction work?

To pass the class: you will need to get at least 35% of the total grade. The pass cutoff is designed so that students can pass either by solving some/all of the programming assignments OR by solving some/all of the weekly assignments.

To score a distinction: you will need to get at least 85% of the total grade. To score a distinction, students must do well in ALL aspects of the course: programming as well as weekly assignments.