Что творится с дейта сайнсом?

[Larsonsager]

Данная конкретная задача в данной формулировке решается очень просто: контейнеры большего веса (плотность-то тут при чем, если контейнеры одинакового размера?) надо пихать ниже.

[Sergunka]

Данная конкретная задача в данной формулировке решается очень просто: контейнеры большего веса (плотность-то тут при чем, если контейнеры одинакового размера?) надо пихать ниже.

Вы не очень в теме их могут подвозить с колес поэтому задача нетривиальная сама по себе там и прстой траков и складирование и какой кран куда должен засунуть. На самом деле и контейнеры при одинаковом размере имеют разный вес к примеру реф тяжелее чем обычный ну и размеры само собой разнятся от 20 до 40 футов.

[Larsonsager]

Я вообще не в теме, поэтому и написал: "в данной формулировке". Если нас интересует только остойчивость, то контейнеры достаточно отсортировать по весу.

> На самом деле и контейнеры при одинаковом размере имеют разный вес

Естественно, я это и написал.

> у и размеры само собой разнятся от 20 до 40 футов.

Насколько я слышал, они не разнятся от 20 до 40 футов, а бывают либо 20, либо 40. Хотя гугль пишет, что бывают и больше.

В общем, если нам не надо оптимизировать что-то ещё (типа того, что часть груза едет в один порт, а часть - в другой, и надо минимизировать время погрузки-разгрузки), а надо просто обеспечить наилучшую остойчивость, то оптимальное решение - отсортировать.

[tessob]

И я же привела вам пример ежесекундного применения симплекс метода в индустрии: расчет stowage plan на контейнеровозах. Как вы себе представляете погрузить 1000 контейнеров, в которых груз разной плотности, от зерна до хлопка до детских игрушек, без решения оптимизационной задачи? Судно должно быть сбалансировано, иначе оно перевернется.

Во-первых, симплекс метод — это все же не «обобщенное определение любого оптимизационного алгоритма», а вполне конкретная группа алгоритмов обхода вершин политопа в неком n-мерном пространстве реальных чисел. Во-вторых, ваша задача размещения груза на контейнеровозе симплексом не решается. Это задача дискретной математики в пространстве натуральных чисел. В математике вообще пока нет ни одного непереборного алгоритма, который бы находил min/max решение подобных задач за менее чем n! шагов. Увы. Однако я безумно рад за ваших одногруппников, которым, с ваших слов, таки удавалось это проделывать.

Что касается реального решения, то Sergunka абсолютно прав! Жадный алгоритм, немного эвристик и немного отсечений областей заведомо плохих решений будет считаться за несколько секунд для контейнеровоза любого размера. Выход на такой же уровень точности для для многих алгоритмов численной оптимизации, в случае какого-нибудь восьмитысячника, будет возможен только через несколько часов на вычислительном кластере из нескольких сот процессорных ядер.

15-30% от всего рынка (согласно разным источникам), и растет каждый месяц.

Вы потроллить меня решили что-ли? Какие 15-30% рынка в day ahead спотах!? Там одна волатильность сидит.

[Lisa]

Выход на такой же уровень точности для для многих алгоритмов численной оптимизации, в случае какого-нибудь восьмитысячника, будет возможен только через несколько часов на вычислительном кластере из нескольких сот процессорных ядер.

Смайлика с фейспалмом не нашла, ну да ладно. Я сдаюсь.

[tessob]

Сколько раз я зарекался не спорить с искусственным интеллектом….

Lisa, вам формально нужно найти оптимальный гамильтонов путь в полносвязном графе в 8’000 вершин. Число возможных гамильтоновых путей у такого графа будет примерно 10 ^ 30’000. Это «слегка» больше, чем число атомов в нашей солнечной системе. При любом алгоритме численной оптимизации, чтоб просто выполнить исследование окрестностей дискретной функции покоординатным спуском, вы выполните не менее, чем 8'000 операций. Более того, оценку целевой функции вы не способны выразить через матрицу переходов, т.к. у вас есть окна допустимых решений, т.к. количество портов назначения более одного. По факту же, вы будете считать каждую пермутацию примерно такое же время за которое вы пройдете жадный алгоритм.

При этом предельное «отлежание» от оптимума у жадного гамильтонова пути математически доказано, а наихудший гамильтонов путь может «отлежать» сколь угодно далеко.

[Larsonsager]

Во-вторых, ваша задача размещения груза на контейнеровозе симплексом не решается. Это задача дискретной математики в пространстве натуральных чисел. В математике вообще пока нет ни одного непереборного алгоритма, который бы находил min/max решение подобных задач за менее чем n! шагов. Увы. Однако я безумно рад за ваших одногруппников, которым, с ваших слов, таки удавалось это проделывать.

- Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал, что
она н-не имеет р-решения.
- Мы сами знаем, что она не имеет решения, - сказал Хунта, немедленно
ощетинившись. - Мы хотим знать, как ее решать.

Никому не нужно решать подобные задачи строго. Из того, что задача о рюкзаке или коммивояжера не решаются строго за приемлемое время, не следует, что они вообще не решаются за приемлемое время. Просто вместо глобального минимума находится тот из локальных, что мало отличается от глобального. И вот тут как раз может вступить в действие та часть алгоритмики, которая немного ближе к дата-сайнсу, чем просто ваши симплекс-методы: рандомизированные алгоритмы, например. А еще некоторые оптимизационные задачи в пространстве натуральных чисел решаются релаксацией до действительных и применением эвристик по превращению действительного решения в натуральное.

[tessob]

Просто вместо глобального минимума находится тот из локальных, что мало отличается от глобального.

Скажете как это посчитать!?

[Larsonsager]

Умные математики посчитали. Вы читаете их работу и говорите: ага, шанс попасть в <(1 + eps) от глобального минимума - 3%. Шанс не попасть, соответственно 0.97. Итого минимум результатов ста случайных экспериментов с вероятностью 95% лежит в терпимом диапазоне, минимум результатов трёхсот экспериментов вас устраивает с вероятностью 99.99%.

[tessob]

Умные математики посчитали. Вы читаете их работу и говорите: ага, шанс попасть в <(1 + eps) от глобального минимума - 3%. Шанс не попасть, соответственно 0.97. Итого минимум результатов ста случайных экспериментов с вероятностью 95% лежит в терпимом диапазоне, минимум результатов трёхсот экспериментов вас устраивает с вероятностью 99.99%.

П####Ц!

[Larsonsager]

Что вас не устраивает? Так, например, решают задачу о рюкзаке за полиномиальное время. Но за этим хоть математика стоит.
На практике коммивояжер решается так же, только за этим еще и математики никакой нет. Запускают пятьсот раз какой-нибудь отжиг безо всяких ветвей и границ из разных стартовых состояний и выбирают лучший вариант.

Да даже простые числа именно так и ищут. Берут наугад взятое число и тестируют его Миллиром-Рабином столько раз, сколько сочтут разумным.

[Lisa]

Сколько раз я зарекался не спорить с искусственным интеллектом….

Lisa, вам формально нужно найти оптимальный гамильтонов путь в полносвязном графе в 8’000 вершин. Число возможных гамильтоновых путей у такого графа будет примерно 10 ^ 30’000. Это «слегка» больше, чем число атомов в нашей солнечной системе. При любом алгоритме численной оптимизации, чтоб просто выполнить исследование окрестностей дискретной функции покоординатным спуском, вы выполните не менее, чем 8'000 операций. Более того, оценку целевой функции вы не способны выразить через матрицу переходов, т.к. у вас есть окна допустимых решений, т.к. количество портов назначения более одного. По факту же, вы будете считать каждую пермутацию примерно такое же время за которое вы пройдете жадный алгоритм.

При этом предельное «отлежание» от оптимума у жадного гамильтонова пути математически доказано, а наихудший гамильтонов путь может «отлежать» сколь угодно далеко.

Вы шутите, да? Вы хоть что-нибудь знаете про современные методы Исследования Операций, а? Ну хоть что-нибудь?

[tessob]

Что вас не устраивает? Так, например, решают задачу о рюкзаке за полиномиальное время. Но за этим хоть математика стоит.

Дело Петрика живет и крепнет.

Вы меня обижаете.

Простите, не хотел.
Просто, Larsonsagerы имеют такие же шансы попасть в индустрию, как вы или я. По факту даже бОльшие. Их просто тупо больше. Я хотел привести Физику-Лирику примеры текущей ситуации, а получилось, что примеры привели Larsonsager и Lisa. Не исключено, что Ф-Л сейчас "бьется в алгебраическом припадке перед монитором". Он работу найти не может, просто на просто, а они на Абелевку претендуют.

Вы шутите, да? Вы хоть что-нибудь знаете про современные методы Исследования Операций, а? Ну хоть что-нибудь?

Ну давайте, не томите, как решать такие задачи?
Только имейте ввиду, что на земле всего примерно 10 ^ 30 FLOPS вычислительных мощностей.

[Larsonsager]

Что вас не устраивает? Так, например, решают задачу о рюкзаке за полиномиальное время. Но за этим хоть математика стоит.

Дело Петрика живет и крепнет.

Хорошо, что здесь все анонимные, правда? А то работодатели могут узнать, насколько tessob отстал от жизни.

Просвещайтесь:
http://theory.stanford.edu/~tim/w16/w16.html
Lecture 15 (Tue Feb 23): Introduction to approximation algorithms. Scheduling, knapsack, Steiner tree, set coverage, influence maximization.
CS161-level videos on NP-completeness (Part XVI) and approximation algorithms for the knapsack problem (Part XVIII).

Ну или прямо тут:
https://books.google.com/books?id=EILqA ... ck&f=false

[tessob]

Larsonsager, давайте вы просто выложите сюда на форум полиномиальный алгоритм для сета Р08 реализованный на любом языке? Там размерность пространства решений всего 24, а не 8'000.