Ускорить симплексный алгоритм

Я играл с большим симплексного алгоритма я нашел здесь: https://github.com/JWally/jsLPSolver/Ускорить симплексный алгоритм

Я создал jsfiddle, где я поставил модель, и я решить эту проблему с помощью алгоритма выше. http://jsfiddle.net/Guill84/qds73u0f/

Модель в основном представляет собой длинный массив переменных и ограничений. Вы можете подумать об этом, пытаясь найти самый дешевый способ перевозки пассажиров между различными узлами (странами), где у каждой страны минимальный спрос на пассажиров, максимальный запас пассажиров, и у каждого соединения есть цена. Мне все равно, куда идут пассажиры, я просто хочу найти самый дешевый способ их распространения. Для достижения этой цели я использую следующую минимизируя цель:

model = { 
     "optimize": "cost", 
      "opType": "min", 
      "constraints": { \\etc...

Я доволен моделью и ответом, алгоритм ... но последние занимает очень много времени, чтобы запустить (> 15 секунд ...) Есть ли какой-либо возможный способ ускорить расчет?

С уважением, спасибо. G.

источник

2015-04-02 Noobster

Выяснил это. Самой дорогой частью кода была операция поворота; который, как оказалось, выполняет большую работу по обновлению матрицы, добавив 0. Выполняя небольшую логику, чтобы предотвратить это, я потерял время выполнения на узле от ~ 12 секунд до ~ 0,5.

for (i = 0; i < length; i++) { 
     if (i !== row) { 
      pivot_row = tbl[i][col]; 
      for (j = 0; j < width; j++) { 


       // No point in doing math if you're just adding 
       // Zero to the thing 


       if (pivot_row !== 0 && tbl[row][j] !== 0) { 
        tbl[i][j] += -pivot_row * tbl[row][j]; 
       } 
      } 
     } 
    }

источник

2015-04-14 22:18:52 JWally

Джастин это действительно впечатляет.Я очень надеюсь, что когда-нибудь мы сможем работать вместе, мне нужно многому научиться у вас. – Noobster

Звучит так, как будто у вас есть minimum-cost flow problem. Там есть разумный вид TopCoder tutorial on min-cost flow от Zealint, который покрывает алгоритм отмены цикла, который был бы моей первой рекомендацией (если предположить, что для вашего LP-решателя нет быстрой оптимизации). Если это все еще слишком медленно, есть целая литература.

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

источник

2015-04-02 13:27:20

Hello David! Да, это действительно проблема с минимальными затратами. Я не пытаюсь изобретать колесо или писать с нуля. На самом деле я не знаю, как начать, поэтому я использую симплекс выше. Мне это нравится, потому что я могу передать его мои переменные и ограничения непосредственно в виде массива. Есть ли причина, по которой она так долго заканчивается? В качестве отправной точки я хотел бы работать над выше, прежде чем рассматривать другие варианты! – Noobster

@Noobster Решатель LP, который вы используете, - это игрушка, но, глядя на нее, я не вижу никаких серьезных проблем с производительностью. Я отредактировал свое предложение в ответ. –

@Noobster, я рад, что кто-то, кроме меня, получает пользу от моей симплексной библиотеки. Я прошел, посмотрел на него и обходил ту же самую рабочую среду, что и вы (10-20 секунд). Был фрагмент кода, который бесполезно переносил массив, чтобы превратить RHS в 1d-массив из массива 2d. С вашей проблемой эта убитая производительность съела 60 мсек каждый раз, когда это произошло (по вашей проблеме 137 раз).

Я исправил это в репо и вижу время работы около 2 секунд. Вероятно, есть тонна оптимизации очистки кода, вроде этого, которая должна произойти, но набор проблем, которые я построил для этого (http://mathfood.com), настолько малы, что я никогда не знал, что это проблема. Благодаря!

Для чего стоит, я взял симплекс-альго из учебника колледжа и превратил его в код; часть MILP появилась из Википедии.

источник

2015-04-02 18:08:37 JWally

Ускорить симплексный алгоритм

ответ

Смежные вопросы