lp_solve игнорирует тривиальные ограничения

Question

Я сделал действительно простую линейную задачу для lp_solve.

$ cat test.txt 
max: 100X ;

X <= 0 ;

bin X ;

Правильный ответ должен состоять в том, что X должно быть 0, поскольку это двоичная переменная и не может быть 1 из-за ограничения.Однако результат:

$ lp_solve test.txt 

Value of objective function: 100.00000000

Actual values of the variables:
X                               1

Чем объясняется такое поведение?Я делаю что-то не так?Это также происходит, когда на более крупные проблемы присутствуют одинаковые ограничения.

Answer 1

Да, когда lp_solve выполняет свою предварительную обработку, это полностью устраняет ваши ограничения.Затем тот факт, что X является двоичным, и функция Objective показана равной 100. (Неверно)

Вы можете увидеть, что это происходит, запустив флаг -stats:

./lp_solve -stat test.lp
Constraints: 0
Variables  : 1
Integers   : 1
Semi-cont  : 0
SOS        : 0
Non-zeros  : 0  density=nan%

Это неожиданное поведение может быть вызвано нулевыми ограничениями и наноплотностью.

Для этого есть несколько способов.

1. Если вы устраните *Ограничение 1015 * в целом, оно решит его правильно и даст вам объективное значение 0.

2. Еще одно «хакоподобное» исправление - добавить фиктивную переменную в ваше тривиальное ограничение.Теперь все ограничение записывается lp_solve.

Например, попробуйте изменить ваш test.lp следующим образом:

max: 100X ;

X  + x_dummy <= 0 ; 

bin X ;

Что теперь дает правильное значение:

Constraints: 1
Variables  : 2
Integers   : 1
Semi-cont  : 0
SOS        : 0
Non-zeros  : 2  density=100.000000%

Надеюсь, это поможет.