Целое число и логическое моделирование

Целочисленные ограничения позволяют вам создавать модели с этими важными функциями:

  • Последствия, такой как, "Если Условие A содержит затем Условие B, содержат".

  • Операционные издержки или затраты на настройку, такие как "Стоимость элемента нуль, если я покупаю нуль элемента, но стоимость является операционными издержками $A плюс $B на элемент, если я покупаю больше, чем нуль". Смотрите Пример: Фиксированные затраты.

  • Логические ограничения, такие как "Дверь воздушной пробки A и дверь B не могут оба быть открыты одновременно".

Много проблем моделирования эквивалентны логическим моделям тот индикатор использования переменные. Эта тема описывает, как использовать переменные индикатора и логические модели. Эти модели основаны на формулировке Big-M, где переменная x и постоянный M приняты, чтобы удовлетворить неравенствам MxM.

Вспомните, что ограничения в оптимизации имеют подразумеваемое "и". Ограничениям c1, c2, и c3 удовлетворяют, когда всем трем ограничениям удовлетворяют: c1 и c2 и c3.

Большая-M формулировка

Предположим, что у вас есть непрерывная переменная x, который ограничен выше постоянным M:

xM.

Вы хотите сопоставить бинарную переменную z индикатора к x так, чтобы z = 1 каждый раз, когда x> 0. Для этого используйте Большую-M формулировку включением ограничения:

xM z.

Это ограничение гарантирует что каждый раз, когда x> 0, затем z = 1 обязательно. Большая-M формулировка имеет больше приложений, как обсуждено в Экспрессе Логические Ограничения Используя Действительные Функции и Бинарные Переменные Индикатора.

Основная проблема: потоки резервуара

Предположим, что вы хотите смоделировать резервуар за целочисленные времена. В каждый положительный целочисленный раз t в фиксированной области значений резервуар может принять воду количества xin (t) или может разрядить количество воды xout (t) в непрерывных суммах до максимального M или в или. Ваша модель должна осуществить это если xin (t)> 0 затем xout (t) = 0, и если xout (t)> 0 затем xin (t) = 0. Как вы моделируете это ограничение? Один путь состоит в том, чтобы ограничить

xin (t) * xout (t) = 0.

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

Лучший способ реализовать ограничение состоит в том, чтобы использовать двоичную переменную индикатора zin (t), который равняется 1 каждый раз, когда xin (t)> 0, и подобная бинарная переменная zout (t), который равняется 1 каждый раз, когда xout (t)> 0. Предположение, что у вас есть такие переменные, добавляет ограничение

zin (t) + zout (t) ≤ 1,

который гарантирует, что xin (t) и xout (t) не оба положительны.

Чтобы гарантировать что zin (t) = 1 каждый раз, когда xin (t)> 0, используйте Большую-M формулировку. Примите, что xin (t) ограничен выше M, положительным числом, для всего t. Включайте ограничение

xin (t) ≤ M *zin (t).

Чтобы гарантировать что zin (t) = 0 каждый раз, когда xin (t) = 0, включайте zin (t) в целевую функцию. Таким образом минимизация целевой функции заставляет zin (t) быть нулем, когда это возможно.

Точно так же, чтобы соединить zout (t) и xout (t), включите ограничение

xout (t) <= M *zout (t).

Таким образом, чтобы осуществить ограничение, что xin (t) и xout (t) не может и быть положительным, вы создаете две бинарных переменные zin (t) и zout (t) в течение каждого раза t, и включаете эти три ограничения:

xin (t) <= M *zin (t) % Гарантирует что zin (t) = 1 каждый раз, когда xin (t)> 0.

xout (t) <= M *zout (t) % Гарантирует что zout (t) = 1 каждый раз, когда xout (t)> 0.

zin (t) + zout (t) <= 1% Гарантирует, что zin (t) и zout (t) не оба положительны.

MATLAB® команды в подходе, основанном на проблеме следующие:

T = 50; % Number of times
M = 40; % Maximum size of x variables
xin = optimvar('xin',T,'LowerBound',0,'UpperBound',M);
xout = optimvar('xout',T,'LowerBound',0,'UpperBound',M);
zin = optimvar('zin',T,'Type','integer','LowerBound',0,'UpperBound',1);
zout = optimvar('zout',T,'Type','integer','LowerBound',0,'UpperBound',1);
prob = optimproblem;

xinzin = xin <= M*zin;
xoutzout = xout <= M*zout;
zinzout = zin + zout <= 1;
prob.Constraints.xinzin = xinzin;
prob.Constraints.xoutzout = xoutzout;
prob.Constraints.zinzout = zinzout;

prob.Objective = sum(zin + zout);

Отметьте следующее:

  • Все ограничения являются векторами из ограничений длины T, как переменные оптимизации и переменные индикатора.

  • Все ограничения заданы с отдельными операторами, не в цикле, который дает лучшую эффективность.

Опишите логические ограничения Используя бинарные переменные

Этот раздел содержит логические операторы и соответствующие команды MATLAB с бинарными переменными. Операторы принимают что переменные zW, и f бинарные переменные оптимизации, означая, что каждый имеет, вводят "integer", нижняя граница 0, и верхняя граница 1.

ОписаниеЛогический операторКоманды MATLAB
z и w имейте противоположные значенияz = not w
z = 1 - w;
По крайней мере один из z или w верноz or w
z + w >= 1;
Самое большее один из z или w верно(not z) or (not w)
z + w <= 1;
f верно точно когда z верно или w верноf = z or w
f >= z;
f >= w;
f <= z + w;
f верно точно когда оба z и w верныf = z and w
f <= z;
f <= w;
f >= z + w - 1;
f верно точно когда один из z или w верноf = z xor w
f >= z - w;
f >= w - z;
f <= z + w;
f <= 2 - (z + w);

Опишите логические ограничения Используя действительные функции и бинарные переменные индикатора

Этот раздел соединяет действительный функциональный g (x) и бинарная переменная z. Как правило, вы вводите z в проблему как переменная индикатора, чтобы смоделировать некоторый аспект проблемы, такой как индикатор когда g (x)> 0. Все эти ограничения основаны на Большой-M формулировке.

Примите, что постоянный M и функциональный g (x) удовлетворяют границам

–Mg (x) ≤ M.

УсловиеОграничительный код
Если z = 1 затем g (x) ≤ 0
g(x) <= M*(1 - z);
Если z = 1 затем g (x) ≥ 0
g(x) >= -M*(1 - z);
Если z = 1 затем g (x) = 0
g(x) <= M*(1 - z);
g(x) >= -M*(1 - z);
Если g (x) ≤ 0 затем z = 1
g(x) >= -M*z;
Если g (x) ≥ 0 затем z = 1
g(x) <= M*z;

Если g (x)> 0 затем z = 1

Если g (x) <0 затем z = 0

Создайте новую бинарную переменную z1 указать на g (x) <0.

g(x) <= M*z;

g(x) >= -M*z1;

z + z1 == 1;

Эта формулировка неопределенна когда g (x) = 0.

Объедините логические ограничения, чтобы создать новые формулы

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

УсловиеОграничительный код

Для скалярных функций g (x) и h (x), удовлетворяющий связанному ограничению M, реализуйте условие:

Если g (x) ≥ 0 затем h (x) ≥ 0

Введите бинарную переменную z индикатора указание, что g (x) ≥ 0. Затем введите ограничение что если z = 1 затем h (x) ≥ 0.

g(x) <= M*z;
h(x) >= -M*(1 - z);

g (x) = z *x, где z является бинарной переменной

Представляйте это условие как два ограничения:

Если z = 1 затем g (x) - x = 0

Если z = 0 затем g (x) = 0

g(x) <= x + M*(1-z);
g(x) >= x - M*(1-z);
g(x) <= M*z;
g(x) >= -M*z;

Пример: фиксированные затраты

Предположим, что стоимость создания количества x элемента

cost={a+bxесли x>00если x=0.

Можно смоделировать эту нелинейную стоимость с помощью линейной переменной x и бинарной переменной z индикатора. Создайте ограничения так, чтобы z = 1 каждый раз, когда x> 0, и включают z в целевую функцию так, чтобы z = 0 каждый раз, когда x = 0. Примите, что проблема включает связанный M так, чтобы xM.

x <= M*z; % Constraint, makes z = 1 when x > 0
cost = a*z + b*x;

Если вы минимизируете стоимость, когда x = 0 затем z = 0 также.

Пример: ограничения OR

Иногда вы хотите смоделировать ограничение, которое осуществляется, когда условие A содержит, или условие B содержит, или условие C содержит. Для этого создайте бинарные переменные zA индикатора, zB, и zC это указывает, когда соответствующие условия A, B, и C содержат и включают дополнительное ограничение

zA + zB + zC >= 1;

Как другой пример, смоделируйте ограничение абсолютного значения |x | = 5, что означает x = 5 или x = –5. Создайте две переменные z1 индикатора и z2 это указывает когда x = 5 и x = –5, соответственно. Затем включайте ограничение

z1 + z2 >= 1;

Один способ установить z 1 = 1, когда x = 5 должен ввести три новых переменные z11 индикатора, z12, и z13 для этих условий:

z11 = 1, когда x <5 и z1 = 0,

z12 = 1, когда x = 5 и z1 = 1,

z13 = 1, когда x > 5 и z1 = 0.

Затем введите ограничение

z11 + z12 + z13 = 1;

Задавать z11, используйте эти три ограничения.

-(1 - z11) <= z1;
z1 <= (1 - z11);
x - 5 <= M(1 - z11);

Задавать z12, используйте эти четыре ограничения.

-(1 - z12) <= z1 - 1;
z1 - 1 <= (1 - z12);
-M(1 - z12) <= x - 5;
x - 5 <= M(1 - z12);

Задавать z13, используйте эти три ограничения.

-(1 - z13) <= z1;
z1 <= (1 - z13);
x - 5 >= -M(1 - z13);

Чтобы закончить модель, задайте подобные ограничения для z21, z22, и z23 это соответствует z2 и условие x = –5.

Дополнительные материалы для чтения

Классической книгой по моделированию для оптимизации является Уильямс [1]. Для обсуждения того, почему Большая-M формулировка бинарных переменных индикатора математически завершена и не расширяема, смотрите Хукера [2]. Для дальнейших примеров использования бинарных переменных индикатора в математическом моделировании смотрите Брауна и Dell [3] и Стивенса и Пэлоксея [4].

Ссылки

[1] Уильямс, Х. Пол. Построение моделей в математическом программировании, 5-м выпуске. Вайли, 2013.

[2] Проститутка, Джон. Принципиальный Подход к Моделированию MILP. Университет Карнеги-Меллон, 2008. Доступный в https://coral.ise.lehigh.edu/mip-2008/talks/hooker.pdf.

[3] Браун, Джеральд Г. и Роберт Ф. Делл. Формулировка Целочисленных Линейных Программ: Галерея Жуликов. Транзакции INFORMS на Образовании 7 (2), 2007, стр 153–159. Доступный в https://doi.org/10.1287/ited.7.2.153.

[4] Стивенс, Скотт П. и Сьюзен В. Пэлоксей. Обучение Использования Бинарных Переменных в Целочисленных Линейных Программах: Формулировка Логических Условий. Транзакции INFORMS на Образовании 18 (1), 2017, стр 28–36. Доступный в https://doi.org/10.1287/ited.2017.0177.

Смотрите также

| (Global Optimization Toolbox) | (Global Optimization Toolbox) | (Global Optimization Toolbox)

Похожие темы