Google OR-Tools: ortools/linear_solver/cbc

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

14#include <cstdint>

15#include <limits>

16#include <memory>

17#include <string>

18#include <utility>

19#include <vector>

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

22#include "absl/status/status.h"

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

28#undef PACKAGE

29#undef VERSION

30#include "CbcConfig.h"

31#include "CbcMessage.hpp"

32#include "CbcModel.hpp"

33#include "CoinModel.hpp"

34#include "OsiClpSolverInterface.hpp"

41 public:

47 void Reset() override;

55 CHECK_GE(num_threads, 1);

56 num_threads_ = num_threads;

57 return absl::OkStatus();

58 }

69 bool IsLP() const override { return false; }

70 bool IsMIP() const override { return true; }

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

83 const MPVariable* const variable, double new_value,

84 double old_value) override {

86 }

94 double coefficient) override {

96 }

101

102

104

105 int64_t nodes() const override;

106

107

109 LOG(FATAL) << "Basis status only available for continuous problems";

111 }

112

114 LOG(FATAL) << "Basis status only available for continuous problems";

116 }

117

121

122 std::string SolverVersion() const override { return "Cbc " CBC_VERSION; }

123

124

125

126

127 void* underlying_solver() override { return reinterpret_cast<void*>(&osi_); }

128

129 private:

130

131

132 void ResetBestObjectiveBound();

133

134

136

137 void SetRelativeMipGap(double value) override;

138 void SetPrimalTolerance(double value) override;

139 void SetDualTolerance(double value) override;

140 void SetPresolveMode(int value) override;

141 void SetScalingMode(int value) override;

142 void SetLpAlgorithm(int value) override;

143

144 OsiClpSolverInterface osi_;

145

146 int64_t iterations_;

147 int64_t nodes_;

148

149 double relative_mip_gap_;

150 int num_threads_ = 1;

151};

152

153

154

155

158 iterations_(0),

159 nodes_(0),

161 osi_.setStrParam(OsiProbName, solver_->name_);

162 osi_.setObjSense(1);

163}

164

166

167

169 osi_.reset();

170 osi_.setObjSense(maximize_ ? -1 : 1);

171 osi_.setStrParam(OsiProbName, solver_->name_);

173}

174

175void CBCInterface::ResetBestObjectiveBound() {

178 } else {

180 }

181}

182

186 osi_.setObjSense(maximize ? -1 : 1);

187 } else {

189 }

190}

191

192namespace {

193

194int MPSolverVarIndexToCbcVarIndex(int var_index) { return var_index + 1; }

195}

196

200 osi_.setColBounds(MPSolverVarIndexToCbcVarIndex(var_index), lb, ub);

201 } else {

203 }

204}

205

208

210 if (integer) {

211 osi_.setInteger(MPSolverVarIndexToCbcVarIndex(var_index));

212 } else {

213 osi_.setContinuous(MPSolverVarIndexToCbcVarIndex(var_index));

214 }

215 } else {

217 }

218}

219

223 osi_.setRowBounds(index, lb, ub);

224 } else {

226 }

227}

228

232

236

237

238

240

241

242

243 if (!solver_->variables_.empty()) {

244 solver_->LookupVariableOrNull(solver_->variables_[0]->name());

245 }

246 if (!solver_->constraints_.empty()) {

247 solver_->LookupConstraintOrNull(solver_->constraints_[0]->name());

248 }

249

252

253

257 }

258

259

260

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

267 }

268

269

270

274 CoinModel build;

275

276 build.addColumn(0, nullptr, nullptr, 1.0, 1.0,

277 solver_->Objective().offset(), "dummy", false);

278 const int nb_vars = solver_->variables_.size();

279 for (int i = 0; i < nb_vars; ++i) {

282 const double obj_coeff = solver_->Objective().GetCoefficient(var);

283 if (var->name().empty()) {

284 build.addColumn(0, nullptr, nullptr, var->lb(), var->ub(), obj_coeff,

285 nullptr, var->integer());

286 } else {

287 build.addColumn(0, nullptr, nullptr, var->lb(), var->ub(), obj_coeff,

289 }

290 }

291

292

293 int max_row_length = 0;

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

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

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

299 }

300 }

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

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

303

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

306 const int size = ct->coefficients_.size();

307 int j = 0;

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

309 const int index = MPSolverVarIndexToCbcVarIndex(entry.first->index());

310 indices[j] = index;

311 coefs[j] = entry.second;

312 j++;

313 }

314 if (ct->name().empty()) {

315 build.addRow(size, indices.get(), coefs.get(), ct->lb(), ct->ub());

316 } else {

317 build.addRow(size, indices.get(), coefs.get(), ct->lb(), ct->ub(),

318 ct->name().c_str());

319 }

320 }

321 osi_.loadFromCoinModel(build);

322 break;

323 }

325 break;

326 }

328 break;

329 }

330 }

331

332

333

334 osi_.setObjSense(maximize_ ? -1 : 1);

335

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

338

339 ResetBestObjectiveBound();

340

341

342 CbcModel model(osi_);

343

344

345 CoinMessageHandler message_handler;

346 model.passInMessageHandler(&message_handler);

348 message_handler.setLogLevel(0, 0);

349 message_handler.setLogLevel(1, 0);

350 message_handler.setLogLevel(2, 0);

351 message_handler.setLogLevel(3, 0);

352 } else {

353 message_handler.setLogLevel(0, 1);

354 message_handler.setLogLevel(1, 1);

355 message_handler.setLogLevel(2, 1);

356 message_handler.setLogLevel(3, 1);

357 }

358

359

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

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

362 model.setMaximumSeconds(solver_->time_limit_in_secs());

363 }

364

365

367

368

369

370

371 SetParameters(param);

372

373

374 model.setTypePresolve(0);

375

376

377 model.setAllowableFractionGap(relative_mip_gap_);

378

379 int return_status =

380 num_threads_ == 1

381 ? callCbc("-solve ", model)

382 : callCbc(absl::StrCat("-threads ", num_threads_, " -solve "), model);

383 const int kBadReturnStatus = 777;

384 CHECK_NE(kBadReturnStatus, return_status);

385

386

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

388

389

390 int tmp_status = model.status();

391

392 VLOG(1) << "cbc result status: " << tmp_status;

393

394

395

396

397

398

399

400

401

402

403

404

405 switch (tmp_status) {

406 case 0:

407

408

409 if (model.isProvenOptimal()) {

411 } else if (model.isContinuousUnbounded()) {

413 } else if (model.isProvenInfeasible()) {

415 } else if (model.isAbandoned()) {

417 } else {

419 }

420 break;

421 case 1:

422 if (model.bestSolution() != nullptr) {

424 } else {

426 }

427 break;

428 default:

430 break;

431 }

432

435

438 const double* const values = model.bestSolution();

439 if (values != nullptr) {

440

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

443 const int var_index = MPSolverVarIndexToCbcVarIndex(var->index());

444 const double val = values[var_index];

446 VLOG(3) << var->name() << "=" << val;

447 }

448 } else {

449 VLOG(1) << "No feasible solution found.";

450 }

451 }

452

453 iterations_ = model.getIterationCount();

454 nodes_ = model.getNodeCount();

457

459

461}

462

463

464

467 return iterations_;

468}

469

474

475

476

477

478

479

480

481

482

486}

487

488void CBCInterface::SetRelativeMipGap(double value) {

489 relative_mip_gap_ = value;

490}

491

492void CBCInterface::SetPrimalTolerance(double value) {

493

494

497 }

498}

499

500void CBCInterface::SetDualTolerance(double value) {

501

502

505 }

506}

507

508void CBCInterface::SetPresolveMode(int value) {

509 switch (value) {

511

512 break;

513 }

514 default: {

516 }

517 }

518}

519

520void CBCInterface::SetScalingMode(int value) {

522}

523

524void CBCInterface::SetLpAlgorithm(int value) {

526}

527

528namespace {

529

530

531const void* const kRegisterCBC ABSL_ATTRIBUTE_UNUSED = [] {

535 return nullptr;

536}();

537

538}

539

540}

Definition cbc_interface.cc:40

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

Definition cbc_interface.cc:220

MPSolver::BasisStatus row_status(int constraint_index) const override

Definition cbc_interface.cc:108

void AddRowConstraint(MPConstraint *ct) override

Definition cbc_interface.cc:229

void ClearObjective() override

Definition cbc_interface.cc:100

void ClearConstraint(MPConstraint *const constraint) override

Definition cbc_interface.cc:88

CBCInterface(MPSolver *solver)

Definition cbc_interface.cc:156

void ExtractNewConstraints() override

Definition cbc_interface.cc:119

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

Definition cbc_interface.cc:197

void ExtractNewVariables() override

Definition cbc_interface.cc:118

absl::Status SetNumThreads(int num_threads) override

Definition cbc_interface.cc:54

int64_t nodes() const override

Definition cbc_interface.cc:470

void ExtractObjective() override

Definition cbc_interface.cc:120

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

Definition cbc_interface.cc:93

void SetOptimizationDirection(bool maximize) override

Definition cbc_interface.cc:183

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

Definition cbc_interface.cc:239

void AddVariable(MPVariable *var) override

Definition cbc_interface.cc:233

MPSolver::BasisStatus column_status(int variable_index) const override

Definition cbc_interface.cc:113

bool IsLP() const override

Definition cbc_interface.cc:69

void Reset() override

Definition cbc_interface.cc:168

int64_t iterations() const override

Definition cbc_interface.cc:465

bool IsMIP() const override

Definition cbc_interface.cc:70

void SetVariableInteger(int var_index, bool integer) override

Definition cbc_interface.cc:206

~CBCInterface() override

Definition cbc_interface.cc:165

std::string SolverVersion() const override

Definition cbc_interface.cc:122

void SetObjectiveOffset(double value) override

Definition cbc_interface.cc:98

bool IsContinuous() const override

Definition cbc_interface.cc:68

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

Definition cbc_interface.cc:82

virtual void ExtractModel()

Definition cbc_interface.cc:65

void * underlying_solver() override

Definition cbc_interface.cc:127

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.

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 SetUnsupportedIntegerParam(MPSolverParameters::IntegerParam param)

void SetUnsupportedDoubleParam(MPSolverParameters::DoubleParam param)

static constexpr int64_t kUnknownNumberOfNodes

double best_objective_bound_

void SetMIPParameters(const MPSolverParameters &param)

MPSolverInterface(MPSolver *solver)

void SetCommonParameters(const MPSolverParameters &param)

MPSolver::ResultStatus result_status_

SynchronizationStatus sync_status_

static const double kDefaultDualTolerance

static const double kDefaultPrimalTolerance

@ DUAL_TOLERANCE

Advanced usage: tolerance for dual feasibility of basic solutions.

@ PRESOLVE_ON

Presolve is on.

@ 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.

@ NOT_SOLVED

not been solved yet.

@ INFEASIBLE

proven infeasible.

@ UNBOUNDED

proven unbounded.

@ ABNORMAL

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

@ CBC_MIXED_INTEGER_PROGRAMMING

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

bool integer() const

Returns the integrality requirement of the variable.

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_solution_value(double value)

int index() const

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