Не могу понять причину невозможности решения проблемы - PullRequest
Новая
       83

Не могу понять причину невозможности решения проблемы

0 голосов
/ 25 июня 2019

У меня есть простая задача линейного программирования, написанная в формате OSiL, которая вырезана из сложной нелинейной задачи, которую SCIP признал недостижимой.Эта простая проблема - минимальные строки, чтобы воспроизвести эту неосуществимую проблему, однако она смущает меня.Ниже приводится содержание OSiL: 

    <instanceData>
        <variables numberOfVariables="1">
            <var name="F"/>
        </variables>
        <objectives numberOfObjectives="1">
            <obj maxOrMin="min" numberOfObjCoef="1" >
                <coef idx="0">1</coef>
            </obj>
        </objectives>
        <constraints  numberOfConstraints="1">
            <con lb="10"/>
        </constraints>
    </instanceData>

Разве OSIL не говорит: 

Minimize:    F
Subject to:  F >= 0

?Почему эта проблема должна быть неосуществимой?На мой взгляд, <con lb="10"/> бесполезен, потому что никто не ссылается на него.Но на самом деле это ограничение действительно влияет на исходную проблему таким образом, что я не заметил, потому что проблема может быть решена, если нижняя граница изменяется на 0 или меньше, или изменить ее на верхнюю границу.Может кто-то объяснить это мне?Я новичок в числовой оптимизации и формате OSiL, поэтому заранее спасибо за ваше время.

1 Ответ

3 голосов
/ 25 июня 2019

В вашем ограничении нет F, вы только добавили переменную к цели.Сформулированное ограничение: 10 <= 0, что недопустимо.

Если вы посмотрите на проблему в SCIP, это может стать более очевидным: 

original problem has 1 variables (0 bin, 0 int, 0 impl, 1 cont) and 1 constraints
SCIP> disp prob

STATISTICS
  Problem name     : a.osil
  Variables        : 1 (0 binary, 0 integer, 0 implicit integer, 1 continuous)
  Constraints      : 0 initial, 1 maximal
OBJECTIVE
  Sense            : minimize
VARIABLES
  [continuous] <F>: obj=1, original bounds=[0,+inf]
CONSTRAINTS
  [linear] <cons0>: 0 >= 10;
END
...