блок последовательных переменных, чтобы иметь одинаковое значение в смешанно-целочисленном линейном программировании

Я пытаюсь смоделировать работу системного компонента, компонент будет иметь два режима работы, назовем их 1 и 2, плюс режим ожидания 0

Нет ограничений на холостой ход, но каждый рабочий режим будет длиться ровно 3 точки временного ряда, поэтому x_ {i} = 1 означает x_ {i + 1} = x_ {i + 2} = 1 (нельзя публиковать изображения, пожалуйста используйте ссылку ниже для уравнения) режим работы 1

то же самое касается рабочего режима 2.

Например. 011102220 действителен, а 01110220 - нет.

111111 или 222222 недействительны, но об этом позаботятся в других ограничениях, связанных с ресурсами (у системы не будет достаточно ресурсов для работы более чем для трех точек временного ряда), так что проблема, связанная с принудительной установкой трех последовательных единиц или 2s в массиве переменных - это адрес, все должно быть в порядке.

Заранее спасибо,


mathematical-optimization linear-programming integer-programming
person BeWater    schedule 12.06.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

Введите новый вспомогательный двоичный вектор start_block. Этот вектор отмечает начала новых блоков.

Ненулевое значение в этом двоичном векторе является частью ограничений, которые определяют значение блока.

Назовем вектор решения X.

Импликация осуществляется попарно.

# zero-order logic
start_block[x] -> X[x]
start_block[x] -> X[x+1]
start_block[x] -> X[x+2]

<=> 

# zero-order logic ( a->b <-> !a V b )
!start_block[x] V X[x]
!start_block[x] V X[x+1]
!start_block[x] V X[x+2]

<=>

# linear expression
(1 - start_block[x]) + X[x] >= 1
(1 - start_block[x]) + X[x+1] >= 1  
(1 - start_block[x]) + X[x+2] >= 1

Сделайте это для всего измерения переменной решения X (забота о границах).

Имейте в виду, что это только говорит: если в X есть 1, это часть блока размером> = 3. Это может быть блок из 4. Поскольку я точно не знаю вашу модель, это наиболее общий подход, который я могу предложить. Конечно, вы можете настроить это дальше для своего случая!

Обобщение этого для целочисленных переменных не должно быть слишком сложным, но может привести к появлению новых вспомогательных переменных.

person sascha    schedule 12.06.2017
comment
Спасибо за быстрый ответ! Не могли бы вы подробнее рассказать о втором блоке вашего кода? часть! start_block v X [x], делает ли start_block [x] равным 0, чтобы указать три последовательных единицы в X? - person BeWater; 12.06.2017
comment
Нет, он говорит: если start_block [x] == 1 - ›в X будет 1 в позиции x, x + 1, x + 2. Таким образом, это зависит от вашей остающейся модели, как это включить (общий поток: start-block подразумевает что-то в X; поэтому, вероятно, start_block - это переменная, которая будет использоваться в оставшейся модели). В кодовом блоке актуальна только последняя часть. Два приведенных выше блока просто показаны, чтобы показать, откуда это происходит. - person sascha; 12.06.2017
comment
Если вам нужно другое направление эффектов, вы всегда можете смоделировать его (например, от X до start_block). Но для этого частного случая блоков размером не менее 3 это направление очень практично. - person sascha; 12.06.2017
comment
Извините за повторяющиеся уточняющие вопросы, поскольку я новичок в этой области, я думаю, что мне действительно нужно повысить свои навыки в логической алгебре. Я думаю, что мне нужно другое направление эффекта (от x = x + 1 = x + 2 = 1 до принудительного start_block [x] = 1. Однако, если я буду рассматривать только другое направление эффекта, не потеряю ли я контроль, который 1s в X должен происходить в блоках по три? или я должен включить оба направления в ограничение? - person BeWater; 12.06.2017
comment
На этот вопрос нельзя ответить при полном знании модели. Вам остается только включить это и опубликовать ограничения на start_block. Не знаю, нужны ли вам другие направления. Вышеупомянутый подход требует, чтобы вы каким-то образом использовали start_block для введения ненулевых значений, а ограничения вызывали блочный эффект. Согласно текущим формулировкам, размещение дополнительных ограничений на start_block не будет иметь никакого эффекта в модели, так как это направление тогда неактивно. Наоборот, X - ›start_vector также потребует некоторых ограничений, действующих на start_vector, чтобы увидеть некоторые эффекты. - person sascha; 12.06.2017
comment
В более общем плане всем, кто плохо знаком с целочисленным программированием, следует прочитать такое руководство, как this один. Возможно, это не ответ на ваши вопросы, но он даст некоторую общую идею (особенно условные ограничения или-или). - person sascha; 12.06.2017
comment
И очень общее замечание по поводу другого направления: X - ›Y, где X - это ваши 0 и 1, трудно что-то сделать, так как для каждого X вы не знаете, является ли ваш X теперь началом блока или конец или что-то посередине (нужно будет проверить оба направления, влево и вправо). Я настоятельно рекомендую сначала смоделировать гораздо более простую модель (убрать сложность) и понаблюдать за тем, что происходит. - person sascha; 12.06.2017
comment
Большое спасибо за помощь и идеи, очень признательны! - person BeWater; 12.06.2017

arrow_upward
4
arrow_downward

Прогоны длиной ровно три можно смоделировать как:

y(t+1) >= y(t)-y(t-1)
y(t+2) >= y(t)-y(t-1)
1-y(t+3) >= y(t)-y(t-1)

где y (t) - двоичная переменная. Прогоны длиной не менее трех можно смоделировать, отбросив последнее ограничение:

y(t+1) >= y(t)-y(t-1)
y(t+2) >= y(t)-y(t-1)
person Erwin Kalvelagen    schedule 12.06.2017
comment
Спасибо! Однако если y (t) = 0, y (t-1) = 1, тогда третье ограничение будет читаться как y (t + 3) ‹= 0, не вызовет ли это нежелательную блокировку значения 0 для значений y? (поскольку y (t) = 0 и y (t + 3) = 0, это заставляет y (t + 1) и y (t + 2) быть 0, поэтому 10⇒10000 - person BeWater; 13.06.2017
comment
Боюсь, я не слежу за тобой. Если y(t)=0, y(t-1)=1, у нас есть 1-y(t+3) >= -1 или y(t+3) <= 2, что не является обязательным. - person Erwin Kalvelagen; 13.06.2017
comment
Вы абсолютно правы! Я допустил глупую ошибку в расчетах. Приношу свои извинения за путаницу. - person BeWater; 13.06.2017