3.1.6 Module 1 Summary

Loading...

En provenance du cours de The University of Melbourne

Solving Algorithms for Discrete Optimization

2 notes

The University of Melbourne

Solving Algorithms for Discrete Optimization

2 notes

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

À partir de la leçon

Basic Constraint Programming

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.

3.1.1 Constraint Programming Solvers13:13

3.1.2 Domains + Propagators18:59

3.1.3 Bounds Propagation21:58

3.1.4 Propagation Engine21:52

3.1.5 Search25:32

3.1.6 Module 1 Summary4:38

Rencontrer les enseignants

Prof. Jimmy Ho Man Lee
Professor
Department of Computer Science and Engineering
Prof. Peter James Stuckey
Professor
Computing and Information Systems

Welcome to the module summary for module one of course three.

Jimmy, what's been happening in story?

Well, a lot have happened since the last two courses.

Although Zhuge Liang our hero,

was a wise person,

his curiosity got the best of him this time.

One night, he couldn't help but to mess around with

the magical tablet and accidentally broke it

and the leak energy from the tablet created chaos in space and time and

Zhuge Liang was actually sent back to

the beginning of time to fix the problems that he created.

So we saw Zhuge Liang helping Nuwa to patch the holes in the Nine Heavens,

we also saw Zhuge Liang teaming up with

our Shennong to help fix the curse issue of the village,

as well as actually creating the 100 herb magical prescription for mankind.

This is actually this module talk about how a CP solver works.

Exactly. So we've looked inside the CP solver

and we looked at the two sort of key components of the CP solver which are the domains,

how we represent variables and what choices that have looked over,

and propagators, which is how

constraints are used to infer or remove values from these domains,

so we get less possible values.

Right. So propagator is really the only way

we represent constraints in the constraints programming server.

Exactly.

To do inference.

The only thing that a constraint programming solver knows about a constraint is

the propagator that implements the inference for that constraint and nothing else.

And then those inference would help remove possible values from the domains of variables.

Exactly. And that's what's stopping us doing our brute force search.

So a propagation engine we then looked at which is the loop which is handling many,

many times running through these propagators.

And we sort of looked at the properties of that engine which will make it

efficient because we're going to run

all these propagators millions and millions of times.

Sure. But propagation is not the only thing that we will

do when solving a constraint programming problem.

That's right. With just propagation,

we're going to solve almost no discrete optimisation problems.

We need to add search.

And search is like guessing a value for each of the variables?

Exactly. So it sounds very,

very naive we're just kind of a guess a value for each variable,

never going to do more propagation, right.

But it makes a difference which values we guess.

So we talked about the variable choice in a basic search,

which variable should we guess for next?

And the value choice, so which value should I give that variable?

When we talk about searching,

I think we were talking about enumeration.

But actually in most of the modern solvers,

they are doing binary search at branching.

That's right. Also all solvers just branch in two ways are they do something,

or the opposite of it because that actually can mimic

any of the valuation kind of branching that we all talk about.

So that is much more easy to implement and in the end much more efficient.

And then we also talk about how we could do all these searching in MiniZinc as well.

Exactly. So finally we exposed to you how you can

actually control the search of the CP solver from the MiniZinc level.

We can talk about workshop as well.

Exactly. So in this workshop, what are we doing Jimmy?

Well, Shennong helped me solve the curses of that village.

But some of their children, they are already sick.

So Shennong will have to prepare some herbs to heal these children.

And then for each of the particular herb,

there will be different processes,

using different tools to prepare them.

Because of the different processes,

we have the standard precedence constraint

because some of the processes must be done before the other ones.

We also have the standard non overlapping constraints

in case two process they're sharing the same tool,

then they cannot take place at the same time.

And what do the learners have to do in this workshop?

Well, different from other workshops,

we don't want you to build the model,

in fact we're going to give you the model.

It's actually a very standard scheduling model.

But what we want you to do is search for the right search strategy.

How should you do the best search on

this model in order to find the solutions as fast as possible?

So they do not have to build a model,

but they'll be a lot of experimentation to do.

Absolutely. There's three different variables we can search on.

Yeah.

And then there's lots of different searches we can try.

And basically we want you to explore as much as you can which of

the searches are the best over a wide variety of different instances.

So by a search, you mean selecting

the right variable choice and then also selecting the right value choices?

Exactly. And that's what we've done in module one of course number three.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play