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"
27 #include "ortools/base/logging.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 
43 namespace 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.
103  void SetObjectiveOffset(double value) override { sync_status_ = MUST_RELOAD; }
104  // Clear the objective from all its terms.
105  void ClearObjective() override { sync_status_ = MUST_RELOAD; }
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 
180 void 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 
197 namespace {
198 // CBC adds a "dummy" variable with index 0 to represent the objective offset.
199 int MPSolverVarIndexToCbcVarIndex(int var_index) { return var_index + 1; }
200 } // namespace
201 
202 void CBCInterface::SetVariableBounds(int var_index, double lb, double ub) {
205  osi_.setColBounds(MPSolverVarIndexToCbcVarIndex(var_index), lb, ub);
206  } else {
208  }
209 }
210 
211 void 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 
225 void 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];
286  set_variable_as_extracted(i, true);
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  }
332  case SOLUTION_SYNCHRONIZED: {
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 
488 void CBCInterface::SetParameters(const MPSolverParameters& param) {
489  SetCommonParameters(param);
490  SetMIPParameters(param);
491 }
492 
493 void CBCInterface::SetRelativeMipGap(double value) {
494  relative_mip_gap_ = value;
495 }
496 
497 void 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 
505 void 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 
513 void CBCInterface::SetPresolveMode(int value) {
514  switch (value) {
516  // CBC presolve is always on.
517  break;
518  }
519  default: {
521  }
522  }
523 }
524 
525 void CBCInterface::SetScalingMode(int value) {
527 }
528 
529 void 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.
const MPObjective & Objective() const
Returns the objective object.
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.
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