24#include "absl/status/status.h"
25#include "absl/strings/str_format.h"
26#include "absl/types/optional.h"
36#include "ortools/linear_solver/linear_solver.pb.h"
41#include "scip/cons_indicator.h"
43#include "scip/scip_copy.h"
44#include "scip/scip_param.h"
45#include "scip/scip_prob.h"
46#include "scip/scipdefplugins.h"
49 "When true, emphasize search towards feasibility. This may or "
50 "may not result in speedups in some problems.");
58class ScipConstraintHandlerForMPCallback;
68 const MPModelRequest& request)
override;
69 void Reset()
override;
79 double new_value,
double old_value)
override;
90 LOG(DFATAL) <<
"Basis status only available for continuous problems";
94 LOG(DFATAL) <<
"Basis status only available for continuous problems";
99 bool IsLP()
const override {
return false; }
100 bool IsMIP()
const override {
return true; }
107 return absl::StrFormat(
"SCIP %d.%d.%d [LP solver: %s]", SCIPmajorVersion(),
108 SCIPminorVersion(), SCIPtechVersion(),
109 SCIPlpiGetSolverName());
113 const absl::MutexLock lock(&hold_interruptions_mutex_);
114 if (scip_ ==
nullptr) {
115 LOG_IF(DFATAL, status_.ok()) <<
"scip_ is null is unexpected here, since "
116 "status_ did not report any error";
119 return SCIPinterruptSolve(scip_) == SCIP_OKAY;
153 void SetRelativeMipGap(
double value)
override;
154 void SetPrimalTolerance(
double value)
override;
155 void SetDualTolerance(
double value)
override;
156 void SetPresolveMode(
int presolve)
override;
157 void SetScalingMode(
int scaling)
override;
158 void SetLpAlgorithm(
int lp_algorithm)
override;
168 absl::Status SetNumThreads(
int num_threads)
override;
170 bool SetSolverSpecificParametersAsString(
173 void SetUnsupportedIntegerParam(
180 void SetSolution(SCIP_SOL* solution);
182 absl::Status CreateSCIP();
186 SCIP* DeleteSCIP(
bool return_scip =
false);
194 absl::Status status_;
197 std::vector<SCIP_VAR*> scip_variables_;
198 std::vector<SCIP_CONS*> scip_constraints_;
199 int current_solution_index_ = 0;
201 std::unique_ptr<ScipConstraintHandlerForMPCallback> scip_constraint_handler_;
203 EmptyStruct constraint_data_for_handler_;
204 bool branching_priority_reset_ =
false;
205 bool callback_reset_ =
false;
210 mutable absl::Mutex hold_interruptions_mutex_;
227 std::vector<CallbackRangeConstraint> SeparateSolution(
229 const bool at_integer_solution);
234#define RETURN_IF_ALREADY_IN_ERROR_STATE \
236 if (!status_.ok()) { \
237 VLOG_EVERY_N(1, 10) << "Early abort: SCIP is in error state."; \
242#define RETURN_AND_STORE_IF_SCIP_ERROR(x) \
244 status_ = SCIP_TO_STATUS(x); \
245 if (!status_.ok()) return; \
250 status_ = CreateSCIP();
257 const absl::MutexLock lock(&hold_interruptions_mutex_);
260 SCIP* old_scip = DeleteSCIP(
true);
262 [&old_scip]() {
CHECK_EQ(SCIPfree(&old_scip), SCIP_OKAY); });
264 scip_constraint_handler_.reset();
268 status_ = CreateSCIP();
282absl::Status SCIPInterface::CreateSCIP() {
287 if (absl::GetFlag(FLAGS_scip_feasibility_emphasis)) {
298 SCIPsetIntParam(scip_,
"timing/clocktype", SCIP_CLOCKTYPE_WALL));
300 nullptr,
nullptr,
nullptr,
nullptr,
303 scip_,
maximize_ ? SCIP_OBJSENSE_MAXIMIZE : SCIP_OBJSENSE_MINIMIZE));
304 return absl::OkStatus();
307SCIP* SCIPInterface::DeleteSCIP(
bool return_scip) {
312 CHECK(scip_ !=
nullptr);
313 for (
int i = 0; i < scip_variables_.size(); ++i) {
314 CHECK_EQ(SCIPreleaseVar(scip_, &scip_variables_[i]), SCIP_OKAY);
316 scip_variables_.clear();
317 for (
int j = 0; j < scip_constraints_.size(); ++j) {
318 CHECK_EQ(SCIPreleaseCons(scip_, &scip_constraints_[j]), SCIP_OKAY);
320 scip_constraints_.clear();
322 SCIP* old_scip = scip_;
325 CHECK_EQ(SCIPfree(&old_scip), SCIP_OKAY);
336 scip_, maximize ? SCIP_OBJSENSE_MAXIMIZE : SCIP_OBJSENSE_MINIMIZE));
347 SCIPchgVarLb(scip_, scip_variables_[var_index], lb));
349 SCIPchgVarUb(scip_, scip_variables_[var_index], ub));
361#if (SCIP_VERSION >= 210)
362 SCIP_Bool infeasible =
false;
364 scip_, scip_variables_[var_index],
365 integer ? SCIP_VARTYPE_INTEGER : SCIP_VARTYPE_CONTINUOUS, &infeasible));
368 scip_, scip_variables_[var_index],
369 integer ? SCIP_VARTYPE_INTEGER : SCIP_VARTYPE_CONTINUOUS));
384 SCIPchgLhsLinear(scip_, scip_constraints_[
index], lb));
386 SCIPchgRhsLinear(scip_, scip_constraints_[
index], ub));
407 scip_, scip_constraints_[constraint->
index()],
408 scip_variables_[variable->
index()], new_value - old_value));
420 const int constraint_index = constraint->
index();
423 for (
const auto& entry : constraint->coefficients_) {
424 const int var_index = entry.first->index();
425 const double old_coef_value = entry.second;
430 SCIPaddCoefLinear(scip_, scip_constraints_[constraint_index],
431 scip_variables_[var_index], -old_coef_value));
454 for (
const auto& entry :
solver_->objective_->coefficients_) {
455 const int var_index = entry.first->index();
461 SCIPchgVarObj(scip_, scip_variables_[var_index], 0.0));
479 branching_priority_reset_ =
true;
496 int total_num_vars =
solver_->variables_.size();
504 SCIP_VAR* scip_var =
nullptr;
506 double tmp_obj_coef = 0.0;
508 scip_, &scip_var,
var->name().c_str(),
var->lb(),
var->ub(),
510 var->integer() ? SCIP_VARTYPE_INTEGER : SCIP_VARTYPE_CONTINUOUS,
true,
511 false,
nullptr,
nullptr,
nullptr,
nullptr,
nullptr));
513 scip_variables_.push_back(scip_var);
514 const int branching_priority =
var->branching_priority();
515 if (branching_priority != 0) {
518 scip_, scip_variables_[
index], branching_priority));
524 for (
const auto& entry :
ct->coefficients_) {
525 const int var_index = entry.first->index();
531 SCIPaddCoefLinear(scip_, scip_constraints_[i],
532 scip_variables_[var_index], entry.second));
541 int total_num_rows =
solver_->constraints_.size();
545 int max_row_length = 0;
550 if (
ct->coefficients_.size() > max_row_length) {
551 max_row_length =
ct->coefficients_.size();
554 std::unique_ptr<SCIP_VAR*[]> vars(
new SCIP_VAR*[max_row_length]);
555 std::unique_ptr<double[]> coeffs(
new double[max_row_length]);
560 const int size =
ct->coefficients_.size();
562 for (
const auto& entry :
ct->coefficients_) {
563 const int var_index = entry.first->index();
565 vars[j] = scip_variables_[var_index];
566 coeffs[j] = entry.second;
569 SCIP_CONS* scip_constraint =
nullptr;
570 const bool is_lazy =
ct->is_lazy();
571 if (
ct->indicator_variable() !=
nullptr) {
572 const int ind_index =
ct->indicator_variable()->index();
574 SCIP_VAR* ind_var = scip_variables_[ind_index];
575 if (
ct->indicator_value() == 0) {
577 SCIPgetNegatedVar(scip_, scip_variables_[ind_index], &ind_var));
580 if (
ct->ub() < std::numeric_limits<double>::infinity()) {
582 scip_, &scip_constraint,
ct->name().c_str(), ind_var, size,
583 vars.get(), coeffs.get(),
ct->ub(),
594 scip_constraints_.push_back(scip_constraint);
596 if (
ct->lb() > -std::numeric_limits<double>::infinity()) {
597 for (
int i = 0; i < size; ++i) {
601 scip_, &scip_constraint,
ct->name().c_str(), ind_var, size,
602 vars.get(), coeffs.get(), -
ct->lb(),
613 scip_constraints_.push_back(scip_constraint);
620 scip_, &scip_constraint,
ct->name().c_str(), size, vars.get(),
621 coeffs.get(),
ct->lb(),
ct->ub(),
633 scip_constraints_.push_back(scip_constraint);
644 for (
const auto& entry :
solver_->objective_->coefficients_) {
645 const int var_index = entry.first->index();
646 const double obj_coef = entry.second;
648 SCIPchgVarObj(scip_, scip_variables_[var_index], obj_coef));
656#define RETURN_ABNORMAL_IF_BAD_STATUS \
658 if (!status_.ok()) { \
659 LOG_IF(INFO, solver_->OutputIsEnabled()) \
660 << "Invalid SCIP status: " << status_; \
661 return result_status_ = MPSolver::ABNORMAL; \
665#define RETURN_ABNORMAL_IF_SCIP_ERROR(x) \
667 RETURN_ABNORMAL_IF_BAD_STATUS; \
668 status_ = SCIP_TO_STATUS(x); \
669 RETURN_ABNORMAL_IF_BAD_STATUS; \
686 branching_priority_reset_ || callback_reset_) {
688 branching_priority_reset_ =
false;
689 callback_reset_ =
false;
693 SCIPsetMessagehdlrQuiet(scip_,
quiet_);
696 if (
solver_->variables_.empty() &&
solver_->constraints_.empty()) {
705 VLOG(1) << absl::StrFormat(
"Model built in %s.",
707 if (scip_constraint_handler_ !=
nullptr) {
712 CHECK_EQ(scip_constraint_handler_->mp_callback(), callback_);
713 }
else if (callback_ !=
nullptr) {
714 scip_constraint_handler_ =
715 absl::make_unique<ScipConstraintHandlerForMPCallback>(callback_);
716 RegisterConstraintHandler<EmptyStruct>(scip_constraint_handler_.get(),
718 AddCallbackConstraint<EmptyStruct>(scip_, scip_constraint_handler_.get(),
719 "mp_solver_callback_constraint_for_scip",
720 &constraint_data_for_handler_,
738 SetParameters(param);
740 solver_->solver_specific_parameter_string_);
743 if (!
solver_->solution_hint_.empty()) {
745 bool is_solution_partial =
false;
746 const int num_vars =
solver_->variables_.size();
747 if (
solver_->solution_hint_.size() != num_vars) {
750 SCIPcreatePartialSol(scip_, &solution,
nullptr));
751 is_solution_partial =
true;
758 for (
const std::pair<const MPVariable*, double>& p :
761 scip_, solution, scip_variables_[p.first->index()], p.second));
764 if (!is_solution_partial) {
765 SCIP_Bool is_feasible;
767 scip_, solution,
false,
true,
770 VLOG(1) <<
"Solution hint is "
771 << (is_feasible ?
"FEASIBLE" :
"INFEASIBLE");
779 if (!is_solution_partial && SCIPisTransformed(scip_)) {
781 scip_, &solution,
false,
true,
786 SCIPaddSolFree(scip_, &solution, &is_stored));
793 ? SCIPsolveConcurrent(scip_)
795 VLOG(1) << absl::StrFormat(
"Solved in %s.",
797 current_solution_index_ = 0;
799 SCIP_SOL*
const solution = SCIPgetBestSol(scip_);
800 if (solution !=
nullptr) {
802 SetSolution(solution);
804 VLOG(1) <<
"No feasible solution found.";
808 SCIP_STATUS scip_status = SCIPgetStatus(scip_);
809 switch (scip_status) {
810 case SCIP_STATUS_OPTIMAL:
813 case SCIP_STATUS_GAPLIMIT:
817 case SCIP_STATUS_INFEASIBLE:
820 case SCIP_STATUS_UNBOUNDED:
823 case SCIP_STATUS_INFORUNBD:
829 if (solution !=
nullptr) {
831 }
else if (scip_status == SCIP_STATUS_TIMELIMIT ||
832 scip_status == SCIP_STATUS_TOTALNODELIMIT) {
846void SCIPInterface::SetSolution(SCIP_SOL* solution) {
851 for (
int i = 0; i <
solver_->variables_.size(); ++i) {
853 const int var_index =
var->index();
855 SCIPgetSolVal(scip_, solution, scip_variables_[var_index]);
856 var->set_solution_value(val);
857 VLOG(3) <<
var->name() <<
"=" << val;
862 const MPModelRequest& request) {
867 if (status_or.ok())
return status_or.value();
870 if (absl::IsUnimplemented(status_or.status()))
return absl::nullopt;
872 if (request.enable_internal_solver_output()) {
873 LOG(
INFO) <<
"Invalid SCIP status: " << status_or.status();
876 response.set_status(MPSOLVER_NOT_SOLVED);
877 response.set_status_str(status_or.status().ToString());
881int SCIPInterface::SolutionCount() {
return SCIPgetNSols(scip_); }
888 if (current_solution_index_ + 1 >= SolutionCount()) {
891 current_solution_index_++;
892 SCIP_SOL** all_solutions = SCIPgetSols(scip_);
893 SetSolution(all_solutions[current_solution_index_]);
901 return SCIPgetNLPIterations(scip_);
910 return SCIPgetNTotalNodes(scip_);
918void SCIPInterface::SetRelativeMipGap(
double value) {
931 if (status_.ok()) status_ = status;
934void SCIPInterface::SetPrimalTolerance(
double value) {
938 if (status_.ok()) status_ = status;
941void SCIPInterface::SetDualTolerance(
double value) {
944 if (status_.ok()) status_ = status;
947void SCIPInterface::SetPresolveMode(
int presolve) {
952 SCIP_TO_STATUS(SCIPsetIntParam(scip_,
"presolving/maxrounds", 0));
953 if (status_.ok()) status_ = status;
958 SCIP_TO_STATUS(SCIPsetIntParam(scip_,
"presolving/maxrounds", -1));
959 if (status_.ok()) status_ = status;
969void SCIPInterface::SetScalingMode(
int scaling) {
976void SCIPInterface::SetLpAlgorithm(
int lp_algorithm) {
978 switch (lp_algorithm) {
982 if (status_.ok()) status_ = status;
988 if (status_.ok()) status_ = status;
995 if (status_.ok()) status_ = status;
1006void SCIPInterface::SetUnsupportedIntegerParam(
1010 status_ = absl::InvalidArgumentError(absl::StrFormat(
1011 "Tried to set unsupported integer parameter %d", param));
1015void SCIPInterface::SetIntegerParamToUnsupportedValue(
1019 status_ = absl::InvalidArgumentError(absl::StrFormat(
1020 "Tried to set integer parameter %d to unsupported value %d", param,
1025absl::Status SCIPInterface::SetNumThreads(
int num_threads) {
1026 if (SetSolverSpecificParametersAsString(
1027 absl::StrFormat(
"parallel/maxnthreads = %d\n", num_threads))) {
1028 return absl::OkStatus();
1030 return absl::InternalError(
1031 "Could not set parallel/maxnthreads, which may "
1032 "indicate that SCIP API has changed.");
1035bool SCIPInterface::SetSolverSpecificParametersAsString(
1037 const absl::Status s =
1041 <<
", error is: " << s;
1049 bool at_integer_solution)
1050 : scip_context_(scip_context),
1051 at_integer_solution_(at_integer_solution) {}
1054 if (at_integer_solution_) {
1071 constraint.
is_cut =
true;
1072 constraint.
range = cutting_plane;
1073 constraint.local =
false;
1074 constraints_added_.push_back(std::move(constraint));
1079 constraint.
is_cut =
false;
1080 constraint.
range = lazy_constraint;
1081 constraint.local =
false;
1082 constraints_added_.push_back(std::move(constraint));
1086 const absl::flat_hash_map<const MPVariable*, double>& solution)
override {
1087 LOG(
FATAL) <<
"SuggestSolution() not currently supported for SCIP.";
1102 return constraints_added_;
1107 bool at_integer_solution_;
1109 std::vector<CallbackRangeConstraint> constraints_added_;
1116 {
"mp_solver_constraint_handler",
1118 "A single constraint handler for all MPSolver models."}
1121 mp_callback_(mp_callback) {}
1123std::vector<CallbackRangeConstraint>
1126 return SeparateSolution(
context,
false);
1129std::vector<CallbackRangeConstraint>
1132 return SeparateSolution(
context,
true);
1135std::vector<CallbackRangeConstraint>
1136ScipConstraintHandlerForMPCallback::SeparateSolution(
1138 const bool at_integer_solution) {
1141 return mp_context.constraints_added();
1145 if (callback_ !=
nullptr) {
1146 callback_reset_ =
true;
1148 callback_ = mp_callback;
1158#undef RETURN_AND_STORE_IF_SCIP_ERROR
1159#undef RETURN_IF_ALREADY_IN_ERROR_STATE
1160#undef RETURN_ABNORMAL_IF_BAD_STATUS
1161#undef RETURN_ABNORMAL_IF_SCIP_ERROR
#define LOG_IF(severity, condition)
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define VLOG(verboselevel)
absl::Duration GetDuration() const
An expression of the form:
virtual void RunCallback(MPCallbackContext *callback_context)=0
The class for constraints of a Mathematical Programming (MP) model.
int index() const
Returns the index of the constraint in the MPSolver::constraints_.
double offset() const
Gets the constant term in the objective.
This mathematical programming (MP) solver class is the main class though which users build and solve ...
ResultStatus
The status of solving the problem.
@ FEASIBLE
feasible, or stopped by limit.
@ NOT_SOLVED
not been solved yet.
@ INFEASIBLE
proven infeasible.
@ UNBOUNDED
proven unbounded.
@ ABNORMAL
abnormal, i.e., error of some kind.
bool SetSolverSpecificParametersAsString(const std::string ¶meters)
Advanced usage: pass solver specific parameters in text format.
int GetNumThreads() const
Returns the number of threads to be used during solve.
const MPObjective & Objective() const
Returns the objective object.
double time_limit_in_secs() const
BasisStatus
Advanced usage: possible basis status values for a variable and the slack variable of a linear constr...
static constexpr int64 kUnknownNumberOfNodes
virtual void SetIntegerParamToUnsupportedValue(MPSolverParameters::IntegerParam param, int value)
static constexpr int64 kUnknownNumberOfIterations
void set_constraint_as_extracted(int ct_index, bool extracted)
MPSolver::ResultStatus result_status_
void InvalidateSolutionSynchronization()
void SetMIPParameters(const MPSolverParameters ¶m)
int last_constraint_index_
bool constraint_is_extracted(int ct_index) const
double best_objective_bound_
bool CheckSolutionIsSynchronizedAndExists() const
bool CheckSolutionIsSynchronized() const
void ResetExtractionInformation()
bool variable_is_extracted(int var_index) const
virtual void SetUnsupportedIntegerParam(MPSolverParameters::IntegerParam param)
void set_variable_as_extracted(int var_index, bool extracted)
void SetCommonParameters(const MPSolverParameters ¶m)
SynchronizationStatus sync_status_
This class stores parameter settings for LP and MIP solvers.
@ INCREMENTALITY_OFF
Start solve from scratch.
IntegerParam
Enumeration of parameters that take integer or categorical values.
@ LP_ALGORITHM
Algorithm to solve linear programs.
@ SCALING
Advanced usage: enable or disable matrix scaling.
@ PRESOLVE
Advanced usage: presolve mode.
@ INCREMENTALITY
Advanced usage: incrementality from one solve to the next.
@ BARRIER
Barrier algorithm.
@ PRESOLVE_ON
Presolve is on.
@ PRESOLVE_OFF
Presolve is off.
int GetIntegerParam(MPSolverParameters::IntegerParam param) const
Returns the value of an integer parameter.
The class for variables of a Mathematical Programming (MP) model.
int index() const
Returns the index of the variable in the MPSolver::variables_.
void BranchingPriorityChangedForVariable(int var_index) override
~SCIPInterface() override
void SetCoefficient(MPConstraint *constraint, const MPVariable *variable, double new_value, double old_value) override
void AddRowConstraint(MPConstraint *ct) override
int64 nodes() const override
void ExtractObjective() override
void * underlying_solver() override
bool IsContinuous() const override
void SetConstraintBounds(int row_index, double lb, double ub) override
bool InterruptSolve() override
MPSolver::ResultStatus Solve(const MPSolverParameters ¶m) override
void ClearConstraint(MPConstraint *constraint) override
MPSolver::BasisStatus row_status(int constraint_index) const override
bool SupportsCallbacks() const override
void SetVariableInteger(int var_index, bool integer) override
void SetCallback(MPCallback *mp_callback) override
void SetObjectiveOffset(double value) override
void AddVariable(MPVariable *var) override
SCIPInterface(MPSolver *solver)
void ExtractNewConstraints() override
std::string SolverVersion() const override
void ExtractNewVariables() override
void SetObjectiveCoefficient(const MPVariable *variable, double coefficient) override
bool AddIndicatorConstraint(MPConstraint *ct) override
void SetVariableBounds(int var_index, double lb, double ub) override
bool IsLP() const override
bool IsMIP() const override
absl::optional< MPSolutionResponse > DirectlySolveProto(const MPModelRequest &request) override
bool NextSolution() override
void SetOptimizationDirection(bool maximize) override
MPSolver::BasisStatus column_status(int variable_index) const override
int64 iterations() const override
void ClearObjective() override
double VariableValue(const MPVariable *variable) const
int64 NumNodesProcessed() const
bool is_pseudo_solution() const
ScipConstraintHandlerForMPCallback(MPCallback *mp_callback)
std::vector< CallbackRangeConstraint > SeparateFractionalSolution(const ScipConstraintHandlerContext &context, const EmptyStruct &) override
MPCallback *const mp_callback() const
std::vector< CallbackRangeConstraint > SeparateIntegerSolution(const ScipConstraintHandlerContext &context, const EmptyStruct &) override
ScipMPCallbackContext(const ScipConstraintHandlerContext *scip_context, bool at_integer_solution)
bool CanQueryVariableValues() override
const std::vector< CallbackRangeConstraint > & constraints_added()
void AddLazyConstraint(const LinearRange &lazy_constraint) override
MPCallbackEvent Event() override
void AddCut(const LinearRange &cutting_plane) override
double SuggestSolution(const absl::flat_hash_map< const MPVariable *, double > &solution) override
int64 NumExploredNodes() override
double VariableValue(const MPVariable *variable) override
SharedResponseManager * response
GurobiMPCallbackContext * context
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
absl::Cleanup< absl::decay_t< Callback > > MakeCleanup(Callback &&callback)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
MPSolverInterface * BuildSCIPInterface(MPSolver *const solver)
absl::StatusOr< MPSolutionResponse > ScipSolveProto(const MPModelRequest &request)
absl::Status LegacyScipSetSolverSpecificParameters(const std::string ¶meters, SCIP *scip)
#define SCIP_TO_STATUS(x)
#define RETURN_IF_SCIP_ERROR(x)
ABSL_FLAG(bool, scip_feasibility_emphasis, false, "When true, emphasize search towards feasibility. This may or " "may not result in speedups in some problems.")
#define RETURN_IF_ALREADY_IN_ERROR_STATE
#define RETURN_ABNORMAL_IF_SCIP_ERROR(x)
#define RETURN_AND_STORE_IF_SCIP_ERROR(x)
#define RETURN_ABNORMAL_IF_BAD_STATUS