CPLEX с использованием формата LP-файла: ограничения индикаторов с булевыми операторами

Question

Я совершенно не знаком с CPLEX и далеко не экспертом в MIP, но я пытаюсь решить проблему с этой технологией (CPLEX 12.4). Я решил создать MIP-модели в файле .lp и передать его CPLEx, чтобы у меня было много входов и тестирование различных решателей и т. Д. Но я считаю, что некоторые ограничения индикаторов немного проблематичны.

Я хочу что-то вроде:

c1: a AND NOT(b)-> i1 - 100 v1 = 0 
c2: b AND NOT(a)-> i1 - 120 v1 = 0 
c3: a AND b -> i1 - 80 v1 =0 

Но нет такой вещи, ANS AND или NOT в формате LP (я даже не уверен, если я мог бы сделать это на интерфейс CPX, но я стараюсь чтобы избежать этого).

Единственный способ решения проблемы я нашел делает:

ca: a_not_b = 1 <-> a - b = 1 
cb: b_not_a = 1 <-> a - b = -1 
cab: a_and_b = 1 <-> a + b = 2 
c1: a_not_b-> i1 - 100 v1 = 0 
c2: b_not_a-> i1 - 120 v1 = 0 
c3: a_and_b = 1-> i1 - 80 v1 =0 

я бы хорошо с наличием этого, потому что я собираюсь порождающие эту пластинку с другой программой, но это замедлить CPLEX? Есть ли лучший способ сделать это?

Thanks

Answer 1

Вы в значительной степени верны. Подход LP и MILP напрямую не учитывает эти виды логических ограничений. Скорее вам обычно нужно создавать вспомогательные переменные в вашей модели, которые можно использовать для захвата этих условий. Во многих случаях это будут логические или 0/1 целые переменные. Большая часть искусства & ремесло написания моделей MILP находит хорошие способы перезаписать эти условия на довольно ограничительном «языке» моделей LP и MILP. Это может привести к некоторой довольно интересной умственной гимнастике! Обратите внимание, что это ограничение подхода MILP, а не только CPLEX. Моделирование языков, поддерживающих эти логические отношения, в основном просто обеспечивает синтаксический сахар вокруг этих же методов моделирования со вспомогательными двоичными/целочисленными переменными.

Решения MILP могут обрабатывать очень большие проблемы с миллионами переменных и ограничений; но это связано с лежащими в основе математическими структурами и предположениями. Такие методы, как программирование ограничения, допускают такое прямое моделирование логических и других отношений, но обычно ограничиваются гораздо меньшими экземплярами проблем.

Что касается замедления CPLEX (или любого другого решателя), ответ, вероятно, да, это будет. Однако не может быть альтернативы, если вы используете решатель MILP - лучше решить правильную проблему, чем неправильную.