|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/solving-algorithms-discrete-optimization
课程评论：没有评论
课程名称：离散优化的解决算法 概述：离散优化旨在在许多选择中做出优秀决策，其应用遍及社会各个领域。从解决数独谜题到婚宴座位安排，离散优化技术都能发挥作用。这种技术还可以用于调度飞机及其机组人员、协调钢铁生产以及组织从矿山到港口的铁矿石运输。明智地使用稀缺或昂贵的资源（如人员和物料资源）能够使公司提升利润数百万美元。此外，我们日常生活中的许多相似问题，如包裹的日常配送路线、制定学校 timetable 和电力供应安排等，都与离散优化密切相关。尽管这些问题至关重要，但使用传统的本科计算机科学方法解决这些问题极具挑战性。 本课程适合已完成高级离散优化建模的学生。在本课程中，您将扩展对解决复杂离散优化问题的理解，学习用于解决这些问题的技术，以及如何将高层次模型（用 MiniZinc 编写）转化为可被底层求解器执行的形式。通过更好地理解解决技术，您不仅能提高建模能力，还能够选择最适合的求解技术。 课程内容大纲： 1. 基本约束编程 - 本模块通过示例阐述约束编程求解器的基本原理，包括约束传播和搜索。您将学习如何用传播引擎处理一组传播器，用以协调约束信息的传播，并了解基本搜索、变量和值选择，以及如何有效结合传播和搜索。 2. 高级约束编程 - 本模块展示分支限界搜索如何解决优化问题，深入探讨在这些情况下搜索策略的重要性，以及包括重启搜索和基于影响的搜索在内的高级搜索策略。 3. 混合整数规划 - 本模块首先介绍线性规划和解决连续线性优化问题的单纯形算法，接着展示如何将该方法融入分支限界搜索以求解混合整数规划，并了解戈莫里切割和分支与切割方法以加速求解过程。 4. 局部搜索 - 本模块探讨局部搜索方法，学习状态、移动和邻域的概念，并在约束搜索空间中应用贪心搜索和最陡下降搜索。您还将学习如何逃离局部最小值，使用不同方法（如重启、模拟退火、禁忌列表和离散拉格朗日乘子），以及大邻域搜索如何将找到最佳邻居的问题视为离散优化问题，从而实现更高效的搜索。 该课程为希望深入了解离散优化技术的学生提供了全面的教学内容，并将为其未来的学术或职业生涯铺平道路。
Name:Basic Constraint Programming
Description:This module starts by using an example to illustrate the basic machinery of Constraint Programming solvers, namely constraint propagation and search. While domains represent possibilities for variables, constraints are actively used to reason about domains and can be encoded as domain propagators and bounds propagators. You will learn how a propagation engine handles a set of propagators and coordinates the propagation of constraint information via variable domains. You will also learn basic search, variable and value choices, and how propagation and search can be combined in a seamless and efficient manner. Last but not least, this module describes how to program search in MiniZinc.
Name:Advanced Constraint Programming
Description:In this module, you will see how Branch and Bound search can solve optimization problems and how search strategies become even more important in such situations. You will be exposed to advanced search strategies, including restart search and impact-based search. The module also uncovers the inner workings of such global constraints as alldifferent and cumulative.
Name:Mixed Integer Programming
Description:This module starts by introducing linear programming and the Simplex algorithm for solving continuous linear optimization problems, before showing how the method can be incorporated into Branch and Bound search for solving Mixed Integer Programs. Learn Gomory Cuts and the Branch and Cut method to see how they can speed up solving.
Name:Local Search
Description:This module takes you into the exciting realm of local search methods, which allow for efficient exploration of some otherwise large and complex search space. You will learn the notion of states, moves and neighbourhoods, and how they are utilized in basic greedy search and steepest descent search in constrained search space. Learn various methods of escaping from and avoiding local minima, including restarts, simulated annealing, tabu lists and discrete Lagrange Multipliers. Last but not least, you will see how Large Neighbourhood Search treats finding the best neighbour in a large neighbourhood as a discrete optimization problem, which allows us to explore farther and search more efficiently.
Discrete Optimization aims to make good decisions when we have many possibilities to choose from. Its applications are ubiquitous throughout our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions on the use of scarce or expensive resources such as staffing and material resources also allow corporations to improve their profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Advanced Modelling for Discrete Optimization. In this course, you will extend your understanding of how to solve challenging discrete optimization problems by learning more about the solving technologies that are used to solve them, and how a high-level model (written in MiniZinc) is transformed into a form that is executable by these underlying solvers. By better understanding the actual solving technology, you will both improve your modeling capabilities, and be able to choose the most appropriate solving technology to use. Watch the course promotional video here: https://www.youtube.com/watch?v=-EiRsK-Rm08
