Моделирование операторов IF/THEN в линейном программировании

Question

Учитывая набор булевых переменных X = {x0, x1, .... xn}, где каждая переменная x \ in X принадлежит одной группе G = {g0, g1,. .., г}, г \ подмножество X.

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

Как я могу моделировать ограничение в LP, который требует все переменные, принадлежащие одной и той же группе g \ в G, должны быть установлены равными 0 или 1? Точнее, никакие две логические переменные из g \ in G не могут иметь разные значения.

P.S: Вышеупомянутая проблема - это просто упрощение реальной проблемы, которая включает дополнительные ограничения, кроме указанных выше.

Answer 1

Такие ограничения не являются выпуклыми и поэтому не могут быть сформулированы как LP. Однако это случай ILP (Integer LP), то есть задача NP, но на практике ее можно решить для разумного числа переменных.

Вы можете даже довольно легко расширить задачу LP на ILP, ограничив 0 <= x <= 1, и когда оптимальный не является ни 0, ни 1, вы решаете два LP, один с фиксацией x на 0, другой на 1 и выбираете лучший , Вы повторяете (recurse), пока не будут выполнены все ваши целые условия. (Для получения дополнительной информации или более эффективных способов использования Google).

---

Edit: Учитывая ваше конкретное присваивание проблемы, почему would't вы просто положить все переменные, равные 1? Это, очевидно, максимум, и для всех возможных групп он считает, что никакие два значения не различаются (так как все равны 1s).