Существуют различные решатели линейного программирования, среди которых lpSolve или GLPK. Это общие LP-решатели, которые подходят для многих целей, но есть ли специализированный LP-решатель для двоичного случая?
В качестве примера, моя проблема заключается в поиске минимального числа строк, которые охватывают все столбцы матрицы, что-то вроде:
0 1 0 1
1 0 0 1
1 0 1 0
Видно, что первый и третий ряды охватывают все четыре столбца, причем второй ряд не имеет значения. Обозначив три строки как A, B и C, задача сводится к решению системы неравенств:
B + C >= 1
A >= 1
C >= 1
A + B >= 1
Это дает решение: A = 1; B = 0; C = 1
(что означает, что минимальное количество строк равно 2).
Заранее спасибо, Адриан