Google OR-Tools: ortools/linear_solver/clp

Google OR-Tools: ortools/linear_solver/clp_interface.cc Source File

14#include <algorithm>

15#include <cstdint>

16#include <memory>

17#include <string>

18#include <vector>

20#include "absl/base/attributes.h"

21#include "absl/strings/str_format.h"

26#undef PACKAGE

27#undef VERSION

28#include "ClpConfig.h"

29#include "ClpMessage.hpp"

30#include "ClpSimplex.hpp"

31#include "CoinBuild.hpp"

36 public:

50 void Reset() override;

53 void SetVariableBounds(int var_index, double lb, double ub) override;

63 double new_value, double old_value) override;

69 double coefficient) override;

79 int64_t nodes() const override;

89 bool IsLP() const override { return true; }

90 bool IsMIP() const override { return false; }

96 std::string SolverVersion() const override { return "Clp " CLP_VERSION; }

99 return reinterpret_cast<void*>(clp_.get());

100 }

101

102 private:

103

104 void CreateDummyVariableForEmptyConstraints();

105

106

108

109

110

111 void ResetParameters();

112

113 void SetRelativeMipGap(double value) override;

114 void SetPrimalTolerance(double value) override;

115 void SetDualTolerance(double value) override;

116 void SetPresolveMode(int value) override;

117 void SetScalingMode(int value) override;

118 void SetLpAlgorithm(int value) override;

119

120

122 ClpSimplex::Status clp_basis_status) const;

123

124 std::unique_ptr<ClpSimplex> clp_;

125 std::unique_ptr<ClpSolve> options_;

126};

127

128

129

130

132 : MPSolverInterface(solver), clp_(new ClpSimplex), options_(new ClpSolve) {

133 clp_->setStrParam(ClpProbName, solver_->name_);

134 clp_->setOptimizationDirection(1);

135}

136

138

140 clp_ = std::make_unique<ClpSimplex>();

141 clp_->setOptimizationDirection(maximize_ ? -1 : 1);

143}

144

145

146

147namespace {

148

149

150int MPSolverVarIndexToClpVarIndex(int var_index) { return var_index + 1; }

151}

152

153

156 clp_->setOptimizationDirection(maximize ? -1 : 1);

157}

158

162

164 clp_->setColumnBounds(MPSolverVarIndexToClpVarIndex(var_index), lb, ub);

165 } else {

167 }

168}

169

170

172

176

178 clp_->setRowBounds(index, lb, ub);

179 } else {

181 }

182}

183

186 double new_value, double old_value) {

190

191

194 clp_->modifyCoefficient(constraint->index(),

195 MPSolverVarIndexToClpVarIndex(variable->index()),

196 new_value);

197 } else {

198

199

201 }

202}

203

204

207

209 for (const auto& entry : constraint->coefficients_) {

211 clp_->modifyCoefficient(constraint->index(),

212 MPSolverVarIndexToClpVarIndex(entry.first->index()),

213 0.0);

214 }

215}

216

217

219 double coefficient) {

222 clp_->setObjectiveCoefficient(

223 MPSolverVarIndexToClpVarIndex(variable->index()), coefficient);

224 } else {

226 }

227}

228

229

231

232

234 clp_->setObjectiveOffset(-offset);

235}

236

237

240

241 for (const auto& entry : solver_->objective_->coefficients_) {

242 const int mpsolver_var_index = entry.first->index();

243

246 } else {

247 clp_->setObjectiveCoefficient(

248 MPSolverVarIndexToClpVarIndex(mpsolver_var_index), 0.0);

249 }

250 }

251

252 clp_->setObjectiveOffset(0.0);

253}

254

258

262

263void CLPInterface::CreateDummyVariableForEmptyConstraints() {

266

267

268

269 std::string dummy = "dummy";

271}

272

273

275

276 int total_num_vars = solver_->variables_.size();

279

280 clp_->resize(0, total_num_vars + 1);

281 CreateDummyVariableForEmptyConstraints();

282 for (int i = 0; i < total_num_vars; ++i) {

285 if (!var->name().empty()) {

286 std::string name = var->name();

287 clp_->setColumnName(MPSolverVarIndexToClpVarIndex(i), name);

288 }

289 clp_->setColumnBounds(MPSolverVarIndexToClpVarIndex(i), var->lb(),

290 var->ub());

291 }

292 } else {

293

294

295

296

297

302

303 double tmp_obj_coef = 0.0;

304 clp_->addColumn(0, nullptr, nullptr, var->lb(), var->ub(),

305 tmp_obj_coef);

306 if (!var->name().empty()) {

307 std::string name = var->name();

308 clp_->setColumnName(MPSolverVarIndexToClpVarIndex(j), name);

309 }

310 }

311

314 const int ct_index = ct->index();

315 for (const auto& entry : ct->coefficients_) {

316 const int mpsolver_var_index = entry.first->index();

319 clp_->modifyCoefficient(

320 ct_index, MPSolverVarIndexToClpVarIndex(mpsolver_var_index),

321 entry.second);

322 }

323 }

324 }

325 }

326 }

327}

328

329

331 int total_num_rows = solver_->constraints_.size();

333

334 int max_row_length = 0;

339 if (ct->coefficients_.size() > max_row_length) {

340 max_row_length = ct->coefficients_.size();

341 }

342 }

343

344 max_row_length = std::max(1, max_row_length);

345 std::unique_ptr<int[]> indices(new int[max_row_length]);

346 std::unique_ptr<double[]> coefs(new double[max_row_length]);

347 CoinBuild build_object;

348

352 int size = ct->coefficients_.size();

353 if (size == 0) {

354

356 coefs[0] = 1.0;

357 size = 1;

358 }

359 int j = 0;

360 for (const auto& entry : ct->coefficients_) {

361 const int mpsolver_var_index = entry.first->index();

363 indices[j] = MPSolverVarIndexToClpVarIndex(mpsolver_var_index);

364 coefs[j] = entry.second;

365 j++;

366 }

367 build_object.addRow(size, indices.get(), coefs.get(), ct->lb(), ct->ub());

368 }

369

370 clp_->addRows(build_object);

373 if (!ct->name().empty()) {

374 std::string name = ct->name();

375 clp_->setRowName(ct->index(), name);

376 }

377 }

378 }

379}

380

382

383

384 for (const auto& entry : solver_->objective_->coefficients_) {

385 clp_->setObjectiveCoefficient(

386 MPSolverVarIndexToClpVarIndex(entry.first->index()), entry.second);

387 }

388

389

390

391 clp_->setObjectiveOffset(-solver_->Objective().offset());

392}

393

394

396 try {

399

403 }

404

405

406 CoinMessageHandler message_handler;

407 clp_->passInMessageHandler(&message_handler);

409 message_handler.setLogLevel(1, 0);

410 clp_->setLogLevel(0);

411 } else {

412 message_handler.setLogLevel(1, 1);

413 clp_->setLogLevel(1);

414 }

415

416

417

418 if (solver_->variables_.empty() && solver_->constraints_.empty()) {

423 }

424

426 VLOG(1) << absl::StrFormat("Model built in %.3f seconds.", timer.Get());

427

428

429 if (solver_->time_limit() != 0) {

430 VLOG(1) << "Setting time limit = " << solver_->time_limit() << " ms.";

431 clp_->setMaximumSeconds(solver_->time_limit_in_secs());

432 } else {

433 clp_->setMaximumSeconds(-1.0);

434 }

435

436

437

438 options_ = std::make_unique<ClpSolve>();

439 SetParameters(param);

440

441

443 clp_->initialSolve(*options_);

444 VLOG(1) << absl::StrFormat("Solved in %.3f seconds.", timer.Get());

445

446

447 int tmp_status = clp_->status();

448 VLOG(1) << "clp result status: " << tmp_status;

449 switch (tmp_status) {

450 case CLP_SIMPLEX_FINISHED:

452 break;

453 case CLP_SIMPLEX_INFEASIBLE:

455 break;

456 case CLP_SIMPLEX_UNBOUNDED:

458 break;

459 case CLP_SIMPLEX_STOPPED:

461 break;

462 default:

464 break;

465 }

466

469

472 const double* const values = clp_->getColSolution();

473 const double* const reduced_costs = clp_->getReducedCost();

474 for (int i = 0; i < solver_->variables_.size(); ++i) {

476 const int clp_var_index = MPSolverVarIndexToClpVarIndex(var->index());

477 const double val = values[clp_var_index];

479 VLOG(3) << var->name() << ": value = " << val;

480 double reduced_cost = reduced_costs[clp_var_index];

482 VLOG(4) << var->name() << ": reduced cost = " << reduced_cost;

483 }

484 const double* const dual_values = clp_->getRowPrice();

485 for (int i = 0; i < solver_->constraints_.size(); ++i) {

487 const int constraint_index = ct->index();

488 const double dual_value = dual_values[constraint_index];

490 VLOG(4) << "row " << ct->index() << " dual value = " << dual_value;

491 }

492 }

493

494 ResetParameters();

497 } catch (CoinError& e) {

498 LOG(WARNING) << "Caught exception in Coin LP: " << e.message();

501 }

502}

503

505 ClpSimplex::Status clp_basis_status) const {

506 switch (clp_basis_status) {

507 case ClpSimplex::isFree:

509 case ClpSimplex::basic:

511 case ClpSimplex::atUpperBound:

513 case ClpSimplex::atLowerBound:

515 case ClpSimplex::superBasic:

517 case ClpSimplex::isFixed:

519 default:

520 LOG(FATAL) << "Unknown CLP basis status";

522 }

523}

524

525

526

529 return clp_->getIterationCount();

530}

531

533 LOG(DFATAL) << "Number of nodes only available for discrete problems";

535}

536

538 DCHECK_LE(0, constraint_index);

540 const ClpSimplex::Status clp_basis_status =

541 clp_->getRowStatus(constraint_index);

542 return TransformCLPBasisStatus(clp_basis_status);

543}

544

546 DCHECK_LE(0, variable_index);

548 const ClpSimplex::Status clp_basis_status =

549 clp_->getColumnStatus(MPSolverVarIndexToClpVarIndex(variable_index));

550 return TransformCLPBasisStatus(clp_basis_status);

551}

552

553

554

557}

558

559void CLPInterface::ResetParameters() {

562}

563

564void CLPInterface::SetRelativeMipGap(double value) {

565 LOG(WARNING) << "The relative MIP gap is only available "

566 << "for discrete problems.";

567}

568

569void CLPInterface::SetPrimalTolerance(double value) {

570 clp_->setPrimalTolerance(value);

571}

572

573void CLPInterface::SetDualTolerance(double value) {

574 clp_->setDualTolerance(value);

575}

576

577void CLPInterface::SetPresolveMode(int value) {

578 switch (value) {

580 options_->setPresolveType(ClpSolve::presolveOff);

581 break;

582 }

584 options_->setPresolveType(ClpSolve::presolveOn);

585 break;

586 }

587 default: {

589 }

590 }

591}

592

593void CLPInterface::SetScalingMode(int value) {

595}

596

597void CLPInterface::SetLpAlgorithm(int value) {

598 switch (value) {

600 options_->setSolveType(ClpSolve::useDual);

601 break;

602 }

604 options_->setSolveType(ClpSolve::usePrimal);

605 break;

606 }

608 options_->setSolveType(ClpSolve::useBarrier);

609 break;

610 }

611 default: {

613 value);

614 }

615 }

616}

617

618namespace {

619

620

621const void* const kRegisterCLP ABSL_ATTRIBUTE_UNUSED = [] {

625 return nullptr;

626}();

627

628}

629

630}

Definition clp_interface.cc:35

int64_t iterations() const override

Definition clp_interface.cc:527

int64_t nodes() const override

Definition clp_interface.cc:532

~CLPInterface() override

Definition clp_interface.cc:137

MPSolver::BasisStatus row_status(int constraint_index) const override

Definition clp_interface.cc:537

CLPInterface(MPSolver *solver)

Definition clp_interface.cc:131

void ClearConstraint(MPConstraint *constraint) override

Definition clp_interface.cc:205

void ExtractNewConstraints() override

Definition clp_interface.cc:330

void SetVariableBounds(int var_index, double lb, double ub) override

Definition clp_interface.cc:159

void ClearObjective() override

Definition clp_interface.cc:238

MPSolver::BasisStatus column_status(int variable_index) const override

Definition clp_interface.cc:545

void AddRowConstraint(MPConstraint *ct) override

Definition clp_interface.cc:255

void SetObjectiveOffset(double offset) override

Definition clp_interface.cc:230

void * underlying_solver() override

Definition clp_interface.cc:98

void SetCoefficient(MPConstraint *constraint, const MPVariable *variable, double new_value, double old_value) override

Definition clp_interface.cc:184

void AddVariable(MPVariable *var) override

Definition clp_interface.cc:259

bool IsContinuous() const override

Definition clp_interface.cc:88

bool IsMIP() const override

Definition clp_interface.cc:90

bool IsLP() const override

Definition clp_interface.cc:89

std::string SolverVersion() const override

Definition clp_interface.cc:96

void SetConstraintBounds(int row_index, double lb, double ub) override

Definition clp_interface.cc:173

void SetOptimizationDirection(bool maximize) override

Definition clp_interface.cc:154

void SetVariableInteger(int var_index, bool integer) override

Definition clp_interface.cc:171

void ExtractNewVariables() override

Definition clp_interface.cc:274

void ExtractObjective() override

Definition clp_interface.cc:381

MPSolver::ResultStatus Solve(const MPSolverParameters &param) override

Definition clp_interface.cc:395

void SetObjectiveCoefficient(const MPVariable *variable, double coefficient) override

Definition clp_interface.cc:218

void Reset() override

Definition clp_interface.cc:139

void set_dual_value(double dual_value)

double lb() const

Returns the lower bound.

double ub() const

Returns the upper bound.

const std::string & name() const

Returns the name of the constraint.

int index() const

Returns the index of the constraint in the MPSolver::constraints_.

static MPSolverInterfaceFactoryRepository * GetInstance()

void Register(MPSolverInterfaceFactory factory, MPSolver::OptimizationProblemType problem_type, std::function< bool()> is_runtime_ready={})

void set_variable_as_extracted(int var_index, bool extracted)

bool CheckSolutionIsSynchronized() const

static constexpr int64_t kUnknownNumberOfIterations

friend class MPConstraint

void InvalidateSolutionSynchronization()

void set_constraint_as_extracted(int ct_index, bool extracted)

void ResetExtractionInformation()

virtual void SetIntegerParamToUnsupportedValue(MPSolverParameters::IntegerParam param, int value)

int last_constraint_index_

static const int kDummyVariableIndex

virtual void SetUnsupportedIntegerParam(MPSolverParameters::IntegerParam param)

bool variable_is_extracted(int var_index) const

bool constraint_is_extracted(int ct_index) const

static constexpr int64_t kUnknownNumberOfNodes

MPSolverInterface(MPSolver *solver)

void SetCommonParameters(const MPSolverParameters &param)

MPSolver::ResultStatus result_status_

SynchronizationStatus sync_status_

static const double kDefaultDualTolerance

static const double kDefaultPrimalTolerance

@ PRESOLVE_OFF

Presolve is off.

@ PRESOLVE_ON

Presolve is on.

@ BARRIER

Barrier algorithm.

@ INCREMENTALITY

Advanced usage: incrementality from one solve to the next.

@ PRESOLVE

Advanced usage: presolve mode.

@ LP_ALGORITHM

Algorithm to solve linear programs.

@ SCALING

Advanced usage: enable or disable matrix scaling.

@ INCREMENTALITY_OFF

Start solve from scratch.

int GetIntegerParam(MPSolverParameters::IntegerParam param) const

Returns the value of an integer parameter.

@ FEASIBLE

feasible, or stopped by limit.

@ INFEASIBLE

proven infeasible.

@ UNBOUNDED

proven unbounded.

@ ABNORMAL

abnormal, i.e., error of some kind.

The class for variables of a Mathematical Programming (MP) model.

double lb() const

Returns the lower bound.

double ub() const

Returns the upper bound.

const std::string & name() const

Returns the name of the variable.

void set_reduced_cost(double reduced_cost)

void set_solution_value(double value)

int index() const

Returns the index of the variable in the MPSolver::variables_.