Есть ли способ установить для переменной решения значение true, если переменная находится в диапазоне в целочисленной линейной программе?

У меня есть ограниченная переменная с целочисленным значением, назовите ее X. (Где-то около 0<=X<=100)

Я хочу иметь двоичную переменную, назовите ее Y, чтобы Y=1, если X >= A и X <= B, иначе Y=0.

Лучшее, что я придумал до сих пор, это следующее (где T<x> вводятся двоичные переменные, а M - большое число)

(minimize Y)
(X - A) <= M*Ta
(B - X) <= M*Tb
Y <= Ta
Y <= Tb
Y >= Ta + Tb - 1

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

Это... Вроде работает, но имеет пару существенных недостатков. В частности, это не определено строго - Y может быть 1, даже если X находится за пределами диапазона.

Итак: есть ли лучший способ сделать это? В частности: есть ли способ строго определить его, или, если нет, способ, по крайней мере, предотвратить ложные срабатывания?

Изменить: для уточнения: A и B являются переменными, а не параметрами.


linear-programming integer-programming
person TLW    schedule 18.06.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я думаю, что ниже работает.

(I) A * Y <= X <= B * Y + 100 * (1 - Y)

(II) (X - A) <= M * Ta

(III) (B - X) <= M * Tb

(IV) Y >= Ta + Tb - 1

Итак, X < A делает:

(I)Y=0

и (II), (III), (IV) не имеют значения.

X > B производит:

(I) Y = 0

и (II), (III), (IV) не имеют значения.

A <= X <= B производит:

(I) Y = 1 or Y = 0

(II) Ta = 1

(III) Tb = 1

(IV) Y = 1

person Ioannis    schedule 19.06.2014
comment
К сожалению, умножение переменных означает, что оно больше не является линейным. (АY, ВY). Тем не менее, я мог бы поиграть с ним, чтобы избежать этого. - person TLW; 19.06.2014
comment
Извините, я думал, что по соглашению «A» и «B» обозначают параметры, а не переменные, потому что это первые буквы алфавита. Сейчас я на мобильном телефоне, но можно линеаризовать произведения переменных как таковые. Вы могли бы хотеть использовать приемы целочисленного программирования Google Aimms для получения дополнительной информации. - person Ioannis; 19.06.2014
comment
Упс. Извините, я неопытен в линейном программировании и поэтому не знаком с соглашениями - я отредактирую вопрос, чтобы было ясно, что A и B являются переменными. Я посмотрел на приемы целочисленного программирования и опубликовал что-то, что, кажется, работает как решение. Не могли бы вы посмотреть на него, когда у вас будет возможность? - person TLW; 19.06.2014

arrow_upward
1
arrow_downward

Переписав ответ Ионниса в линейной форме, расширив умножение двоичных переменных на непрерывную переменную:

  1. Tc <= M*Y
  2. Tc <= A
  3. Tc >= A - M*(1-Y)
  4. Tc >= 0
  5. Tc <= X
  6. Td <= M*Y
  7. Td <= B
  8. Td >= B - M*(1-Y)
  9. Td >= 0
  10. X <= Td + 100*(1-Y)
  11. (X - A + 1) <= M * Ta
  12. (B - X + 1) <= M * Tb
  13. Y >= Ta + Tb - 1

Кажется, это работает, хотя у меня еще не было возможности расширить его, чтобы доказать это. Кроме того, некоторые из этих ограничений могут быть ненужными; Я не проверял.

Расширение, которое я сделал, было в соответствии со следующим правилом:

Если b — двоичная переменная, а c — непрерывная, и 0 <= c <= M, то y=b*c эквивалентно следующему:

  1. y <= M*b
  2. y <= c
  3. y >= c - M*(1 - b)
  4. y >= 0
person TLW    schedule 19.06.2014
comment
Это правильно (+1). Мне вот интересно, а зачем вам такое условие? Если A и B переменные, какова их физическая интерпретация? Возможно, вы сможете сформулировать проблему в целом гораздо проще, если только A и B не имеют других атрибутов, не раскрытых здесь. Кстати, я бы предложил Z и W вместо A и B, а также использовать строчные буквы вместо заглавных (для матриц обычно используются заглавные). - person Ioannis; 20.06.2014
comment
Кстати, убедитесь, что вы принимаете свой ответ, если он решит вашу проблему! - person Ioannis; 20.06.2014
comment
@loannis - это для решения головоломки, похожей на нонограмму, но на непрямоугольной сетке. Самый простой способ представить это, с которым я столкнулся, - это целочисленное значение, указывающее, где начинается каждый блок в подсказке, с ячейкой, установленной, если одно из целочисленных значений находится в диапазоне, в котором оно установило бы ячейку. - person TLW; 27.06.2014