OR-Tools  8.2
cbc_interface.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14//
15
16#include <limits>
17#include <memory>
18#include <string>
19#include <utility>
20#include <vector>
21
22#include "absl/status/status.h"
23#include "absl/strings/str_format.h"
25#include "ortools/base/hash.h"
28#include "ortools/base/timer.h"
30
31#if defined(USE_CBC)
32
33#undef PACKAGE
34#undef VERSION
35#include "CbcConfig.h"
36#include "CbcMessage.hpp"
37#include "CbcModel.hpp"
38#include "CoinModel.hpp"
39#include "OsiClpSolverInterface.hpp"
40
41// Heuristics
42
43namespace operations_research {
44
46 public:
47 // Constructor that takes a name for the underlying glpk solver.
48 explicit CBCInterface(MPSolver* const solver);
49 ~CBCInterface() override;
50
51 // ----- Reset -----
52 void Reset() override;
53
54 // Sets the optimization direction (min/max).
55 void SetOptimizationDirection(bool maximize) override;
56
57 // ----- Parameters -----
58
59 absl::Status SetNumThreads(int num_threads) override {
60 CHECK_GE(num_threads, 1);
61 num_threads_ = num_threads;
62 return absl::OkStatus();
63 }
64
65 // ----- Solve -----
66 // Solve the problem using the parameter values specified.
67 MPSolver::ResultStatus Solve(const MPSolverParameters& param) override;
68
69 // TODO(user): separate the solve from the model extraction.
70 virtual void ExtractModel() {}
71
72 // Query problem type.
73 bool IsContinuous() const override { return false; }
74 bool IsLP() const override { return false; }
75 bool IsMIP() const override { return true; }
76
77 // Modify bounds.
78 void SetVariableBounds(int var_index, double lb, double ub) override;
79 void SetVariableInteger(int var_index, bool integer) override;
80 void SetConstraintBounds(int row_index, double lb, double ub) override;
81
82 // Add constraint incrementally.
83 void AddRowConstraint(MPConstraint* const ct) override;
84 // Add variable incrementally.
85 void AddVariable(MPVariable* const var) override;
86 // Change a coefficient in a constraint.
87 void SetCoefficient(MPConstraint* const constraint,
88 const MPVariable* const variable, double new_value,
89 double old_value) override {
91 }
92 // Clear a constraint from all its terms.
93 void ClearConstraint(MPConstraint* const constraint) override {
95 }
96
97 // Change a coefficient in the linear objective.
98 void SetObjectiveCoefficient(const MPVariable* const variable,
99 double coefficient) override {
101 }
102 // Change the constant term in the linear objective.
104 // Clear the objective from all its terms.
106
107 // Number of simplex iterations
108 int64 iterations() const override;
109 // Number of branch-and-bound nodes. Only available for discrete problems.
110 int64 nodes() const override;
111
112 // Returns the basis status of a row.
113 MPSolver::BasisStatus row_status(int constraint_index) const override {
114 LOG(FATAL) << "Basis status only available for continuous problems";
115 return MPSolver::FREE;
116 }
117 // Returns the basis status of a column.
118 MPSolver::BasisStatus column_status(int variable_index) const override {
119 LOG(FATAL) << "Basis status only available for continuous problems";
120 return MPSolver::FREE;
121 }
122
123 void ExtractNewVariables() override {}
124 void ExtractNewConstraints() override {}
125 void ExtractObjective() override {}
126
127 std::string SolverVersion() const override { return "Cbc " CBC_VERSION; }
128
129 // TODO(user): Maybe we should expose the CbcModel build from osi_
130 // instead, but a new CbcModel is built every time Solve is called,
131 // so it is not possible right now.
132 void* underlying_solver() override { return reinterpret_cast<void*>(&osi_); }
133
134 private:
135 // Reset best objective bound to +/- infinity depending on the
136 // optimization direction.
137 void ResetBestObjectiveBound();
138
139 // Set all parameters in the underlying solver.
140 void SetParameters(const MPSolverParameters& param) override;
141 // Set each parameter in the underlying solver.
142 void SetRelativeMipGap(double value) override;
143 void SetPrimalTolerance(double value) override;
144 void SetDualTolerance(double value) override;
145 void SetPresolveMode(int value) override;
146 void SetScalingMode(int value) override;
147 void SetLpAlgorithm(int value) override;
148
149 OsiClpSolverInterface osi_;
150 // TODO(user): remove and query number of iterations directly from CbcModel
151 int64 iterations_;
152 int64 nodes_;
153 // Special way to handle the relative MIP gap parameter.
154 double relative_mip_gap_;
155 int num_threads_ = 1;
156};
157
158// ----- Solver -----
159
160// Creates a LP/MIP instance with the specified name and minimization objective.
162 : MPSolverInterface(solver),
163 iterations_(0),
164 nodes_(0),
165 relative_mip_gap_(MPSolverParameters::kDefaultRelativeMipGap) {
166 osi_.setStrParam(OsiProbName, solver_->name_);
167 osi_.setObjSense(1);
168}
169
171
172// Reset the solver.
174 osi_.reset();
175 osi_.setObjSense(maximize_ ? -1 : 1);
176 osi_.setStrParam(OsiProbName, solver_->name_);
178}
179
180void CBCInterface::ResetBestObjectiveBound() {
181 if (maximize_) {
182 best_objective_bound_ = std::numeric_limits<double>::infinity();
183 } else {
184 best_objective_bound_ = -std::numeric_limits<double>::infinity();
185 }
186}
187
191 osi_.setObjSense(maximize ? -1 : 1);
192 } else {
194 }
195}
196
197namespace {
198// CBC adds a "dummy" variable with index 0 to represent the objective offset.
199int MPSolverVarIndexToCbcVarIndex(int var_index) { return var_index + 1; }
200} // namespace
201
202void CBCInterface::SetVariableBounds(int var_index, double lb, double ub) {
205 osi_.setColBounds(MPSolverVarIndexToCbcVarIndex(var_index), lb, ub);
206 } else {
208 }
209}
210
211void CBCInterface::SetVariableInteger(int var_index, bool integer) {
213 // TODO(user) : Check if this is actually a change.
215 if (integer) {
216 osi_.setInteger(MPSolverVarIndexToCbcVarIndex(var_index));
217 } else {
218 osi_.setContinuous(MPSolverVarIndexToCbcVarIndex(var_index));
219 }
220 } else {
222 }
223}
224
225void CBCInterface::SetConstraintBounds(int index, double lb, double ub) {
228 osi_.setRowBounds(index, lb, ub);
229 } else {
231 }
232}
233
236}
237
240}
241
242// Solve the LP/MIP. Returns true only if the optimal solution was revealed.
243// Returns the status of the search.
245 // CBC requires unique variable and constraint names. By using Lookup*, we
246 // generate variable and constraint indices and ensure the duplicate name
247 // crash will happen here with a readable error message.
248 if (!solver_->variables_.empty()) {
249 solver_->LookupVariableOrNull(solver_->variables_[0]->name());
250 }
251 if (!solver_->constraints_.empty()) {
252 solver_->LookupConstraintOrNull(solver_->constraints_[0]->name());
253 }
254
255 WallTimer timer;
256 timer.Start();
257
258 // Note that CBC does not provide any incrementality.
261 Reset();
262 }
263
264 // Special case if the model is empty since CBC is not able to
265 // handle this special case by itself.
266 if (solver_->variables_.empty() && solver_->constraints_.empty()) {
271 return result_status_;
272 }
273
274 // Finish preparing the problem.
275 // Define variables.
276 switch (sync_status_) {
277 case MUST_RELOAD: {
278 Reset();
279 CoinModel build;
280 // Create dummy variable for objective offset.
281 build.addColumn(0, nullptr, nullptr, 1.0, 1.0,
282 solver_->Objective().offset(), "dummy", false);
283 const int nb_vars = solver_->variables_.size();
284 for (int i = 0; i < nb_vars; ++i) {
285 MPVariable* const var = solver_->variables_[i];
287 const double obj_coeff = solver_->Objective().GetCoefficient(var);
288 if (var->name().empty()) {
289 build.addColumn(0, nullptr, nullptr, var->lb(), var->ub(), obj_coeff,
290 nullptr, var->integer());
291 } else {
292 build.addColumn(0, nullptr, nullptr, var->lb(), var->ub(), obj_coeff,
293 var->name().c_str(), var->integer());
294 }
295 }
296
297 // Define constraints.
298 int max_row_length = 0;
299 for (int i = 0; i < solver_->constraints_.size(); ++i) {
300 MPConstraint* const ct = solver_->constraints_[i];
302 if (ct->coefficients_.size() > max_row_length) {
303 max_row_length = ct->coefficients_.size();
304 }
305 }
306 std::unique_ptr<int[]> indices(new int[max_row_length]);
307 std::unique_ptr<double[]> coefs(new double[max_row_length]);
308
309 for (int i = 0; i < solver_->constraints_.size(); ++i) {
310 MPConstraint* const ct = solver_->constraints_[i];
311 const int size = ct->coefficients_.size();
312 int j = 0;
313 for (const auto& entry : ct->coefficients_) {
314 const int index = MPSolverVarIndexToCbcVarIndex(entry.first->index());
315 indices[j] = index;
316 coefs[j] = entry.second;
317 j++;
318 }
319 if (ct->name().empty()) {
320 build.addRow(size, indices.get(), coefs.get(), ct->lb(), ct->ub());
321 } else {
322 build.addRow(size, indices.get(), coefs.get(), ct->lb(), ct->ub(),
323 ct->name().c_str());
324 }
325 }
326 osi_.loadFromCoinModel(build);
327 break;
328 }
329 case MODEL_SYNCHRONIZED: {
330 break;
331 }
333 break;
334 }
335 }
336
337 // Changing optimization direction through OSI so that the model file
338 // (written through OSI) has the correct optimization duration.
339 osi_.setObjSense(maximize_ ? -1 : 1);
340
342 VLOG(1) << absl::StrFormat("Model built in %.3f seconds.", timer.Get());
343
344 ResetBestObjectiveBound();
345
346 // Solve
347 CbcModel model(osi_);
348
349 // Set log level.
350 CoinMessageHandler message_handler;
351 model.passInMessageHandler(&message_handler);
352 if (quiet_) {
353 message_handler.setLogLevel(0, 0); // Coin messages
354 message_handler.setLogLevel(1, 0); // Clp messages
355 message_handler.setLogLevel(2, 0); // Presolve messages
356 message_handler.setLogLevel(3, 0); // Cgl messages
357 } else {
358 message_handler.setLogLevel(0, 1); // Coin messages
359 message_handler.setLogLevel(1, 1); // Clp messages
360 message_handler.setLogLevel(2, 1); // Presolve messages
361 message_handler.setLogLevel(3, 1); // Cgl messages
362 }
363
364 // Time limit.
365 if (solver_->time_limit() != 0) {
366 VLOG(1) << "Setting time limit = " << solver_->time_limit() << " ms.";
367 model.setMaximumSeconds(solver_->time_limit_in_secs());
368 }
369
370 // And solve.
371 timer.Restart();
372
373 // Here we use the default function from the command-line CBC solver.
374 // This enables to activate all the features and get the same performance
375 // as the CBC stand-alone executable. The syntax is ugly, however.
376 SetParameters(param);
377 // Always turn presolve on (it's the CBC default and it consistently
378 // improves performance).
379 model.setTypePresolve(0);
380 // Special way to set the relative MIP gap parameter as it cannot be set
381 // through callCbc.
382 model.setAllowableFractionGap(relative_mip_gap_);
383 // NOTE: Trailing space is required to avoid buffer overflow in cbc.
384 int return_status =
385 num_threads_ == 1
386 ? callCbc("-solve ", model)
387 : callCbc(absl::StrCat("-threads ", num_threads_, " -solve "), model);
388 const int kBadReturnStatus = 777;
389 CHECK_NE(kBadReturnStatus, return_status); // Should never happen according
390 // to the CBC source
391
392 VLOG(1) << absl::StrFormat("Solved in %.3f seconds.", timer.Get());
393
394 // Check the status: optimal, infeasible, etc.
395 int tmp_status = model.status();
396
397 VLOG(1) << "cbc result status: " << tmp_status;
398 /* Final status of problem
399 (info from cbc/.../CbcSolver.cpp,
400 See http://cs?q="cbc+status"+file:CbcSolver.cpp)
401 Some of these can be found out by is...... functions
402 -1 before branchAndBound
403 0 finished - check isProvenOptimal or isProvenInfeasible to see
404 if solution found
405 (or check value of best solution)
406 1 stopped - on maxnodes, maxsols, maxtime
407 2 difficulties so run was abandoned
408 (5 event user programmed event occurred)
409 */
410 switch (tmp_status) {
411 case 0:
412 // Order of tests counts; if model.isContinuousUnbounded() returns true,
413 // then so does model.isProvenInfeasible()!
414 if (model.isProvenOptimal()) {
416 } else if (model.isContinuousUnbounded()) {
418 } else if (model.isProvenInfeasible()) {
420 } else if (model.isAbandoned()) {
422 } else {
424 }
425 break;
426 case 1:
427 if (model.bestSolution() != nullptr) {
429 } else {
431 }
432 break;
433 default:
435 break;
436 }
437
440 // Get the results
441 objective_value_ = model.getObjValue();
442 VLOG(1) << "objective=" << objective_value_;
443 const double* const values = model.bestSolution();
444 if (values != nullptr) {
445 // if optimal or feasible solution is found.
446 for (int i = 0; i < solver_->variables_.size(); ++i) {
447 MPVariable* const var = solver_->variables_[i];
448 const int var_index = MPSolverVarIndexToCbcVarIndex(var->index());
449 const double val = values[var_index];
450 var->set_solution_value(val);
451 VLOG(3) << var->name() << "=" << val;
452 }
453 } else {
454 VLOG(1) << "No feasible solution found.";
455 }
456 }
457
458 iterations_ = model.getIterationCount();
459 nodes_ = model.getNodeCount();
460 best_objective_bound_ = model.getBestPossibleObjValue();
461 VLOG(1) << "best objective bound=" << best_objective_bound_;
462
464
465 return result_status_;
466}
467
468// ------ Query statistics on the solution and the solve ------
469
472 return iterations_;
473}
474
477 return nodes_;
478}
479
480// ----- Parameters -----
481
482// The support for parameters in CBC is intentionally sparse. There is
483// a memory leak in callCbc that prevents to pass parameters through
484// it, so handling parameters would require an comprehensive rewrite
485// of the code. I will improve the parameter support only if there is
486// a relevant use case.
487
488void CBCInterface::SetParameters(const MPSolverParameters& param) {
489 SetCommonParameters(param);
490 SetMIPParameters(param);
491}
492
493void CBCInterface::SetRelativeMipGap(double value) {
494 relative_mip_gap_ = value;
495}
496
497void CBCInterface::SetPrimalTolerance(double value) {
498 // Skip the warning for the default value as it coincides with
499 // the default value in CBC.
502 }
503}
504
505void CBCInterface::SetDualTolerance(double value) {
506 // Skip the warning for the default value as it coincides with
507 // the default value in CBC.
510 }
511}
512
513void CBCInterface::SetPresolveMode(int value) {
514 switch (value) {
516 // CBC presolve is always on.
517 break;
518 }
519 default: {
521 }
522 }
523}
524
525void CBCInterface::SetScalingMode(int value) {
527}
528
529void CBCInterface::SetLpAlgorithm(int value) {
531}
532
534 return new CBCInterface(solver);
535}
536
537} // namespace operations_research
538#endif // #if defined(USE_CBC)
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define LOG(severity)
Definition: base/logging.h:420
#define VLOG(verboselevel)
Definition: base/logging.h:978
void Start()
Definition: timer.h:31
void Restart()
Definition: timer.h:35
double Get() const
Definition: timer.h:45
void AddRowConstraint(MPConstraint *const ct) override
int64 nodes() const override
bool IsContinuous() const override
void SetConstraintBounds(int row_index, double lb, double ub) override
MPSolver::ResultStatus Solve(const MPSolverParameters &param) 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
void SetVariableInteger(int var_index, bool integer) override
void SetObjectiveOffset(double value) override
std::string SolverVersion() const override
absl::Status SetNumThreads(int num_threads) override
void AddVariable(MPVariable *const var) override
CBCInterface(MPSolver *const solver)
void SetVariableBounds(int var_index, double lb, double ub) override
void SetOptimizationDirection(bool maximize) override
MPSolver::BasisStatus column_status(int variable_index) const override
int64 iterations() const override
The class for constraints of a Mathematical Programming (MP) model.
double GetCoefficient(const MPVariable *const var) const
Gets the coefficient of a given variable in the objective.
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 ...
MPVariable * LookupVariableOrNull(const std::string &var_name) const
Looks up a variable by name, and returns nullptr if it does not exist.
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.
MPConstraint * LookupConstraintOrNull(const std::string &constraint_name) const
Looks up a constraint by name, and returns nullptr if it does not exist.
const MPObjective & Objective() const
Returns the objective object.
BasisStatus
Advanced usage: possible basis status values for a variable and the slack variable of a linear constr...
static constexpr int64 kUnknownNumberOfNodes
static constexpr int64 kUnknownNumberOfIterations
void SetUnsupportedDoubleParam(MPSolverParameters::DoubleParam param)
void set_constraint_as_extracted(int ct_index, bool extracted)
void SetMIPParameters(const MPSolverParameters &param)
virtual void SetUnsupportedIntegerParam(MPSolverParameters::IntegerParam param)
void set_variable_as_extracted(int var_index, bool extracted)
void SetCommonParameters(const MPSolverParameters &param)
This class stores parameter settings for LP and MIP solvers.
@ INCREMENTALITY_OFF
Start solve from scratch.
@ DUAL_TOLERANCE
Advanced usage: tolerance for dual feasibility of basic solutions.
@ PRIMAL_TOLERANCE
Advanced usage: tolerance for primal feasibility of basic solutions.
@ 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.
int GetIntegerParam(MPSolverParameters::IntegerParam param) const
Returns the value of an integer parameter.
The class for variables of a Mathematical Programming (MP) model.
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
int64_t int64
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
const int FATAL
Definition: log_severity.h:32
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
MPSolverInterface * BuildCBCInterface(MPSolver *const solver)
int index
Definition: pack.cc:508
int64 coefficient