Как использовать Lpsolve ide

Обновлено: 21.11.2024

Недавно Сяо Бянь изучала симплекс-метод в исследовании операций.

поэтому, скоро мое сердце не может не биться.

Мне пришлось взять ручку и бумагу и подумать,

Важный вопрос:

Как собрать полные 13？

Программист 30 фраз, какую из них вы произносите чаще всего?
Полное понимание того, как разрабатывать WebService с помощью среды Apache CXF
Настройка мониторинга базы данных Druid в проекте
[Интервью с БД 375] когда объект данных a блокируется исключительно транзакцией, другие транзакции блокируются ()
[Интервью с БД 330] какое из следующих утверждений о концептуальной модели неверно ()
[Интервью с БД 371] Какие из следующих операций восстановления будет выполнять СУБД, чтобы обеспечить правильность и согласованность данных? （）
[Интервью с БД 376]. Чтобы создать индекс с максимальной производительностью, завершите следующие предложения:
[Интервью с БД 328] какое из следующих утверждений о модели данных неверно ()
[Интервью с БД 374] для модели данных следующее утверждение неверно ()
Как узнать размер чистого устройства?

Что такое символьное устройство, блочное устройство и простое устройство?

Minio закрывает отображение списка общедоступных сегментов (браузер S3)

Вы знаете, что я = я + +; Что это значит? Принцип не так прост, как вы думаете

Многие говорят, что хранимые процедуры сложны? Достаточно внимательно прочитать эту статью

Используйте относительную единицу длины REM для компоновки содержимого веб-страницы

Сегодня у тебя все отлично.

Настоящий бой | рука об руку, чтобы научить вас, как использовать артефакт mitmproxy для захвата сумок

[Инструмент для ПК] отличная аннотация кода уровня God, красивый и практичный инструмент аннотации кода, инструмент для создания логотипа кода

Photoscape — простой в использовании, экологичный, бесплатный и мощный фоторедактор

[DIY] как сделать детскую игрушку "Сказочный цыпленок" из малинового пирога 3B+

– Могу ли я использовать lp_solve в коммерческом коде?
Да, можно. Однако прочтите МАЛЕНЬКУЮ ОБЩЕСТВЕННУЮ ЛИЦЕНЗИЮ GNU, которую вы можете найти в LGPL.txt

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

A: "Работа, в которой используется библиотека"
B: "Работа, основанная на библиотеке"

Случай A: поскольку код lp_solve не был изменен и он используется исключительно как библиотека, основанная на распространяемом исходном коде, необходимы только заметно размещенная информация об авторских правах/цитировании и ссылка на источник. Никакая часть вашего собственного кода не должна быть предоставлена, и он может быть защищен и лицензирован по вашему желанию.

Случай B1: Полный код модифицированной библиотеки lp_solve должен быть распространен или легко доступен с полными авторами и информацией о лицензии (опционально LGPL или GPL). Ваш собственный исходный код *не* должен быть включен, и он может быть защищен и лицензирован по вашему желанию.

Вариант B2: Полный код модифицированной библиотеки lp_solve должен быть распространен или легко доступен с полными авторскими правами и информацией о лицензии (опционально LGPL или GPL). Ваш собственный код *должен* быть общедоступным/способным для обратного проектирования и распространяться под лицензией LGPL или GPL.

Случай B3: поскольку код lp_solve не был изменен и он используется как связанная библиотека на основе распространяемого исходного кода, необходимы только заметно размещенная информация об авторских правах и ссылка на источник. Ваш собственный код *должен* быть общедоступным/способным для обратного проектирования и распространяться под лицензией LGPL или GPL.

Вы должны принять разумное решение на основе этого. Если ваш код подпадает под категории B2 или B3, и условия неприемлемы для вас (или компании, которую вы представляете), то наша интерпретация LGPL заключается в том, что вы должны найти подходящее коммерческое соглашение/лицензирование с правообладателями lp_solve. . Если это применимо к вам, вы можете направлять нам любое письмо о лицензировании/авторских правах, и мы решим эту проблему.

- Но сколько мне стоит lp_solve?

lp_solve абсолютно бесплатен, если вы следуете правилам LGPL. Вы, конечно, можете просить деньги за код, который вы разработали или добавили, но только за эту часть, и положения об открытости LGPL должны соблюдаться. Если вы не желаете уважать это, то единственный выход — заключить соглашение с правообладателями соответствующих частей lp_solve.

– Как следует цитировать lp_solve, когда я его использую?

Этот текст также находится в файле citations.txt

– Каковы ограничения по умолчанию для переменных?
Как и во всех (по крайней мере, симплексных) решателях lp, нижняя граница переменной по умолчанию равна 0, а верхняя граница по умолчанию не ограничена.

- Можно ли установить отрицательные границы переменных?
Да, это вполне возможно.

- Можно ли установить минус бесконечную нижнюю границу переменной?
Да, это возможно. В формате lp используйте в качестве нижней границы -Inf. В формате mps в разделе BOUNDS используйте FR.
Если вы используете интерфейс API, используйте get_infinite(lp)
Обратите внимание, что lp_solve разбивает эту переменную на 2, если имеется положительная верхняя граница или ее нет. Это делается автоматически с помощью lp_solve. Из-за этого модель становится больше, и, таким образом, может потребоваться больше времени для решения, поэтому устанавливайте нижнюю границу минус бесконечность для переменной только тогда, когда это необходимо.

- Как выглядит формат lp/mps/CPLEX?
См. файл справки

- Когда я вызываю API-вызовsolve(), на экране печатается несколько сообщений. Как я могу отключить эти сообщения?
Используйте вызов API set_verbose. По умолчанию НОРМАЛЬНЫЙ (4). Изменение этого параметра на ВАЖНО (3) уже отключает множество сообщений.

- lp_solve не может решить мою модель или решение моей модели занимает очень много времени. Что я могу сделать?
lp_solve имеет множество опций. Рассмотрите возможность использования следующего:

Используйте LUSOL bfp. См. Базовые пакеты факторизации. Это значительно улучшит скорость и числовую стабильность. Этот bfp, вероятно, будет использоваться по умолчанию в более поздней версии lp_solve.
Используйте масштабирование. См. масштабирование и set_scaling. Это значительно улучшит числовую стабильность и даже производительность.
Используйте предварительное решение. Presolve устраняет переменные и ограничения, где это возможно. Это делает модель меньше, чтобы она решалась быстрее. Но предварительное решение также занимает некоторое время, поэтому от модели зависит, будет ли общее время быстрее или даже медленнее.
Если в модели есть целочисленные переменные, обратите внимание на параметры ветвления и пропуски допусков. Особенно обратите внимание на следующие вызовы API: set_mip_gap, set_break_at_firstset_break_at_valueset_bb_floorfirstset_bb_depthlimitset_solutionlimitset_bb_rule

- Может ли lp_solve обрабатывать нелинейные уравнения?
Нет, lp_solve может обрабатывать только линейные ограничения. Однако он также поддерживает целые и полунепрерывные переменные и специальные упорядоченные наборы. Это может помочь смоделировать нелинейность.

- Может ли lp_solve обрабатывать коэффициенты?
Соотношения могут быть преобразованы в линейные уравнения. См. файл справки.

- Я получаю ошибку синтаксического анализа моего lp-файла, но я не вижу никакой ошибки в формулировке, которую я сделал. Что здесь не так?
Вы ввели свою модель через Word? Тогда проблема, вероятно, будет заключаться в том, что некоторые символы имеют коды ascii, которые не распознаются lp_solve. Например, Word заменяет знак минус (-) на другой символ, который также выглядит как знак минус, но немного длиннее. ASCII-код этого символа отличается от ASCII-кода реального знака минус, и у lp_solve есть проблемы с этим. Однако вы видите - на экране. Решение — не использовать Word для ввода вашей lp-модели. Блокнот должен быть в порядке. Лучше использовать интегрированную среду разработки LPsolve.

- lp_solve выводит вывод на экран. Могу ли я получить вывод также в файл?
Да, для этого можно использовать стандартное перенаправление. Используйте > перед именем файла, чтобы сделать это.
Например:
lp_solve input.lp >output.txt

- У меня есть ограничение, говорящее, что x совпадает с >=
Это более чем разумно. Математически 1,9999999999999999999999999999999999999999999999999 меньше 2, но в чем практическая разница с 2? Вы всегда должны учитывать ошибки округления. Если переменная определена как целое число, просто скажите x

- Когда я решаю свою модель, я получаю ошибку переполнения стека/дампа памяти/защиты. Что случилось?
Если в вашей модели есть переменные типа integer/binary/semi-cont/SOS, тогда версия 5 может решить вашу проблему. В версии 4 реализованный алгоритм ветвей и границ помещает свои ветви в стек, что может привести к переполнению стека, если это жесткая модель. Версия 5 больше не помещает ветки в стек, поэтому эта ошибка устранена.

- Версия 4 решает мои модели медленнее, чем версия 3. Что я могу сделать?
Некоторые модели действительно работают медленнее с версией 4. Версия 5 имеет несколько улучшений и работает быстрее и стабильнее. Кроме того, версия 4 всегда вычисляет информацию о чувствительности, в то время как в более ранних версиях этой функции не было. Это также занимает некоторое время. Версия 5 вычисляет чувствительность только тогда, когда эта информация специально запрашивается, что снова ускоряет процесс.

– Построение модели через интерфейс API занимает много времени. В частности, add_constraint, add_constraintex, str_add_constraint кажутся медленными. Как это можно сделать быстрее?
В версии 5 появился новый вызов API set_add_rowmode, который значительно ускоряет операции add_constraint, str_add_constraint.
Если модель строится столбец за столбцом, то настоятельно рекомендуется использовать add_columnex вместо add_column, потому что add_columnex дает возможность указывать только ненулевые элементы и значительно ускоряет построение модели, особенно если матрица разрежена (много нулевых элементов).
Если модель строится построчно, то настоятельно рекомендуется использовать add_constraintex вместо add_constraint, потому что add_constraintex дает возможность указывать только ненулевые элементы и значительно ускоряет построение модели, особенно если матрица является разреженным (много нулевых элементов).

- Может ли lp_solve дать мне "симплексную таблицу" модели?
В версии 5 есть новая функция (print_tableau), предоставляющая вам эту информацию.

- Есть ли документация по интерфейсу API?
Да, есть html (справочные) файлы. См. раздел «Файлы» в группе Yahoo.

- Какое максимальное количество строк/столбцов может обрабатывать lp_solve?
Фиксированного лимита нет. Ограничена только доступная память.

- Я использую язык программирования, который не указан в списке поддерживаемых или для которого нет примеров. Можно ли вызвать lp_solve из этого языка?
Если этот язык позволяет вызывать функции из C-dll, то это возможно. Не потому, что (пока) нет примера, это невозможно. Сообщество lp_solve всегда заинтересовано в вашем интерфейсе для вызова библиотеки lp_solve. Он не должен быть идеальным.

- Примеры для Windows не работают. Я получаю сообщение об ошибке при их запуске. Некоторые dll не могут быть найдены.
В примерах вызывается dll, содержащая подпрограммы lp_solve. Эта dll называется lpsolve*.dll и должна находиться в системе либо в каталоге приложения, либо где-то в пути.
Эта dll содержится в архиве двоичных файлов Windows в разделе файлов.

- Поддерживает ли lp_solve бесплатный формат mps?
Это возможно с версии 5.0.10.0. Раньше нельзя было. См. read_freeMPS или опции -fmps и -wfmps для программы lp_solve. Также есть утилита LPx2D, позволяющая конвертировать этот формат. См. раздел «Файлы».

- Поддерживает ли формат lp_solve lp комментарии?
Да, это так. Поместите комментарии между /* */
Он может быть где угодно в тексте, даже на нескольких строках. Как и в C,
lp_solve 4.0.1.11 и новее также поддерживает строчный комментарий C++ //

- Я сам компилирую lp_solve, но получаю ошибки ссылок, говорящие о том, что main (или _main) уже определен.
demo.c, mps2lp.c, lp2mps.c, lp_solve.c никогда не могут находиться в одном проекте. Вы должны использовать один из них с другими исходными файлами C (кроме lex.c, см. выше), чтобы сделать demo.exe, mps2lp.exe, lp2mps.exe, lp_solve.exe

- lp.c и lex.c, созданные в моей системе, отличаются от версий, которые можно найти в папке поддержки в разделе файлов. Последние версии этих файлов есть на вашем сайте?
В зависимости от платформы, используемой команды и версии команды эти файлы действительно различаются. Это не проблема. Вы можете сравнить это с компилятором. Один и тот же исходный код генерирует совершенно разные двоичные файлы, в зависимости от используемого компилятора и его версии, но программы реагируют одинаково (по крайней мере, они должны . ).

макс.: -x1 + 2x2;
С1: 2х1 + х2 -4 х1 + 4 х2

Этот формат lp является форматом программы lp_solve по умолчанию.

Другой формат — формат mps. Это совершенно другой формат, который используется многими решателями MIP. Этот формат не очень удобочитаем для нас, людей. Тот же пример, что и выше, в формате mps выглядит так:

Чтобы включить этот формат ввода в программе lp_solve, используйте параметр -mps.

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

Есть еще две демонстрационные программы: lp2mps и mps2lp. Они конвертируют файлы моделей из одного формата в другой.

Все программы lp_solve, lp2mps и mps2lp используют вызовы API библиотеки lp_solve для выполнения своих действий.

Если lp_solve запускается без входного файла, он выдает мигающий курсор и ожидает ввода. Теперь можно вводить модель в указанном формате (по умолчанию lp). Но это не очень удобно. Вы должны вводить всю модель каждый раз, когда хотите ее решить, и должны быть осторожны, чтобы не ввести никаких ошибок. Чтобы выйти из режима ввода, нажмите Ctrl Z.
Однако гораздо лучше записать вашу модель в файл на диске в вашем любимом редакторе (убедитесь, что он в текстовом формате), а затем передать этот файл в lp_solve. Например:

Также можно использовать перенаправление ввода:

Или более сложные конструкции, такие как:

gen_model здесь представляет собой написанную пользователем программу, которая выводит модель на стандартный вывод, а через символ вертикальной черты (|) этот вывод перенаправляется на lp_solve. Таким образом, в этом случае промежуточный файл не требуется.

– Нет ли более удобного интерфейса, чем программа командной строки lp_solve?
Да, благодаря Анри Гурвесту. Для версии 5 теперь есть LPsolve IDE, Windows-интерфейс к библиотеке lpsolve. Для получения дополнительной информации см. LPsolve IDE.

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

Строки ограничений и назначений могут быть помечены, например, линия x3=x1+x2+1. Вы всегда должны маркировать строки назначения. Непомеченные строки назначения могут привести к тому, что lpsolve проигнорирует ваше назначение. Маркировка может упростить отслеживание результатов lpsolve и устранение неполадок. Метки могут быть практически любой строкой, за которой следует двоеточие (:), но, вероятно, лучше придерживаться букв и цифр.

Мы также можем добавить переменные, чтобы отслеживать результаты. LP выше можно было бы написать так:

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

В последней строке указано, что x1, x2 и x3 являются целыми числами. В дополнение к int мы также можем использовать bin, чтобы указать, что переменные являются двоичными, т. е. они принимают только значения 0 и 1. Например, вместо строки int выше строка

Если для переменной нет спецификации, lpsolve будет рассматривать переменную как реальную (с плавающей запятой). Таким образом, в этом примере x4 будет реальной переменной (т. е. может принимать нецелые значения).

Часто многие переменные в решении будут равны нулю, поэтому не указывайте их в своих описаниях и добавляйте комментарий "Все остальные переменные равны нулю". после того, как вы зададите значения ненулевых переменных, например так:

Это гораздо легче читать, чем, возможно, очень длинный список, который читателю (и вам!) придется просматривать, чтобы найти нужное.

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

На пересечении бизнес-аналитики и аналитики

Информационный бюллетень BI Corner

Самые просматриваемые сообщения

Облако тегов

Я пишу новую книгу об исследовании операций. Хотя у меня пока нет названия, это будет что-то вроде Исследование операций с использованием очень хороших инструментов, за которые вам не нужно платить. В число инструментов входят R, Octave, LPsolve и Scilab (я писал обо всех них, кроме LPsolve).

Сегодня я хочу поговорить о линейном программировании с помощью LPsolve. Поскольку я недавно писал о линейном программировании («Что такое линейное программирование?»), я не буду утомлять вас подробностями формулировки задачи, а вместо этого перейду непосредственно к использованию LPSolve для получения оптимального решения. Я использую IDE-версию LPSolve, но ее можно вызывать из MATLAB, Octave, Scilab и R. В качестве примера я буду использовать задачу коммивояжера.

Упор здесь делается на инструмент, а не на проблему. Задачу коммивояжера (TSP) и ее решение можно найти в многочисленных статьях, книгах и так далее. Чтобы добавить начинку к торту, LPsolve является открытым исходным кодом.

Задача коммивояжера

MILP можно использовать для моделирования и решения многих комбинаторных задач. Возможно, самая известная или печально известная комбинаторная задача — это задача коммивояжера. Известно много способов ее решения. Здесь мы представляем путь MILP. К сожалению, никто не знает быстрых способов решить задачу коммивояжера. На рис. 1 показан поиск оптимального решения для TSP с 7 городами с использованием алгоритма ветвей и границ.

Рис. 1. Решение TSP с 7 городами с использованием простого алгоритма ветвей и границ.

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

В каком порядке Бриджит должна отправиться в тур?

Очевидный метод грубой силы для решения задачи коммивояжера — проверить все возможные маршруты и выбрать самый короткий. Очевидная проблема с этим очевидным методом заключается в том, что с городами мы должны проверять маршруты. Например, с 20 городами у нас будет 20! = 2,432,902,008,176,640 ,000 маршрутов для проверки. Таким образом, если мы американцы, мы должны проверить более 2 квинтиллионов маршрутов. Европейцам предстоит проверить более 2 триллионов маршрутов G.Это наш старый Немезида, комбинаторное проклятие.

С помощью IDE мы можем вводить LP так же, как если бы мы их писали, за исключением того, что за каждым оператором следует точка с запятой. Это можно сделать в редакторе, таком как Notepad++ (см. рис. 2), сохранить как ASCII с расширением .lp и прочитать в LP_SOLVE IDE (Файл | Открыть) или записать в исходном коде IDE (см. рис. 3) или в окнах Matrix. Вы можете скопировать и вставить его в свой редактор и сохранить как Brigette_travels.lp (текст находится в конце этой статьи). Формулировку задачи LP см. в Исследовании операций: приложения и алгоритмы, написанной Уэйном Уинстоном.

Рис. 2. LP Brigette’s Travel в Notepad++

Начнем с того, что я предполагаю, что мы не знаем, какие ограничения являются обязательными:

Рисунок 3. LPsolve IDE с окном исходного кода

Решение находится на вкладке «Результат», а затем на вкладках «Переменные», «Возможность MILP» и «Результаты». Переменные результаты показаны на рисунке 3, что дает общую стоимость тура 6243 доллара. Итак, оптимальный тур: Киев → Вааса → Париж → Рим (→ Киев). Подробнее о решении см. здесь (или дождитесь публикации моей книги).

Рисунок 4. Окно результатов LPSolve

Хорошей функцией LPSolve является вкладка Matrix. Когда вы вводите (или считываете) свой LP, LPSoleve преобразует его в матричную форму. В меню «Файл» вы можете экспортировать матрицу в Excel (например). Мне нравится делать это и запускать LP в Excel, чтобы проверить мои результаты. Вы также можете сделать это с помощью MATLAB, Octave и Scilab.

Мы также можем просмотреть ограничения (вкладка «Ограничения»), чтобы увидеть, какие из них являются обязательными. Кроме того, мы можем провести анализ чувствительности, используя результаты на вкладке «Чувствительность», где мы также найдем Dual LP. Двойные переменные иногда называют теневыми затратами или предельными затратами.

Заключение

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

Читайте также: