В последнее время я пытался немного узнать о CPLEX и надеялся, что кто-нибудь может помочь мне понять сложность при решении целочисленных и двоичных ограничений.
Например, скажем, мы пытаемся выделитьПирог около 10 человек для максимальной полезности, где у каждого человека есть полезность, которая линейна с количеством пирога, который они получают.Однако мы хотим ввести ограничение, согласно которому по крайней мере 3 человека должны получить немного пирога.
В чем разница между представлением об этом как одно целочисленное ограничение (number_of_people_with_pie> = 3) против 10 двоичных переменных(person_1_has_pie + person_2_has_pie + ... person_10_has_pie> = 3)?Я полагаю, что первое является самым простым, но задаюсь вопросом, есть ли какие-либо преимущества в формировании проблемы с точки зрения бинарных переменных?
В дополнение к этому, любое рекомендованное чтение для лучшего понимания MIP и CPLEX будет высоко оценено, особеннов лучшем понимании, где проблема становится NP или в каких ситуациях симплекс пытается найти глобальные минимумы.
Спасибо!