Указание сложных ограничений в cvxpy приводит к ошибке строгих неравенств

Я пытаюсь воссоздать целочисленную задачу линейной оптимизации, используя cvxpy, которую я описал в Excel - Скриншот Excel. Обратите внимание, что это фиктивный пример, фактический набор данных будет содержать тысячи переменных. Не обращайте внимания на решение в ячейке K5 электронной таблицы, так как Excel Solver не может предоставить целочисленные решения.

Учтите, что 9 переменных разделены на 3 сегмента. Обратите внимание, что моя цель с ограничениями 1–3 состоит в том, чтобы либо было как минимум 2 из 3 единиц для набора переменных, либо все значения равны 0. Например, a, b, c должны быть либо 1,1,1 или 1, 1, 0 или 1,0,1 или 0, 1, 1 или 0, 0, 0.

import numpy as np
import cvxpy as cp
import cvxopt 

coefs= np.array([0.7, 0.95, 0.3, 2, 1.05, 2.2, 4, 1, 3])

dec_vars = cp.Variable(len(coefs), boolean = True)

constr1 = np.array([1,1,1,0,0,0,0,0,0]) @ dec_vars == 2 * max(dec_vars[0:3]) 
constr2 = np.array([0,0,0,1,1,1,0,0,0]) @ dec_vars == 2 * max(dec_vars[3:6])
constr3 = np.array([0,0,0,0,0,0,1,1,1]) @ dec_vars == 2 * max(dec_vars[6:9])
constr4 = np.ones(len(coefs)) @ dec_vars >= 2

Когда я подбегаю сюда, я получаю NotImplementedError: Strict inequalities are not allowed. ошибку


python integer-programming cvxpy
person matsuo_basho    schedule 22.12.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Основная проблема заключается в использовании вами python max, который пытаются оценить до достижения cvxpy. Вы не можете использовать для cvxpy-объектов какие-либо собственные функции python. max(cvx_vars) не поддерживается, как abs(cvx_vars) и многое другое.

В cvxpy есть max-function, а именно: cp.max(...), но я не понимаю, что вы пытаетесь сделать и как вы этого добьетесь, используя max. См. ниже...

Обратите внимание, что моя цель с ограничениями 1–3 состоит в том, чтобы либо было как минимум 2 из 3 единиц для набора переменных, либо все значения равны 0. Например, a, b, c должны быть либо 1,1,1 или 1, 1, 0 или 1,0,1 или 0, 1, 1 или 0, 0, 0.

Это, как правило, требует некоторого дизъюнктивного рассуждения.

Подход А

Общий подход заключается в использовании двоичной индикаторной переменной вместе с выражением на основе big-M:

is_zero = binary aux-var

sum(dec_vars) <= 3 * is_zero
sum(dec_vars) >= 2 * is_zero

Подход B

В качестве альтернативы, можно также смоделировать это (без дополнительных переменных):

a -> b || c
b -> a || c
c -> a || b

значение: если есть ненулевое значение, необходимо как минимум еще одно ненулевое значение. Это выглядело бы так:

(1-a) + b + c >= 1
(1-b) + a + c >= 1
(1-c) + a + b >= 1
person sascha    schedule 23.12.2020
comment
Подход Б работает. Для подхода A не могли бы вы уточнить синтаксис binary aux-var. - person matsuo_basho; 23.12.2020
comment
is_zero - это просто новая переменная, такая как aux_var = cp.Variable(1, boolean = True) (хотя, возможно, по одной для каждого из ваших сегментов). Эта двоичная переменная принимает решение: все нули или другой случай (ограничения затем накладывают 0 везде или ограничивают сумму) - person sascha; 23.12.2020
comment
Это главным образом потому, что подход A кажется намного более элегантным. Учтите, что на самом деле у меня есть тысячи переменных, и подход B требует, чтобы я написал правило для каждой из них, в отличие от общего правила для корзины. - person matsuo_basho; 23.12.2020
comment
Да, эти подходы различаются по сценариям использования. - person sascha; 23.12.2020
comment
Что я не понимаю, так это то, что теперь у нас есть отдельная переменная для каждой переменной, а также переменная, указывающая, равно ли ведру 0 или нет. Это кажется избыточным и более сложным, чем необходимо. Я предполагаю, что подход B не имеет этой проблемы, но проблема с B заключается в том, что нужно запрограммировать отдельное ограничение для каждой из 15K переменных. - person matsuo_basho; 23.12.2020
comment
У вас есть одна вспомогательная / вспомогательная / отдельная переменная для каждого дизъюнктивного рассуждения, которое вам нужно (не для каждой переменной!). Если у вас есть n элементы / корзины / что угодно (состоящее из m двоичных переменных внутри), где вам нужно принудительно применить 0 or bounds on the sum of m_of_n, вам понадобится n aux-vars. Оба подхода представляют собой просто линеаризацию некоторого дизъюнктивного пространства, которое необходимо, несмотря ни на что. Один использует дополнительные переменные, другой нет, но в некоторых случаях масштабируется хуже с точки зрения ограничений. - person sascha; 23.12.2020