Android — быстрое решение многих крошечных задач линейного программирования
В рамках некоторого процесса рендеринга в реальном времени для программы, работающей на 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), но
- это довольно большая зависимость, 7 МБ кода для чего-то такого маленького
- Я обеспокоен накладными расходами на настройку проблем с LP.
Я чувствую, что это можно решить напрямую, просто перечислив вершины и проверив целевую функцию, но я не могу обернуть голову вокруг этого.
Можно ли использовать крошечную библиотеку LP с небольшими накладными расходами? Или, как альтернатива, как бы я сломал математику?
Решение
Решение может быть разумно закодировано следующим образом:
-
возьмите первые два линейных ограничения и выберите три переменные (есть 10 способов сделать это), которым вы назначаете либо 0, либо максимум (есть 8 способов сделать это). Это приводит к 10 элементарным системам 2х2 с 8 различными правыми сторонами.
-
проверить, допустимы ли эти решения (два вычисленных неизвестных в диапазоне от 0 до max).
-
сохранить допустимое решение, которое минимизирует цель.
Я не удивлюсь, что тщательно микрооптимизированный и развернутый код может превзойти универсальный решатель (симплексный алгоритм).
Другие решения
Я бы порекомендовал вам использовать Анализ чувствительности для линейного программирования (пример с Excel Вот). Идея состоит в том, чтобы решить LP: min{ cx: Ax>= b } для данного входа (c,A,b) и найдите диапазоны параметров (используя формулы из ссылки выше), для которых решение остается оптимальным. Если вы знаете приблизительные возможные границы ваших параметров, тогда вам нужно решить ряд LP и сохранить диапазоны и решения.