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"
42 #include "scip/scip.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.");
55 struct EmptyStruct {};
58 class 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();
282 absl::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();
307 SCIP* 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) {
846 void 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());
881 int 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_);
918 void SCIPInterface::SetRelativeMipGap(
double value) {
931 if (status_.ok()) status_ = status;
934 void SCIPInterface::SetPrimalTolerance(
double value) {
938 if (status_.ok()) status_ = status;
941 void SCIPInterface::SetDualTolerance(
double value) {
944 if (status_.ok()) status_ = status;
947 void 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;
969 void SCIPInterface::SetScalingMode(
int scaling) {
976 void 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;
1006 void SCIPInterface::SetUnsupportedIntegerParam(
1010 status_ = absl::InvalidArgumentError(absl::StrFormat(
1011 "Tried to set unsupported integer parameter %d", param));
1015 void SCIPInterface::SetIntegerParamToUnsupportedValue(
1019 status_ = absl::InvalidArgumentError(absl::StrFormat(
1020 "Tried to set integer parameter %d to unsupported value %d", param,
1025 absl::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.");
1035 bool 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) {}
1123 std::vector<CallbackRangeConstraint>
1126 return SeparateSolution(
context,
false);
1129 std::vector<CallbackRangeConstraint>
1132 return SeparateSolution(
context,
true);
1135 std::vector<CallbackRangeConstraint>
1136 ScipConstraintHandlerForMPCallback::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 ...
const MPObjective & Objective() const
Returns the objective object.
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.
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
void * underlying_solver() override
int64 nodes() const override
void ExtractObjective() 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)
const std::vector< CallbackRangeConstraint > & constraints_added()
bool CanQueryVariableValues() override
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