Экономные границы в смешанном целочисленном линейном программировании

Question

В настоящее время я использую lp_solve и его R API для установки и решения задачи линейного программирования.

Для целей этого вопроса настройтегораздо более простая задача линейного программирования полезна, поэтому давайте возьмем этот игрушечный пример, с которым вам предлагается поиграть:

 minimize     3 x1 -   x2
 subject to    -x1 + 6 x2 - x3 +   x4 >= -3
                     7 x2      + 2 x4 <=  5
                x1 +   x2 + x3        >=  1
                            x3 +   x4 <=  2

Более того, x1, x2, x3 и x4должны быть целыми числами.

Это можно решить очень легко, но что, если мне нужно добавить ограничение, которое говорит:

abs(x1) + abs(x2) + abs(x3) + abs(x4) <= 3

Как бы вы добавили это ограничение и / иликак бы вы справились с решением для соблюдения такого дополнительного ограничения?

Answer 1

Ваша проблема в настоящее время

minimize     3 x1 -   x2
 subject to    -x1 + 6 x2 - x3 +   x4 >= -3
                     7 x2      + 2 x4 <=  5
                x1 +   x2 + x3        >=  1
                            x3 +   x4 <=  2

Чтобы добавить ограничение

abs(x1) + abs(x2) + abs(x3) + abs(x4) <= 3

Введите некоторые дополнительные переменные и переписайте ограничение:

 x1<=z1
-x1<=z1
 x2<=x2
-x2<=z2
 x3<=z3
-x3<=z3
 x4<=z4
-x4<=z4
z1+z2+z3+z4<=3

z переменные будут связываться только с положительными (абсолютными) значениями x переменных.