MIP: добавление переменной для обозначения равенства

Question

Я пытаюсь построить модель MIP в API Python OR Tools.У меня есть два выражения x и y, и я хочу создать переменную b, равную 1, когда x == y и 0 в противном случае.Пока я пытался сделать это, добавив ограничение -M(1 - b) <= x - y <= M(1 - b) для некоторого большого значения M, что заставляет b быть 0, если x != y.Я застреваю, добавляя ограничение, которое заставляет b быть 1, если x == y.Я думаю, что я хотел бы что-то вроде x - y >= 1 - b или y - x >= 1 - b, но я не знаю, как логически объединить ограничения, как это.Любые предложения о том, как это сделать?Или для совершенно другого подхода?

Answer 1

Обратите внимание, что в зависимости от характера модели решатель CP-SAT может оказаться конкурентоспособным. И это обеспечивает реификацию и половину реификации изначально.

Пожалуйста, посмотрите на

• [ Конкретный ответ ] https://github.com/google/or-tools/blob/master/ortools/sat/doc/channeling.md
• [ Введение ] https://developers.google.com/optimization/cp/cp_solver#cp-sat_example
• [ Рецепты CP-SAT ] https://github.com/google/or-tools/blob/master/ortools/sat/doc/index.md

Answer 2

Я думаю, что следующие выражения подойдут вам:

b <= x - y + 1
b <= y - x + 1
b >= 1-x + 1-y - 1
b >= y + x - 1