Решение системы уравнений/неравенств

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

Есть метод branch and bound, но он не полиномиальной сложности.

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

Сейчас времени нет, вечером может посмотрю как свести к задаче ЦЛП.

Вот сведение данной задачи к задаче целочисленного линейного программирования (если я ничего не напутал).

Пусть количество элементов A = |A|, B = |B|.
Пусть M = |A| * |B|. Введем M дополнительных целочисленных переменных yi, i = 1...M, yi = {-1, 1}.
Всего пар V_i из A, V_j из B M штук, дадим каждой число k от 1 до M.
Для каждой k-ой пары V_i из A, V_j из B введем ограничения y_k * (V_i - V_j) > 0.
минимизируем w_1 + ... + w_n + 0 * y_1 + ... 0 * y_M.

да, еще забыл об ограничениях w_i > 0, для i = 1...n.

И еще, если нужно, вечером могу посмотреть, у меня были где-то мои старые реализации метода ветвей и границ и метода Гомори, правда на OCaml'е...

Эх подзабыл уже... залажал я с решением, это уже НЕ ЛИНЕЙНАЯ задача.

Итак, дубль два. Главная проблема записать то, что для каждой пары V_i из A, V_j из B должно выполняться V_i - V_j != 0. Делаем это так:

Пусть количество элементов A = |A|, B = |B|. Пусть M = |A| * |B|. Введем M дополнительных целочисленных переменных yij, i = 1..|A|, j = 1..|B|, yij = {0, если в решении получается V_i >= V_j; 1, если V_i < V_j}. Пусть D - достаточно большое число, тогда нужное нам ограничение для каждой пары запишется в виде системы двух неравенств: D * yij + (V_i - V_j) > 0; D * (1 - yij) + (V_j - V_i) > 0.

Вот как это работает: если на оптимальном решении y_ij = 0, то второе неравенство избыточно, а первое активно, получаем V_i - V_j > 0; если же на оптимальном решении y_ij = 1, то первое неравенство избыточно, а второе активно и оно раскрывается в V_j - V_i > 0.

Дополняем эти 2 * M неравенств ограничениями на положительность w_i и минимизируем w_1 + ... + w_n + 0 * y_1 + ... 0 * y_M.

P.S. монолог какой-то получается, 5 сообщения подряд.

Эх подзабыл уже... залажал я с решением, это уже НЕ ЛИНЕЙНАЯ задача.

Итак, дубль два. Главная проблема записать то, что для каждой пары V_i из A, V_j из B должно выполняться V_i - V_j != 0. Делаем это так:

Пусть количество элементов A = |A|, B = |B|.
Пусть M = |A| * |B|. Введем M дополнительных целочисленных переменных yij, i = 1..|A|, j = 1..|B|,
yij = {0, если в решении получается V_i >= V_j; 1, если V_i < V_j}.
Пусть D - достаточно большое число, тогда нужное нам ограничение для каждой пары запишется в виде системы двух неравенств:
D * yij + (V_i - V_j) > 0;
D * (1 - yij) + (V_j - V_i) > 0.

Вот как это работает:
если на оптимальном решении y_ij = 0, то второе неравенство избыточно, а первое активно, получаем V_i - V_j > 0;
если же на оптимальном решении y_ij = 1, то первое неравенство избыточно, а второе активно и оно раскрывается в V_j - V_i > 0.

Дополняем эти 2 * M неравенств ограничениями на положительность w_i и минимизируем w_1 + ... + w_n + 0 * y_1 + ... 0 * y_M.

P.S. Уже 6-е сообщение подряд :)

Спасибо за подсказку.