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)
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);
158int 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);
271void 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);
567void CLPInterface::ResetParameters() {
572void CLPInterface::SetRelativeMipGap(
double value) {
573 LOG(
WARNING) <<
"The relative MIP gap is only available "
574 <<
"for discrete problems.";
577void CLPInterface::SetPrimalTolerance(
double value) {
578 clp_->setPrimalTolerance(
value);
581void CLPInterface::SetDualTolerance(
double value) {
582 clp_->setDualTolerance(
value);
585void CLPInterface::SetPresolveMode(
int value) {
588 options_->setPresolveType(ClpSolve::presolveOff);
592 options_->setPresolveType(ClpSolve::presolveOn);
601void CLPInterface::SetScalingMode(
int value) {
605void 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
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
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 ...
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.
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_
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)