CO@Work Teaser 1YouTube↗  IA↗(long shot)
Science & Technology  1.2K views 15 likes 0 dislikes   12 Jul 2020
Mixed Integer Programming 3.6K subscribers United States YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Click to Play Video Click to Play Video
Привет, меня зовут Торстен Кох, и я профессор
Hallo, mein Name ist Thorsten Koch
программного обеспечения и алгоритмов
und ich bin Professor für Software
для дискретной оптимизации в ТУ Берлин,
und Algorithmen für die diskrete
и в то же самое время я глава кафедры прикладных
Optimierung an der TU Berlin. Gleichzeitig bin ich Leiter der
методов алгоритмического интеллекта в
Abteilung Methoden der Angewandten
институте Цузе.
Algorithmischen Intelligenz am Zuse-Institut.
Оптимизация означает, что мы ищем наилучшее
Optimierung bedeutet, wir suchen
возможное решение, и оно дискретно, потому
die bestmögliche Lösung und diskret
что мы имеем дело с целыми объектами, например,
heißt, wir betrachten ganze Objekte
целыми числами.
zum Beispiel ganze Zahlen.
Предположим, задача состоит в том, чтобы
Angenommen, die Aufgabe besteht
найти самый короткий маршрут для 40-тонного
darin, den kürzesten Weg für einen
грузовика.
40-Tonnen-LKW zu finden.
Не имеет смысла искать два отдельных маршрута,
Es nützt nichts zwei unterschiedliche
оба из которых допускают до 20 тонн.
Routen zu finden, die beide jeweils
Нам просто нужно найти один непрерывный
20 Tonnen erlauben. Wir müssen einen ungeteilten Weg
путь, допускающий 40 тонн.
finden der 40 Tonnen erlaubt.
Или если вопрос в том, сколько яиц нам нужно
Oder wenn die Frage ist, wie viele
купить для рецепта.
Eier wir für ein Rezept kaufen müssen.
Ответ, который мы хотим услышать, не 2.3.
Als Antwort wollen wir nicht 2,3 hören.
К сожалению, просто округление не всегда
Leider löst einfach nur aufrunden
решает задачу и оказывается, что многие
nicht immer das Problem und wie
вопросы становятся гораздо сложнее, если
sich herausstellt werden viele Fragen
вы настаиваете на целочисленном ответе.
sehr viel schwieriger zu lösen, sobald ganzzahlige Antworten benötigt werden.
В каком-то смысле больше 40 лет я пытаюсь
In gewisser Weise versuche ich jetzt
заставить компьютеры делать то, что я хочу,
seit mehr als 40 Jahre, Computer
и недавно я добавил более сложную задачу
dazu zu bringen, das zu tun, was möchte. Vor kurzem habe jetzt die anspruchsvollere
- попытаться заставить студентов делать
Aufgabe hinzugefügt, zu versuchen
то, что я хочу.
Studenten dazu zu bekommen zu tun,
Это, безусловно, все еще незавершенная работа.
was ich möchte. Dies ist noch in Bearbeitung.
Область, о которой мы говорим.
Der Bereich, über den wir sprechen
находится где-то на пересечении прикладной
liegt irgendwo im Schnittpunkt von
математики, информатики и программной инженерии,
angewendter Mathematik, Informatik und Softwareentwicklung, Wirtschaftswissenschaften
экономики и исследования операций, промышленной
und Operations Research, Ingenieurwesen,
инженерии, и любой области, из которой происходят
und aus welchem Gebiet auch immer
задачи, которые мы пытаемся выполнять, будь
die Aufgaben, die wir lösen möchten, stammen.
то общественные науки или квантовая физика.
Seien es Sozialwissenschaft oder Quantenphysik.
В этой лекции я расскажу о том, как давать
In diesem Vortrag werde ich darüber
инструкции машинам, т.е.
sprechen wie man Maschinen, d.h.
компьютерам, для выполнения конкретного
Computer, instruiert eine bestimmte
задания.
Aufgabe ausführen.
Интересно, методы весьма похожи на те, которые
Interessanterweise, sind die Methoden
вы использовали бы для людей, например,
ziemlich die gleichen, die man auch für Menschen, zum Beispiel Studenten,
студентов.
verwendet.
Удивительно, но наиболее сложные приёмы
Überraschenderweise sind die anspruchsvolleren
с точки зрения компьютера также являются
Techniken aus der Sicht der Computer
самыми старыми из используемых людьми и
auch die ältesten von Menschen verwendeten.
иногда даже могут быть применены к животным.
Und manchmal können sie sogar auf
Давайте начнем с примера.
Tiere angewendet werden. Beginnen wir mit einem Beispiel.
Задача, которую мы хотим выполнить, заключаются
Die Aufgaben, die wir ausführen
в том, чтобы решить воскресный тизер из газеты.
möchten, ist ein Sonntagsrätsel
Я покажу вам, как.
aus einer Zeitung zu lösen. Ich vorführen wie man das macht.
Вот воскресный тизер из газеты.
Hier ist das Sonntagsrätsel aus einer Zeitung.
Вы должны поместить 10 цифр в углы трех квадратов.
Sie sollen 10 Ziffern in die Ecken von drei Quadraten schreiben.
Квадраты соединены одним углом, как видно
Die Quadrate haben jeweils eine
на изображении.
gemeinsame Ecke, wie im Bild zu sehen ist.
Просто распределите числа от 1 до 10 по кругам
Verteilen Sie einfach die Zahlen
так, чтобы сумма каждого квадрата была одинакова.
von 1 bis 10 in die Kreise so, dass
Есть ли решение?
die Summe jedes Quadrats gleich ist.
Есть ли больше одного решения?
Gibt es eine Lösung? Gibt es mehr als eine Lösung?
Если да, то какова наименьшая сумма, и какая
Wenn ja, was ist das kleinste Summe,
будет самая большая сумма?
und was wäre die größte Summe?
Давайте используем компьютер, чтобы решить
Lassen Sie uns das mit dem Computer
эту задачу: если мы применим глупую грубую
lösen: Wenn wir nur dumm durchprobieren,
силу и просто перепробуем все цифры от 0
probieren wir alle Zahlen durch
до 10 миллиардов минус 1, то это будет сложность
von 0 bis 10 Milliarden minus 1 und hätten eine Komplexität von n hoch n.
n в степени n. Но как мы заметили, нам нужны только перестановки
Aber wie man leicht sieht, brauchen
из 10 цифр, так что если в графе 10 узлов, то
wir nur die Permutationen der 10 Ziffern. Wenn der Graph also 10 Knoten hat, gibt es 10!
мы получаем 10 факториал, или три с половиной миллиона возможностей.
oder dreieinhalb Millionen Möglichkeiten.
С лишь двумя квадратами у нас было бы всего
Bei nur zwei Quadraten hätten wir
5040 возможностей, но с четырьмя квадратами
nur 5040 Möglichkeiten, aber mit
мы уже достигаем более 6 миллиардов.
vier Quadraten sind es bereits mehr
В любом случае, это уже хорошее ускорение
als 6 Milliarden. Auf jeden Fall ist das schon eine
по сравнению с тем, как если бы мы действовали
schöne Beschleunigung im Vergleich
совершенно глупо.
zu gänzlich dummem ausprobieren.
Как мы решим это?
Wie würden wir das lösen?
Во-первых, мы отмечаем, что сумма всех чисел
Zunächst stellen wir fest, dass
с 1 по 10 равна 55.
die Summe aller Zahlen von 1 bis 10 = 55 ist.
Если у нас есть 3 квадрата, это значит, что
Wenn wir 3 Quadrate haben, zählen
мы считаем два числа дважды, так что мы знаем,
wir zwei Zahlen zweimal, also wissen
что 3 умножить на сумму квадрата равно 55
wir dreimal die die Summe eines
плюс a плюс b.
Quadrats entspricht 55 plus a plus b.
Поэтому a плюс b должно быть как минимум
Daher muss a plus b mindestens gleich
3, и может быть максимум 19.
3 sein und kann höchstens 19 sein.
Так что наше решение находится между 58 и 74.
Damit liegt unser Lösungsbereich zwischen 58 und 74.
Мы теперь имеем нижнюю и верхнюю границы
Wir haben jetzt untere und obere
нашего решения.
Schranken für unserer Lösungen.
Но мы все еще можем усилить эти границы,
Aber wir können diese Schranken
заметив, что решение должно делиться на
noch verstärken durch durch die Beobachtung, dass die Lösung durch
3, так что мы можем округлить это вверх до
3 teilbar sein muss. Also können wir die Schranken auf
60 и вниз до 72.
60 und auf 72 runden.
При 60 это означает 20 на квадрат, следовательно
Bei 60 bedeutet dies 20 pro Quadrat,
a плюс б должно быть равно 5, оставляя нам
also a plus b muss gleich 5 sein.
либо 1 и 4, либо 2 и 3.
Damit bleiben entweder 1 und 4 oder 2 und 3.
С этого момента осталось не так уж много
Von da an gibt es nicht mehr so
вариантов.
viele Möglichkeiten.
Теперь давайте построим математическую
Lassen Sie uns nun ein mathematisches
модель для этого.
Modell dafür erstellen.
Мы вводим переменные от X1 до X10, которые
Wir führen die Variablen X1 bis
должны быть целыми числами между 1 и 10.
X10 ein die ganze Zahlen zwischen
Сперва мы займемся минимальной суммой по
1 und 10 sein müssen. Zuerst minimieren wird die Summe der Quadrate.
квадратам. Итак, мы минимизируем X1 до X4.
Also minimieren wir X1 bis X4.
Так как все квадраты должны быть равны,
Da alle Quadrate gleich sein müssen,
то нет смысла также иметь остальные переменные
macht es keinen Sinn, auch den anderen
в целевой функции.
Variablen in der Zielfunktion zu haben.
Тогда мы вводим ограничения: квадрат 1 должке
Dann kommen die Nebenbedingungen:
быть равен квадрату 2 и квадрат 2 равен квадрату
Quadrat 1 sollte gleich Quadrat 2 sein und Quadrat 2 gleich Quadrat 3.
3. Мы всегда опускаем совместную переменную.
Wir lassen die gemeinsame Variable immer weg.
Наконец, все X_i должны быть различными.
Schließlich sollten alle X_i unterschiedlich
Теперь это модель.
sein. Dies ist jetzt ein Modell.
Данных ограничений достаточно, чтобы описать
Die Einschränkungen reichen aus,
допустимое решение.
um eine zulässige Lösung zu beschreiben.
Есть еще ограничения, которые мы могли бы
Es gibt weitere Bedingungen, die
добавить, например, сумма от X1 до X10 + X4 + X7
wir hinzufügen könnten. Z.B: die Summe von X1 bis X10 +
должна быть делима на 3.
X4 + X7 muss durch 3 teilbar sein.
Но это уже неявно там.
Aber das ist schon implizit da.
Теперь, так как я хочу получить в конце концов
Da wir am Ende ein ein ganzzahliges
целочисленную линейную программу, я хотел
lineares Programm haben möchten,
бы смоделировать ограничение все-различные
modellieren wir die „all-different”
другим способом.
Bedingung auf eine andere andere Weise.
Я объясню позже, почему это плохая идея
Ich werde später erklären, warum
- моделировать все-различные с использованием
es keine gute Idee ist, „all-different”
переменных X.
den X-Variablen zu modellieren,
Хотя это технически возможно.
obwohl dies technisch möglich ist.
Что мы делаем, так это мы вводим дополнительные
Stattdessen führen wir zusätzliche
двоичные переменные Z.
binäre Variablen Z ein.
Есть 10 двоичных переменных Z, связанных
Jeder X-Variablen sind sind 10 Null-Eins
с с каждой переменной Х.
Z-Variablen zugeordnet.
Из этих 10 мы всегда требуем, чтобы ровно
Von diesen 10 muss immer genau eine
одна переменная была равна одному, а все
Variable gleich eins sein und alle
остальные - нулю.
anderen sind 0.
Переменная Z указывает, которая цифра является
Die Z-Variable gibt an, welche Ziffer
нашим текущим выбором для соответствующей
unserer aktuellen Auswahl für das
переменной X.
entsprechende X gesetzt ist.
Итак, у нас есть двоичная переменная для
Wir haben also eine binäre Variable
каждой цифры каждой переменной.
für jede Ziffer jeder Variablen.
И конечно, каждая переменная может иметь
Und natürlich kann für jede Variable
только одну активную цифру.
nur eine Ziffer aktiv sein.
Но также каждая цифра может быть активной
Aber auch jede Ziffer darf zu einem
только в одной переменной за раз.
Zeitpunkt nur in einer Variablen aktiv sein.
Итак, мы получили эту таблицу, и каждая строка
Damit bekommen wir diese Tabelle,
и столбец составляет в сумме 1.
in der sich jede Zeile und jede
Мы теперь соединяем переменные X и Z этими
Spalte zu 1 summiert. Wir verbinden nun die X mit den
уравнениями, где каждое Z умножается на
Z Variablen durch diese Gleichungen, in denen jedes Z mit seiner Ziffer
свою цифру.
multipliziert wird.
Теперь мы используем так называемый язык
Wir verwenden jetzt eine so genannte
алгебраического моделирования, чтобы написать
Algebraische Modellierungssprache
это.
um dies aufzuschreiben.
Как вы видите, это просто записанная математическая нотация.
Wie Sie sehen können, ist es nur die mathematische Notation aufgeschrieben.
Теперь мы дадим это решателю целочисленного
Jetzt geben wir dies einem Löser
программирования, в данном случае SCIP, который
ganzzahlige Programme, in diesem
разрабатывается здесь, в ZIB.
Fall SCIP, das hier bei uns am ZIB
Как видите, он находит решение очень быстро,
entwickelt wird. Wie Sie sehen können, findet es
и это действительно глобально оптимальное
sehr schnell eine Lösung. Diese ist in der Tat eine global
решение, и мы получаем 20.
optimale Lösung und wir bekommen 20.
Если перейти к максимизации, результат будет 24.
Wenn Sie wir maximieren würden, wäre das Ergebnis entsprechend 24.
Я также попробую это с 5 квадратами, что
Ich habe das auch mit 5 Quadraten
означает граф с 16 узлами.
versucht, was einem 16-Knoten-Graphen
Это уже значит 21 триллион возможностей,
entspricht. Dieses Problem hat bereits 21 Billionen
и это все еще решается меньше чем за 1с.
Möglichkeiten und es wird immer
Так что, что бы ни делал решатель, это не
noch unter 1s gelöst. Was auch immer der Löser tut, es
поиск при помощи грубой силы, но нечто более
ist nicht einfach dummes durchprobieren,
умное.
sondern eine intelligente Suche.
Если вы хотите узнать больше о том, как грамотно
Wenn Sie mehr darüber wissen möchten
находить оптимальные решения дискретных
wie man intelligent optimale Lösungen
задач, присоединяйтесь к нам на Комбинаторной
für diskrete Fragen berechnet, nehmen Sie an Combinatorial Optimization
Оптимизации на Практике в сентябре этого года.
at Work im September dieses Jahres teil.
30 экспертов со всего мира научат вас моделировать
30 Experten aus der ganzen Welt
и находить решения задач, которые людям
unterrichten wie man modelliert und Lösungen berechnet für Probleme,
слишком трудно решить.
die für Menschen zu schwer zu lösen sind.
Я с нетерпением жду вас там.
Ich freue mich darauf, Sie dort zu sehen.
Пока!
Bye Bye!!
Similar videos:

Libgdx for Android | Tutorial 14 | Multiple Screens | How to make Android games
Programming Tutorials
9.7K views 146 likes 3 dislikes 07 Oct 201537% match









Algebra I: Translating Sentences into Equations (Level 2 of 2) | Examples II
Math Fortress
6.2K views 26 likes 1 dislikes 26 Feb 201337% match











Trolls, tolls, and systems of equations | Algebra II | Khan Academy
Khan Academy
676.9K views 355 likes 23 dislikes 19 Oct 201237% match


Typecasting
CS50
50.1K views 0 likes 0 dislikes 16 Sep 201236% match










Is Simulating Soft and Bouncy Jelly Possible? 🦑
Two Minute Papers
2.9M views 89.9K likes -1 dislikes 25 Apr 202036% match

Cómo poner Fondos de Escritorio Animados | Wallpaper Engine | tener fondo de pantalla en movimiento
AirXander
8.4K views 208 likes 20 dislikes 25 Feb 201936% match







Git and GitHub course | 05 You may have already used GitHub
Programming Tutorials
1.8K views 21 likes 1 dislikes 14 Sep 201636% match









Cubo de Rubik inteligente - Unboxing y Review | SuperCube Giiker | Rubik's Cube puzzle Bluetooth
AirXander
639 views 60 likes 1 dislikes 29 Jan 202036% match





String theory and the hidden structures of the universe - Clifford Johnson
TED-Ed
118.5K views 1.5K likes 51 dislikes 22 Apr 201336% match



¿Cómo David Coperfield logra VOLAR? Pacto ILUMINATI o el mejor acto de ILUSIONISMO del MUNDO
Fake Buster
450.6K views 10.9K likes 836 dislikes 01 Feb 201936% match





Libgdx for Android | Tutorial 07 | Inserting Images with SpriteBatch | How to make Android games
Programming Tutorials
13K views 176 likes 8 dislikes 05 Oct 201535% match









Leather and meat without killing animals | Andras Forgacs
TED
249.4K views 5.4K likes 173 dislikes 19 Sep 201335% match






How computers learn to recognize objects instantly | Joseph Redmon
TED
1M views 26.8K likes 394 dislikes 18 Aug 201735% match




The next step in nanotechnology | George Tulevski
TED
431.8K views 7.1K likes 423 dislikes 31 Jan 201735% match




A headset that reads your brainwaves | Tan Le
TED
362.8K views 2.7K likes 52 dislikes 22 Jul 201035% match





Làm thế nào để ươm, ghép cây

62 views 0 likes 0 dislikes 22 Sep 201535% match

Can You Trust Kurzgesagt Videos?
Kurzgesagt – In a Nutshell
6.7M views 530.4K likes -1 dislikes 03 Mar 201935% match






Create a Project | Learning Android 06
Programming Tutorials
15.1K views 167 likes 3 dislikes 14 May 201535% match









Assad Interview With Dennis Kucinich On Fox News
The Young Turks
51.1K views 1.1K likes 871 dislikes 19 Sep 201335% match

Amazing Chinese Face Mask Changing Magic REVEALED
Fake Buster
133.5K views 3.3K likes 510 dislikes 03 Nov 201835% match




Introduction to limits 2 | Limits | Precalculus | Khan Academy
Khan Academy
1.9M views 5.9K likes 216 dislikes 30 Sep 200735% match




¿COMO HACER APARECER UN ELEFANTE 🐘?- David Copperfield el "Mago Illuminati" - Video to Life REVELADO
Fake Buster
1.3M views 22.8K likes 2K dislikes 01 Dec 201835% match
0 views 0 likes 0 dislikes 11 Jun 202635% match














Larry Burns: Reinventing the car
TED
35.5K views 146 likes 112 dislikes 05 Dec 200835% match




Kevin Hale: Advice | Implement a Monetization Strategy | App Monetization | Udacity
Udacity
1K views 13 likes 0 dislikes 30 Apr 201634% match


Transistor hoạt động như thế nào? | Transistor là gì? | Bóng bán dẫn là gì? | Tri thức nhân loại
Tri Thức Nhân Loại
389.9K views 8.7K likes 255 dislikes 20 May 202034% match



Algebra I: Translating Problems Into Equations (Level 1 of 2) | Word Problems, Problem Solving
Math Fortress
8.9K views 55 likes 3 dislikes 18 Aug 201334% match











Con Người Sẽ Trở Thành Siêu Nhân, Quyến Rũ, Thông Minh Hơn Trong Tương Lai | Khoa Học Huyền Bí
Trung Quốc Không Kiểm Duyệt
31.7K views 371 likes 24 dislikes 28 Apr 201734% match

Bastian Schaefer: A 3D-printed jumbo jet?
TED
118.4K views 1.2K likes 244 dislikes 29 Jul 201334% match





Andreas Raptopoulos: No roads? There's a drone for that
TED
145.2K views 1.8K likes 56 dislikes 21 Nov 201334% match





Settings Privacy About Contact Donate