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

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

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

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

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

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

С уважением и спасибо. ГРАММ.


javascript arrays algorithm mathematical-optimization simplex
person Noobster    schedule 02.04.2015    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Догадаться. Самой дорогой частью кода была операция поворота; что, как оказалось, проделало большую работу по обновлению матрицы, добавив 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];
                }
            }
        }
    }
person JWally    schedule 14.04.2015
comment
Джастин, это действительно впечатляет. Я очень надеюсь, что когда-нибудь мы поработаем вместе, мне есть чему у вас поучиться. - person Noobster; 15.04.2015

arrow_upward
4
arrow_downward

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

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

person David Eisenstat    schedule 02.04.2015
comment
Привет Дэвид! Да, это действительно проблема потока с минимальными затратами. Я не пытаюсь изобретать велосипед или писать алгоритм с нуля. На самом деле я не знаю, с чего начать, поэтому я использую симплекс выше. Мне это нравится, потому что я могу передать ему свои переменные и ограничения непосредственно в виде массива. Есть ли причина, почему это занимает так много времени? В качестве отправной точки я хотел бы поработать над вышеизложенным, прежде чем рассматривать другие варианты! - person Noobster; 02.04.2015
comment
@Noobster Решатель LP, который вы используете, - это игрушка, но, взглянув на него, я не увидел никаких явных проблем с производительностью. Я отредактировал свое предложение в ответе. - person David Eisenstat; 02.04.2015

arrow_upward
3
arrow_downward

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

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

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

person JWally    schedule 02.04.2015