Discrete Optimization

开始时间: 03/04/2015 持续时间: 9 weeks

所在平台: Coursera

课程类别: 计算机科学

大学或机构: University of Melbourne(墨尔本大学)

   

课程主页: https://www.coursera.org/course/optimization

课程评论: 3 个评论

评论课程        关注课程

课程详情

Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals.

This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation. 

课程评论(3条)

0

半饱半醉 2015-05-20 06:42 0 票支持; 0 票反对

终于把这门课过了,过了评论一下
这门课非常有意思,老师是个逗逼很风趣很牛X。课程形式也很独特,一开课就把所有的视频和作业都放出来,只要在课程结束之前完成就通过,学生可以根据自己的时间来安排学习进度。作业是5个 NP-Hard 优化问题,分别是背包问题、地图着色、TSP,后两个是比较接近实际的优化问题:机构设施选址和车辆路由。每个问题又有6个子部分,每个部分规模逐个增加,越来越难。每个部分0-10分,根据solution的质量评分,所有部分都拿到7或者至少3个10其他都是3就能获得证书,拿到满分是很困难的。有意思的是,这门课讲了3种优化方法:Constraint Programming、Local Search和Linear & Integer Programming,每种方法都能解决上述作业,各有优劣,学生可以按照自己熟悉的方法解题,满分的solution往往都是几种方法的混合。作业不限制编程语言和类库,只要能找到最优结果就行。作业还有排行榜,把大家的计算结果进行排行,有时候你吭哧吭哧优化了半天,自以为不错,但是发现和别人的差距超级大。

这门课的视频量和作业量都很大,每周大约十几个小时的编程,有时候我会思考一个作业好几天,很辛苦也很有乐趣,就像老师在视频里讲的:It's going to be a lot of fun and a lot of work, But a lot of fun。 所以过了这门课我还是很有成就感的。

课程的视频我已经备份下来,留作以后参考。[百度网盘](http://pan.baidu.com/s/1ntDWbX3)

4

wzyer 2013-08-20 15:23 4 票支持; 0 票反对

终于有时间来谈一谈离散优化这门课了。我一般不愿在某门课刚结束甚至是还没结束时就来谈论得失,因为只有经过时间的消化,才能让有价值的东西沉淀下来。但是离散优化这门课给我的体验之好,让我确信不需要多余的时间,我也能从中受益。

从第一周开始,这门课上课的方式就让我觉得意外:所有的视频,作业以及资料都完整的出现在课程页面上,没有明确的要求学生应该在哪一周完成哪些学习。如果你愿意,第一周就完成所有作业也完全是可行的——只要你有这个能力。如此自由化的学习对我而言完全是一种全新的体验,你面对的,只是几周的作业和几个专题的讲课视频。作业和视频并非一一对应,甚至也并非循序渐进。因此,很多人在第一周都会显得很迷茫,我也是如此,但之后的学习进程让我深深喜欢上了这种做法。

为什么我喜欢这种方法?因为我觉得这种方式契合了我们解决未知问题的过程。这门课的最终目标,是要解决5个NP问题。对于这样的难题,初学者很难一上来就有解决问题的思路。这时候,我们会怎么做?尝试!对,你需要一些解决这类问题的通用工具,然后拿着这些工具去不断尝试解决问题,在尝试的过程中,你自然就会知道哪些工具优势在哪里,缺点是什么。然后围绕着最终目标,选择最合适的解决办法。因此,我觉得这门课最有价值的一点就是鼓励你去尝试各种方法,然后从中获得一般的课堂讲授中无法获得的经验。也正是在这样一种实践的引领下,有同学甚至做出了让老师都赞叹的优化解。比如1000个节点的graph coloring问题,有人将最小颜色数压缩到了83(我只弄到了99)。对于这样的问题,如果所有同学都沿着老师设定的轨道走,很难设想会出现这么好的结果。

当然,基于这种学习方式,这门课的作业会显得有些偏难。由于都是NP问题,而且每个问题都有大规模的数据需要求解,想要全满分还是需要付出一些时间的。如果你真的是尝试了很多方法,小心翼翼的写代码以求运行效率,那么平均每周花费十几个小时的时间是合理的,而且代码量也绝对不会少。相反,如果你事先知道了哪个问题最适合用哪种方法,那其实也花不了多少时间,写不了多少代码,不过这样似乎解决问题的成就感就大大降低了。

这门课还有气死人不偿命的leader board。每当你精疲力尽打算收工的时候,看一眼leader board,看看自己的排名。顿时又有一种小宇宙要爆发的感觉了……

最后提一句,Pascal Van Hentenryck可是优化领域的大牛,很多有影响力的优化程序都有他的贡献。他本人不仅是墨尔本大学的教授,还是NICTA优化研究小组的老大。他在这门课里的讲解也非常风趣幽默,绝对能抓住你的眼球。是你不能错过的好老师。

1

ototsuyume 2013-07-01 22:28 1 票支持; 0 票反对

课没上完,不过开始了两个星期,可以给这个课程一个评价。
优点:老师讲课很有激情,内容很丰富,每个星期的作业都是一道np-complete的问题,要想拿满分十分有挑战性(但是对于参加ACM的高手来说这些题目应该不难)。
缺点:最大的确定是各个作业的解法分散在不同阶段的视频里,老师推荐看视频的顺序跟作业的阶段不太一致。
总的来说十分推荐想在算法上更进一部的同学去学,虽然这门课的介绍性质居多,但光是视频长度就是其他课程的两倍,压力还是有点大的

课程简介

Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization, including constraint programming, local search, and mixed-integer programming.

课程标签

离散优化 离散 优化 最优化 数学 应用数学 计算数学 墨尔本大学

52人关注该课程

主题相关的课程

Linear and Discrete Optimization 关注

Natural Language Processing 关注

Natural Language Processing 关注

Probabilistic Graphical Models 关注

Computer Vision: From 3D Reconstruction to Visual Recognition 关注

Introduction to Databases 关注

Web Intelligence and Big Data 关注

Fundamentals of Digital Image and Video Processing 关注

The Hardware/Software Interface 关注

Cryptography II 关注