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

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.

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.

Dates:

- 20 October 2014, 7 weeks
- 2 September 2013, 9 weeks

Included in selections:

Optimization

Optimization is for optimistic people!

Optimization is for optimistic people!

More on this topic:

Physics Essentials 1

INTRODUCTION Why learn Physics? Physics is the fundamental science of everything...

INTRODUCTION Why learn Physics? Physics is the fundamental science of everything...

Nonlinear Programming (Spring 2003)

6.252J is a course in the department's "Communication, Control, and Signal Processing...

6.252J is a course in the department's "Communication, Control, and Signal Processing...

Introduction to Algorithms (Spring 2008)

This course provides an introduction to mathematical modeling of computational...

This course provides an introduction to mathematical modeling of computational...

Introduction to Computer Science and Programming (Fall 2008)

This subject is aimed at students with little or no programming experience....

This subject is aimed at students with little or no programming experience....

Discrete Optimization

Tired of solving Sudokus by hand? This class teaches you how to solve complex...

Tired of solving Sudokus by hand? This class teaches you how to solve complex...

More from 'Coursera':

First Year Teaching (Secondary Grades) - Success from the Start

Success with your students starts on Day 1. Learn from NTC's 25 years developing...

Success with your students starts on Day 1. Learn from NTC's 25 years developing...

Understanding 9/11: Why Did al Qai’da Attack America?

This course will explore the forces that led to the 9/11 attacks and the policies...

This course will explore the forces that led to the 9/11 attacks and the policies...

Aboriginal Worldviews and Education

This course will explore indigenous ways of knowing and how this knowledge can...

This course will explore indigenous ways of knowing and how this knowledge can...

Analytic Combinatorics

Analytic Combinatorics teaches a calculus that enables precise quantitative...

Analytic Combinatorics teaches a calculus that enables precise quantitative...

Accountable Talk®: Conversation that Works

Designed for teachers and learners in every setting - in school and out, in...

Designed for teachers and learners in every setting - in school and out, in...

© 2013-2019