Итеративное использование bintprog на MATLAB

Question

У нас есть проблема формулировки, как показано в this link.

Учитывая, что первый вызов bintprog дает решение x, что после того, как некоторые после обработки не адекватно решает проблемы, можно вспомнить bintprog и исключить предварительное решение x?

Answer 1

Вам нужен разрез для ногуда.

Предположим, вы нашли решение \ hat {x}, которое вы затем решили, является недопустимым (через некоторую пост-обработку). Пусть x и \ hat {x} индексируются i.

Вы можете добавить ограничение следующего вида:

\sum_{i : \hat{x}_i = 0} x_i + \sum_{i : \hat{x} = 1} (1-x_i) \geq 1 

Это ограничение является примером не-хорошего разреза: решение должно отличаться от \ шляпы {х}, по меньшей мере, с одним индексом I, в противном случае это невозможно. Если ваши переменные не являются бинарными, не-товары могут быть немного сложнее.

Вы можете добавить no-good к вашему решению, добавив ограничение в виде строки к вашей матрице ограничений и переуступая с помощью функции bintprog(). Я оставлю это вам, чтобы вы переписали его в нотации MATLAB.

Вы не сказали, что делает ваша пост-обработка, но было бы даже лучше, если бы пост-обработка могла вывести из вашего решения \ hat {x}, что другие решения также недопустимы, и вы можете добавить больше, чем одна строка на итерацию. Это форма декомпозиции Benders на основе логики, и вывод других неосуществимых решений называется решением двойного вывода (в отличие от стандартной декомпозиции Benders, где вы решаете двойное линейное программирование). More on logic based Benders decomposition от человека, который придумал термин, Джон Хукер из КМУ.

Извините за форматирование. Мне нужно идти, но я выясню способ отображения уравнений более красиво позже.