метод решения ЗЛП в булевых переменных

[kym]

Здравствуйте!
Помогите, пожалуйста! Нужен эффективный метод решения задачи линейного программирования в булевых переменных для задачи размерности порядка 10тыс переменных на 100тыс ограничений. Особенность задачи: в оптимальном решении прогнозируется наличие единиц на порядок меньше, чем нулей. В данный момент используется метод ветвей и границ, но возникает переполнение массива вершин, которые стоят в очереди на ветвление.

[e7e5]

kym писал(а):

Здравствуйте!
для задачи размерности порядка 10тыс переменных на 100тыс ограничений.

А почему именно столько переменныхи и ограничений?

[ddn]

kym писал(а):

Нужен эффективный метод решения задачи линейного программирования в булевых переменных

Это типа все переменные $a$, $b$ и $c$ принимают значения $0$ и $1$, а сложение и умножение двоичные? Тогда это задача целочисленного линейного программирования по модулю $2$. Я конечно не специалист, но в ЦЛП не существует эффективных методов точного решения.

[kym]

e7e5 писал(а):

kym писал(а):

Здравствуйте!
для задачи размерности порядка 10тыс переменных на 100тыс ограничений.

А почему именно столько переменныхи и ограничений?

так вот задача разворачивается...

Добавлено спустя 1 минуту 28 секунд:

Цитата:

в ЦЛП не существует эффективных методов точного решения.

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

[ha]

ddn писал(а):

Тогда это задача целочисленного линейного программирования по модулю $2$.

Лично я не могу себе представить неравенства и вычисление по модулю одновременно. Может все-таки задача целочисленного программирования при условиях $0\le x_i\le 1$.