## Linear and Integer Programming

 所在平台: Coursera 课程类别: 计算机科学

Explore 1600+ online courses from top universities. Join Coursera today to learn data science, programming, business strategy, and more.

#### 课程详情

Linear Programming (LP), 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 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

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

2. Understand important and emerging applications of LP to economic problems (optimal resource allocation, scheduling problems), machine learning (SVM), control design (finite horizon optimal control, dynamic programming), and formal verification (ranking functions, symbolic execution, SMT solvers).

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.

#### 课程大纲

A list of topics that will be covered:

• Linear Programs: Simplex algorithm and its analysis, duality, complementary slackness.
• Geometry of linear programs: Convex polyhedra, Generator vs. Constraint representations, Convex Hull and Facet Enumeration.
• Network flow algorithms.
• Integer Linear Programs: Branch & Bound, Gomory cuts, approximation/randomization through LP.
• Applications: Optimal allocation of resources, control design, verification, regression, relaxations of hard combinatorial problems to LP.
• Interior Point Methods

#### 课程评论(3条)

 0 sweetglue 2013-11-17 18:09 0 票支持; 0 票反对 必须满分。这课的确推荐。里面那个印度籍老师语速飞快但吐字很清晰，单位时间内获得的信息量极大。这门课让我头一次真切地明白了对偶问题到底是怎么回事... 此外该印度老师还在讲课中顺带吐槽印度...
 0 钛合金蛙眼 2013-11-17 17:11 0 票支持; 0 票反对 楼上神级评价我就不好意思瞎说了，老师付出了很多辛苦，但是取消了期末的考试有点小不爽，下一次开课应该会更好
 4 爬犁腿 2013-11-16 22:17 4 票支持; 0 票反对 轮次：Sep 2nd 2013 背景：基本的线性代数知识，基础的编程能力。 内容： 共9周，每周大约2小时的课程。深入介绍了线性规划问题的单纯形法、对偶原理；整数规划的分支定界法、切割平面法（要求编程实践）。介绍了一些优秀的能够完成凸规划软件如CVX、CVXOPT、GLPK、MATLAB等。简述了它们的实际应用，如最小二乘法的拟合、去噪；求解数独等（要求至少能够使用规划软件实现）。分别对算法的时间复杂度进行了分析，最后谈到了内点法。 提供了一些优秀的进步学习凸规划课程的材料： http://stanford.edu/~boyd/cvxbook/ http://www.seas.ucla.edu/~vandenbe/ Prof. Sriram Sankaranarayanan讲授课程主题85%的理论内容，虽然有他一些印度口音且说话语速略快，但经历一段时间的熟悉，就会慢慢适应。Prof. Shalom D. Ruben介绍理论内容的相关应用，相比前一位，他的准备似乎不太认真，有时会顿住、或者讲错，但无伤大雅。 与国内课程相异之处： 单纯形法的表述并非国内普遍介绍的形式（Tableau），而是Dictionary；但二者等价，并未给学习带来不便。 通过偏重于编程实现算法，从而提高学生对算法的理解。比如从算法效率的角度对对偶原理进行了深入介绍，这是在国内的教材中我从未见到的（如陈宝林的《最优化理论与算法》）。 作业： 这部分是课程的重中之重，只有紧跟课程作业才能够深入理解并且各种算法的步骤及衍生的种种性质。几乎每周都有选择、填空形式的Homework。每两周一道Programming Assignment，分别为：转轴操作，优化阶段单纯形法，初始化阶段单纯形法（直译），切割平面法。最后有一个针对前半部分线性规划内容的Exam。 论坛： 很活跃，Prof. Sriram 极其敬业，几乎每个帖子里都有他的回复，他还贴出了一些python程序片段作为提示。同时每周课程的深入话题或远离主线的内容也会在其中讨论，看帖子很有收获。 评分方式及下期课程： 这是本期的评分方式， (Weekly) Assignments - 40% of the grade Programming (biweekly) Assignment - 35% of the grade Exam: 25% of the grade. - Certificate of completion: 30/100 or above - Distinction: 85/100 or above 据Prof. Sriram 在论坛中的叙述： 因为有很多选课的同学不会或没时间编程。下期课程很可能提供两类证书，即编程版的和不编程版的。课程论坛大大帮助了同学们的学习进程，下期课程考核可能会记入5%的论坛活跃度。 感受： 收获极大，第一次对某种算法有了非常深入的理解，应用时都不必查书了~

#### 课程简介

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.