2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Switch в MIP
Сообщение11.01.2023, 18:12 
Аватара пользователя
Пытаясь свести одну задачу к целочисленному линейному программированию, столкнулся с такой проблемой: у меня есть целочисленная переменная, принимающая 3 значения: $b, integer, \geqslant0, \leqslant2$. А нужна булевская, $x, binary$, которая бы принимала значение $1$, когда $b=0$, и $0$ в остальных случаях. Методом тыка довольно легко нашел, что проблема решается добавлением неравенств $1\leqslant b+2x\leqslant2$.
Однако применение того же метода к случаю $y, binary$, которая бы принимала значение $1$, когда $b=1$, как-то не пошло, получалось, что это (написать такое неравенство) невозможно. Нарисовав картинку на плоскости $(b,y)$, понял, почему: я пытался "вырезать" выпуклый многоугольник, в котором целых точек было бы $3$, $(0,0)$, $(1,1)$ и $(2,0)$. Однако на отрезке с концами $(0,0)$ и $(2,0)$ лежит "лишняя" точка $(1,0)$, от которой, таким образом, нельзя избавиться.
Пришлось пойти длинным путем: ввести признак равенства двум ($z, binary$, которая принимает значение $1$, когда $b=2$), тогда проблемы лишней точки нет, $z$ задается неравенством $-1\leqslant-b+2z\leqslant0$, а уж признак равенства единице $y$ задаем через $x$ и $z$: $y=(¬x)\&(¬z)$, по MIP-вски, соответственно, $0\leqslant(1-x)+(1-z)-2y\leqslant1$.
Вопрос, собс-но, нет ли какой-то общей технологии решения такого сорта задач? скажем, для переменной с 4 значениями все еще усложняется, не хочется изобретать велосипеды.
Может быть, есть какая-то книжка (типа "Математическая логика и целочисленное программирование")?

 
 
 
 Re: Switch в MIP
Сообщение11.01.2023, 20:55 
А что такое MIP? Там нельзя просто написать типа:
Код:
function f1(b) {
    int x = 1; if (b!=0) x = 0;
    return x;
}
function f2(b) {
    int y = 1; if (b!=1) y = 0;
    return y;
}
И т.д...

Или вместе
Код:
function f1(b,par) {
    int x = 1; if (b!=par) x = 0;
    return x;
}

 
 
 
 Re: Switch в MIP
Сообщение11.01.2023, 21:00 
Аватара пользователя
gevaraweb в сообщении #1576806 писал(а):
А что такое MIP?
Mixed Integer Programming - задача оптимизации с ограничениями, в которой на часть переменных наложено ограничение целочисленности (а на часть - нет, иначе это просто Integer Programming). Как правило ограничения и целевая функция считаются линейными.

 
 
 
 Re: Switch в MIP
Сообщение11.01.2023, 21:36 
Аватара пользователя
Да, все верно.
В линейном программировании, включая целочисленный вариант, можно только писать линейные уравнения и неравенства, никакие другие манипуляции не допускаются.

 
 
 
 Re: Switch в MIP
Сообщение18.09.2023, 23:22 
Аватара пользователя
Введите 3 бинарные переменные, удовлеворяющие условиям:
$$\begin{cases}
x_0 + x_1 + x_2 = 1\\
0x_0 + 1x_1 + 2x_2 = b
\end{cases}
$$
Тогда $x_i=1$ тогда и только тогда, когда $b=i$.

 
 
 
 Re: Switch в MIP
Сообщение19.09.2023, 14:07 
Аватара пользователя
maxal
Да, точно. И для любого числа вариантов работает.
Очень изящно. Спасибо!

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group