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

Question

Как часть какого-то реального процесса рендеринга для программы, работающей на iOS/Android, написанной на C/C++, мне нужно решить множество крошечных задач линейного программирования с 5 переменными и 2 ограничения, т.е.

minimize: a_0*x + b_0*y + c_0*z + d_0*u + e_0*v 
subject to: 
    p_1 = a_1*x + b_1*y + c_1*z + d_1*u + e_1*v 
    p_2 = a_2*x + b_2*y + c_2*z + d_2*u + e_2*v 
    0 <= x <= x_max 
    0 <= y <= y_max 
    0 <= z <= z_max 
    0 <= u <= u_max 
    0 <= v <= v_max 

Я бы хотел решить эту проблему быстро, используя разрешительную лицензию.

Поиск Я нашел линейную библиотеку оптимизации от Google glop (Apache2), но

1. это довольно большая зависимость, 7MB кода для чего-то настолько мал
2. Я обеспокоен погона установки проблемы с ЛП.

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

Есть ли крошечная библиотека с небольшими накладными расходами, которые я мог бы использовать? Или, альтернативно, как я сломаю математику?

Answer 1

Решение может быть разумно жестко закодированы следующим образом:

• занимают первые два линейных ограничений и выбрать три переменные (есть 10 способов сделать это), к которому вы назначаете 0 или не более (есть 8 способов сделать это). Это приводит к 10 элементарным системам 2x2 с 8 различными правыми сторонами.

• проверить, допустимы ли эти решения (два вычисленных неизвестных в диапазоне от 0 до макс.).

• поддерживать допустимое решение, которое минимизирует цель.

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

Answer 2

Я бы рекомендовал вам использовать Sensitivity Analysis for Linear Programming (пример с Excel - here). Идея состоит в том, чтобы решить LP: min{ cx: Ax>= b } для заданного ввода (c,A,b) и найти диапазоны параметров (используя формулы из приведенной выше ссылки), для которых решение остается оптимальным. Если вы знаете приблизительные возможные границы ваших параметров, то это вопрос решения ряда ЛП и хранения диапазонов и решений.