SCIP: как разрешить LP после перехвата события «невозможность узла», - PullRequest
Новая
       24

SCIP: как разрешить LP после перехвата события «невозможность узла»,

1 голос
/ 15 апреля 2019

У меня есть алгоритм генерации рабочего столбца в SCIP.Из-за определенных ограничений, которые я включаю при создании столбцов, может случиться так, что последний ценовой раунд определит, что корневой узел недопустим (конечно, по цене Фаркаша).

В этом случае я бы хотел 1) ослабить эти конкретные ограничения, 2) разрешить ЛП и 3) снова начать столбцы ценообразования.

Итак, я создал свой собственный класс EventHandler, перехватывая событие невозможности узла: 

SCIP_DECL_EVENTINITSOL(EventHandler::scip_initsol)
{
    SCIP_CALL( SCIPcatchEvent(scip_, SCIP_EVENTTYPE_NODEINFEASIBLE, eventhdlr, NULL, NULL));
    return SCIP_OKAY;
}

И, соответственно, виртуальный метод scip_exec: 

SCIP_DECL_EVENTEXEC(EventHandler::scip_exec)
{
  double cur_rhs = SCIPgetRhsLinear(scip_, *d_varConsInfo).c_primal_obj_cut);
  SCIPchgRhsLinear (scip_, (*d_varConsInfo).c_primal_obj_cut, cur_rhs + DELTA);

  return SCIP_OKAY;     
}

Где(*d_varConsInfo).c_primal_obj_cut - это конкретное ограничение, которое нужно изменить, DELTA - глобальный параметр, а cur_rhs - текущая правая часть конкретного ограничения.Эта функция вызывается после подтверждения невозможности узла, однако я не знаю, как «сказать» Скипу, что LP должен быть разрешен, и, возможно, должны быть добавлены новые столбцы.Может ли кто-нибудь помочь мне с этим?

Ответы [ 2 ]

4 голосов
/ 16 апреля 2019

Когда обработчик события перехватывает событие NODEINFEASIBLE, уже слишком поздно что-то менять в отношении невозможности решения проблемы, обработка узла уже завершена. Кроме того, вам не разрешено изменять rhs ограничения во время процесса решения (поскольку это означает, что сокращения, сделанные ранее, потенциально могут быть недействительными).

Я бы предложил следующее: если ваша цена Farkas не может определить новые столбцы для повторного выполнения LP, то узел будет объявлен недопустимым в следующих случаях. Следовательно, по окончании ценообразования Farkas (если вы находитесь в корневом узле) вы можете просто оценить вспомогательную переменную, которую вы добавляете к ограничению, которое вы хотите ослабить, с границами, соответствующими вашему DELTA. Обратите внимание, что вы должны пометить ограничение, чтобы его можно было изменять при его создании. Затем, поскольку переменная была добавлена, SCIP запустит еще один раунд цен.

1 голос
/ 15 апреля 2019

возможно, вам стоит взглянуть на метод SCIP PRICERFARKAS (https://scip.zib.de/doc/html/PRICER.php#PRICER_FUNDAMENTALCALLBACKS).

Если текущее ослабление LP невозможно, задача оценщика - сгенерировать дополнительные переменные, которые потенциально могутсделайте LP снова выполнимым. В стандартной ветке и цене это переменные с положительными значениями Фаркаша, и метод PRICERFARKAS должен идентифицировать эти переменные.

...