В проблеме ILP возможно ли ограничить / оштрафовать число используемых переменных решения?

Question

Я пытаюсь настроить проблемы минимизации с ограничениями на количество используемых переменных решения.

Возможно ли сделать это в рамках линейного программирования?Или я вынужден использовать более сложную структуру оптимизации?

Предположим, что все x являются неотрицательными целыми числами:

x1, x2, x3, x4, x5 >= 0

1) Ограничение: возможно ли установить проблему так, чтобы не более 3 x были ненулевыми?например, если

x1 = 1, x2 = 2, x3 = 3 then x4 = 0 and x5 = 0 

2) Штраф: предположим, есть 3 возможных решения проблемы:

a) x1 = 1, x2 = 2, x3 = 3, x4 = 0, x5 = 0
b) x1 = 2, x2 = 3, x3 = 0, x4 = 0, x5 = 0
c) x1 = 3, x2 = 0, x3 = 0, x4 = 0, x5 = 0

Из-за простоты решение (c) предпочтительнее решения (b), котороепредпочтительнее решения (а), то есть «использование» меньшего количества переменных решения является предпочтительным.

В обоих вопросах я упростил задачу до 5 х, но в действительности у меня есть 100 х для оптимизации.

Я могу видеть, как я мог бы сделать это в общей структуре оптимизации с использованием индикаторных / дельта-переменных, но не могу понять, как это сделать в линейном программировании.Любая помощь будет оценена!

Answer 1

Вы можете создавать свои собственные индикаторы (и без ограничений для некоторых очень специфических проблем, которые вам также нужны).

Предполагая, что есть верхняя граница ub_i для всех ваших целочисленных переменных x0, x1, ..., xn, введите двоичные переменные u0, u1, ... un и добавьте новые ограничения, такие как:

u1 * ub_1 >= x1
u2 * ub_2 >= x2
...

(константы ub_x часто называют константами big-M ; но мы сохраняем их как можно меньшими для лучшей релаксации)

Тогда ваше ограничение кардинальности просто:

sum(u) <= 3

Конечно, вы также можете использовать эти переменные u в любом дизайне штрафов, который вы захотите использовать.