21 #include "absl/memory/memory.h"
22 #include "absl/strings/match.h"
23 #include "absl/strings/str_format.h"
31 #if defined(USE_CLP) || defined(USE_CBC)
35 #include "ClpConfig.h"
36 #include "ClpMessage.hpp"
37 #include "ClpSimplex.hpp"
38 #include "CoinBuild.hpp"
57 void Reset()
override;
70 const MPVariable*
const variable,
double new_value,
71 double old_value)
override;
97 bool IsLP()
const override {
return true; }
98 bool IsMIP()
const override {
return false; }
107 return reinterpret_cast<void*
>(clp_.get());
112 void CreateDummyVariableForEmptyConstraints();
119 void ResetParameters();
121 void SetRelativeMipGap(
double value)
override;
122 void SetPrimalTolerance(
double value)
override;
123 void SetDualTolerance(
double value)
override;
124 void SetPresolveMode(
int value)
override;
125 void SetScalingMode(
int value)
override;
126 void SetLpAlgorithm(
int value)
override;
130 ClpSimplex::Status clp_basis_status)
const;
132 std::unique_ptr<ClpSimplex> clp_;
133 std::unique_ptr<ClpSolve> options_;
141 clp_->setStrParam(ClpProbName,
solver_->name_);
142 clp_->setOptimizationDirection(1);
148 clp_ = absl::make_unique<ClpSimplex>();
149 clp_->setOptimizationDirection(
maximize_ ? -1 : 1);
158 int MPSolverVarIndexToClpVarIndex(
int var_index) {
return var_index + 1; }
164 clp_->setOptimizationDirection(maximize ? -1 : 1);
172 clp_->setColumnBounds(MPSolverVarIndexToClpVarIndex(var_index), lb, ub);
186 clp_->setRowBounds(
index, lb, ub);
194 double new_value,
double old_value) {
202 clp_->modifyCoefficient(constraint->
index(),
203 MPSolverVarIndexToClpVarIndex(variable->
index()),
217 for (
const auto& entry : constraint->coefficients_) {
219 clp_->modifyCoefficient(constraint->
index(),
220 MPSolverVarIndexToClpVarIndex(entry.first->index()),
230 clp_->setObjectiveCoefficient(
242 clp_->setObjectiveOffset(-offset);
249 for (
const auto& entry :
solver_->objective_->coefficients_) {
250 const int mpsolver_var_index = entry.first->index();
255 clp_->setObjectiveCoefficient(
256 MPSolverVarIndexToClpVarIndex(mpsolver_var_index), 0.0);
260 clp_->setObjectiveOffset(0.0);
271 void CLPInterface::CreateDummyVariableForEmptyConstraints() {
277 std::string dummy =
"dummy";
284 int total_num_vars =
solver_->variables_.size();
288 clp_->resize(0, total_num_vars + 1);
289 CreateDummyVariableForEmptyConstraints();
290 for (
int i = 0; i < total_num_vars; ++i) {
293 if (!
var->name().empty()) {
294 std::string
name =
var->name();
295 clp_->setColumnName(MPSolverVarIndexToClpVarIndex(i),
name);
297 clp_->setColumnBounds(MPSolverVarIndexToClpVarIndex(i),
var->lb(),
311 double tmp_obj_coef = 0.0;
312 clp_->addColumn(0,
nullptr,
nullptr,
var->lb(),
var->ub(),
314 if (!
var->name().empty()) {
315 std::string
name =
var->name();
316 clp_->setColumnName(MPSolverVarIndexToClpVarIndex(j),
name);
322 const int ct_index =
ct->index();
323 for (
const auto& entry :
ct->coefficients_) {
324 const int mpsolver_var_index = entry.first->index();
327 clp_->modifyCoefficient(
328 ct_index, MPSolverVarIndexToClpVarIndex(mpsolver_var_index),
339 int total_num_rows =
solver_->constraints_.size();
342 int max_row_length = 0;
347 if (
ct->coefficients_.size() > max_row_length) {
348 max_row_length =
ct->coefficients_.size();
352 max_row_length =
std::max(1, max_row_length);
353 std::unique_ptr<int[]> indices(
new int[max_row_length]);
354 std::unique_ptr<double[]> coefs(
new double[max_row_length]);
355 CoinBuild build_object;
360 int size =
ct->coefficients_.size();
368 for (
const auto& entry :
ct->coefficients_) {
369 const int mpsolver_var_index = entry.first->index();
371 indices[j] = MPSolverVarIndexToClpVarIndex(mpsolver_var_index);
372 coefs[j] = entry.second;
375 build_object.addRow(size, indices.get(), coefs.get(),
ct->lb(),
ct->ub());
378 clp_->addRows(build_object);
381 if (!
ct->name().empty()) {
382 std::string
name =
ct->name();
383 clp_->setRowName(
ct->index(),
name);
392 for (
const auto& entry :
solver_->objective_->coefficients_) {
393 clp_->setObjectiveCoefficient(
394 MPSolverVarIndexToClpVarIndex(entry.first->index()), entry.second);
414 CoinMessageHandler message_handler;
415 clp_->passInMessageHandler(&message_handler);
417 message_handler.setLogLevel(1, 0);
418 clp_->setLogLevel(0);
420 message_handler.setLogLevel(1, 1);
421 clp_->setLogLevel(1);
426 if (
solver_->variables_.empty() &&
solver_->constraints_.empty()) {
434 VLOG(1) << absl::StrFormat(
"Model built in %.3f seconds.", timer.
Get());
441 clp_->setMaximumSeconds(-1.0);
446 options_ = absl::make_unique<ClpSolve>();
447 SetParameters(param);
451 clp_->initialSolve(*options_);
452 VLOG(1) << absl::StrFormat(
"Solved in %.3f seconds.", timer.
Get());
455 int tmp_status = clp_->status();
456 VLOG(1) <<
"clp result status: " << tmp_status;
457 switch (tmp_status) {
458 case CLP_SIMPLEX_FINISHED:
461 case CLP_SIMPLEX_INFEASIBLE:
464 case CLP_SIMPLEX_UNBOUNDED:
467 case CLP_SIMPLEX_STOPPED:
480 const double*
const values = clp_->getColSolution();
481 const double*
const reduced_costs = clp_->getReducedCost();
482 for (
int i = 0; i <
solver_->variables_.size(); ++i) {
484 const int clp_var_index = MPSolverVarIndexToClpVarIndex(
var->index());
485 const double val = values[clp_var_index];
486 var->set_solution_value(val);
487 VLOG(3) <<
var->name() <<
": value = " << val;
488 double reduced_cost = reduced_costs[clp_var_index];
489 var->set_reduced_cost(reduced_cost);
490 VLOG(4) <<
var->name() <<
": reduced cost = " << reduced_cost;
492 const double*
const dual_values = clp_->getRowPrice();
493 for (
int i = 0; i <
solver_->constraints_.size(); ++i) {
495 const int constraint_index =
ct->index();
496 const double dual_value = dual_values[constraint_index];
497 ct->set_dual_value(dual_value);
498 VLOG(4) <<
"row " <<
ct->index() <<
" dual value = " << dual_value;
505 }
catch (CoinError& e) {
506 LOG(
WARNING) <<
"Caught exception in Coin LP: " << e.message();
513 ClpSimplex::Status clp_basis_status)
const {
514 switch (clp_basis_status) {
515 case ClpSimplex::isFree:
517 case ClpSimplex::basic:
519 case ClpSimplex::atUpperBound:
521 case ClpSimplex::atLowerBound:
523 case ClpSimplex::superBasic:
525 case ClpSimplex::isFixed:
528 LOG(
FATAL) <<
"Unknown CLP basis status";
537 return clp_->getIterationCount();
541 LOG(DFATAL) <<
"Number of nodes only available for discrete problems";
548 const ClpSimplex::Status clp_basis_status =
549 clp_->getRowStatus(constraint_index);
550 return TransformCLPBasisStatus(clp_basis_status);
556 const ClpSimplex::Status clp_basis_status =
557 clp_->getColumnStatus(MPSolverVarIndexToClpVarIndex(variable_index));
558 return TransformCLPBasisStatus(clp_basis_status);
567 void CLPInterface::ResetParameters() {
572 void CLPInterface::SetRelativeMipGap(
double value) {
573 LOG(
WARNING) <<
"The relative MIP gap is only available "
574 <<
"for discrete problems.";
577 void CLPInterface::SetPrimalTolerance(
double value) {
578 clp_->setPrimalTolerance(
value);
581 void CLPInterface::SetDualTolerance(
double value) {
582 clp_->setDualTolerance(
value);
585 void CLPInterface::SetPresolveMode(
int value) {
588 options_->setPresolveType(ClpSolve::presolveOff);
592 options_->setPresolveType(ClpSolve::presolveOn);
601 void CLPInterface::SetScalingMode(
int value) {
605 void CLPInterface::SetLpAlgorithm(
int value) {
608 options_->setSolveType(ClpSolve::useDual);
612 options_->setSolveType(ClpSolve::usePrimal);
616 options_->setSolveType(ClpSolve::useBarrier);
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define VLOG(verboselevel)
void AddRowConstraint(MPConstraint *const 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
MPSolver::ResultStatus Solve(const MPSolverParameters ¶m) override
void ClearConstraint(MPConstraint *const constraint) override
void SetObjectiveCoefficient(const MPVariable *const variable, double coefficient) override
void SetCoefficient(MPConstraint *const constraint, const MPVariable *const variable, double new_value, double old_value) override
MPSolver::BasisStatus row_status(int constraint_index) const override
CLPInterface(MPSolver *const solver)
void SetVariableInteger(int var_index, bool integer) override
void ExtractNewConstraints() override
void SetObjectiveOffset(double offset) override
std::string SolverVersion() const override
void AddVariable(MPVariable *const var) override
void ExtractNewVariables() override
void SetVariableBounds(int var_index, double lb, double ub) override
bool IsLP() const override
bool IsMIP() const override
void SetOptimizationDirection(bool maximize) override
MPSolver::BasisStatus column_status(int variable_index) const override
int64 iterations() const override
void ClearObjective() override
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.
@ INFEASIBLE
proven infeasible.
@ UNBOUNDED
proven unbounded.
@ ABNORMAL
abnormal, i.e., error of some kind.
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_
static const int kDummyVariableIndex
void InvalidateSolutionSynchronization()
int last_constraint_index_
bool constraint_is_extracted(int ct_index) 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.
static const double kDefaultDualTolerance
@ 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.
static const double kDefaultPrimalTolerance
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_.
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
MPSolverInterface * BuildCLPInterface(MPSolver *const solver)