OR-Tools  8.2
clp_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 <algorithm>
17#include <memory>
18#include <string>
19#include <vector>
20
21#include "absl/memory/memory.h"
22#include "absl/strings/match.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_CLP) || defined(USE_CBC)
32
33#undef PACKAGE
34#undef VERSION
35#include "ClpConfig.h"
36#include "ClpMessage.hpp"
37#include "ClpSimplex.hpp"
38#include "CoinBuild.hpp"
39
40namespace operations_research {
41
43 public:
44 // Constructor that takes a name for the underlying CLP solver.
45 explicit CLPInterface(MPSolver* const solver);
46 ~CLPInterface() override;
47
48 // Sets the optimization direction (min/max).
49 void SetOptimizationDirection(bool maximize) override;
50
51 // ----- Solve -----
52 // Solve the problem using the parameter values specified.
53 MPSolver::ResultStatus Solve(const MPSolverParameters& param) override;
54
55 // ----- Model modifications and extraction -----
56 // Resets extracted model
57 void Reset() override;
58
59 // Modify bounds.
60 void SetVariableBounds(int var_index, double lb, double ub) override;
61 void SetVariableInteger(int var_index, bool integer) override;
62 void SetConstraintBounds(int row_index, double lb, double ub) override;
63
64 // Add constraint incrementally.
65 void AddRowConstraint(MPConstraint* const ct) override;
66 // Add variable incrementally.
67 void AddVariable(MPVariable* const var) override;
68 // Change a coefficient in a constraint.
69 void SetCoefficient(MPConstraint* const constraint,
70 const MPVariable* const variable, double new_value,
71 double old_value) override;
72 // Clear a constraint from all its terms.
73 void ClearConstraint(MPConstraint* const constraint) override;
74
75 // Change a coefficient in the linear objective.
76 void SetObjectiveCoefficient(const MPVariable* const variable,
77 double coefficient) override;
78 // Change the constant term in the linear objective.
79 void SetObjectiveOffset(double offset) override;
80 // Clear the objective from all its terms.
81 void ClearObjective() override;
82
83 // ------ Query statistics on the solution and the solve ------
84 // Number of simplex iterations
85 int64 iterations() const override;
86 // Number of branch-and-bound nodes. Only available for discrete problems.
87 int64 nodes() const override;
88
89 // Returns the basis status of a row.
90 MPSolver::BasisStatus row_status(int constraint_index) const override;
91 // Returns the basis status of a column.
92 MPSolver::BasisStatus column_status(int variable_index) const override;
93
94 // ----- Misc -----
95 // Query problem type.
96 bool IsContinuous() const override { return true; }
97 bool IsLP() const override { return true; }
98 bool IsMIP() const override { return false; }
99
100 void ExtractNewVariables() override;
101 void ExtractNewConstraints() override;
102 void ExtractObjective() override;
103
104 std::string SolverVersion() const override { return "Clp " CLP_VERSION; }
105
106 void* underlying_solver() override {
107 return reinterpret_cast<void*>(clp_.get());
108 }
109
110 private:
111 // Create dummy variable to be able to create empty constraints.
112 void CreateDummyVariableForEmptyConstraints();
113
114 // Set all parameters in the underlying solver.
115 void SetParameters(const MPSolverParameters& param) override;
116 // Reset to their default value the parameters for which CLP has a
117 // stateful API. To be called after the solve so that the next solve
118 // starts from a clean parameter state.
119 void ResetParameters();
120 // Set each parameter in the underlying solver.
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;
127
128 // Transforms basis status from CLP enum to MPSolver::BasisStatus.
129 MPSolver::BasisStatus TransformCLPBasisStatus(
130 ClpSimplex::Status clp_basis_status) const;
131
132 std::unique_ptr<ClpSimplex> clp_; // TODO(user) : remove pointer.
133 std::unique_ptr<ClpSolve> options_; // For parameter setting.
134};
135
136// ----- Solver -----
137
138// Creates a LP/MIP instance with the specified name and minimization objective.
140 : MPSolverInterface(solver), clp_(new ClpSimplex), options_(new ClpSolve) {
141 clp_->setStrParam(ClpProbName, solver_->name_);
142 clp_->setOptimizationDirection(1);
143}
144
146
148 clp_ = absl::make_unique<ClpSimplex>();
149 clp_->setOptimizationDirection(maximize_ ? -1 : 1);
151}
152
153// ------ Model modifications and extraction -----
154
155namespace {
156// Variable indices are shifted by 1 internally because of the dummy "objective
157// offset" variable (with internal index 0).
158int MPSolverVarIndexToClpVarIndex(int var_index) { return var_index + 1; }
159} // namespace
160
161// Not cached
164 clp_->setOptimizationDirection(maximize ? -1 : 1);
165}
166
167void CLPInterface::SetVariableBounds(int var_index, double lb, double ub) {
169 if (variable_is_extracted(var_index)) {
170 // Not cached if the variable has been extracted
172 clp_->setColumnBounds(MPSolverVarIndexToClpVarIndex(var_index), lb, ub);
173 } else {
175 }
176}
177
178// Ignore as CLP does not solve models with integer variables
179void CLPInterface::SetVariableInteger(int var_index, bool integer) {}
180
181void CLPInterface::SetConstraintBounds(int index, double lb, double ub) {
184 // Not cached if the row has been extracted
186 clp_->setRowBounds(index, lb, ub);
187 } else {
189 }
190}
191
193 const MPVariable* const variable,
194 double new_value, double old_value) {
196 if (constraint_is_extracted(constraint->index()) &&
197 variable_is_extracted(variable->index())) {
198 // The modification of the coefficient for an extracted row and
199 // variable is not cached.
200 DCHECK_LE(constraint->index(), last_constraint_index_);
202 clp_->modifyCoefficient(constraint->index(),
203 MPSolverVarIndexToClpVarIndex(variable->index()),
204 new_value);
205 } else {
206 // The modification of an unextracted row or variable is cached
207 // and handled in ExtractModel.
209 }
210}
211
212// Not cached
215 // Constraint may not have been extracted yet.
216 if (!constraint_is_extracted(constraint->index())) return;
217 for (const auto& entry : constraint->coefficients_) {
218 DCHECK(variable_is_extracted(entry.first->index()));
219 clp_->modifyCoefficient(constraint->index(),
220 MPSolverVarIndexToClpVarIndex(entry.first->index()),
221 0.0);
222 }
223}
224
225// Cached
227 double coefficient) {
229 if (variable_is_extracted(variable->index())) {
230 clp_->setObjectiveCoefficient(
231 MPSolverVarIndexToClpVarIndex(variable->index()), coefficient);
232 } else {
234 }
235}
236
237// Cached
239 // Constant term. Use -offset instead of +offset because CLP does
240 // not follow conventions.
242 clp_->setObjectiveOffset(-offset);
243}
244
245// Clear objective of all its terms.
248 // Clear linear terms
249 for (const auto& entry : solver_->objective_->coefficients_) {
250 const int mpsolver_var_index = entry.first->index();
251 // Variable may have not been extracted yet.
252 if (!variable_is_extracted(mpsolver_var_index)) {
254 } else {
255 clp_->setObjectiveCoefficient(
256 MPSolverVarIndexToClpVarIndex(mpsolver_var_index), 0.0);
257 }
258 }
259 // Clear constant term.
260 clp_->setObjectiveOffset(0.0);
261}
262
265}
266
269}
270
271void CLPInterface::CreateDummyVariableForEmptyConstraints() {
272 clp_->setColumnBounds(kDummyVariableIndex, 0.0, 0.0);
273 clp_->setObjectiveCoefficient(kDummyVariableIndex, 0.0);
274 // Workaround for peculiar signature of setColumnName. Note that we do need
275 // std::string here, and not 'string', which aren't the same as of 2013-12
276 // (this will change later).
277 std::string dummy = "dummy"; // We do need to create this temporary variable.
278 clp_->setColumnName(kDummyVariableIndex, dummy);
279}
280
281// Define new variables and add them to existing constraints.
283 // Define new variables
284 int total_num_vars = solver_->variables_.size();
285 if (total_num_vars > last_variable_index_) {
287 // Faster extraction when nothing has been extracted yet.
288 clp_->resize(0, total_num_vars + 1);
289 CreateDummyVariableForEmptyConstraints();
290 for (int i = 0; i < total_num_vars; ++i) {
291 MPVariable* const var = solver_->variables_[i];
293 if (!var->name().empty()) {
294 std::string name = var->name();
295 clp_->setColumnName(MPSolverVarIndexToClpVarIndex(i), name);
296 }
297 clp_->setColumnBounds(MPSolverVarIndexToClpVarIndex(i), var->lb(),
298 var->ub());
299 }
300 } else {
301 // TODO(user): This could perhaps be made slightly faster by
302 // iterating through old constraints, constructing by hand the
303 // column-major representation of the addition to them and call
304 // clp_->addColumns. But this is good enough for now.
305 // Create new variables.
306 for (int j = last_variable_index_; j < total_num_vars; ++j) {
307 MPVariable* const var = solver_->variables_[j];
310 // The true objective coefficient will be set later in ExtractObjective.
311 double tmp_obj_coef = 0.0;
312 clp_->addColumn(0, nullptr, nullptr, var->lb(), var->ub(),
313 tmp_obj_coef);
314 if (!var->name().empty()) {
315 std::string name = var->name();
316 clp_->setColumnName(MPSolverVarIndexToClpVarIndex(j), name);
317 }
318 }
319 // Add new variables to existing constraints.
320 for (int i = 0; i < last_constraint_index_; i++) {
321 MPConstraint* const ct = solver_->constraints_[i];
322 const int ct_index = ct->index();
323 for (const auto& entry : ct->coefficients_) {
324 const int mpsolver_var_index = entry.first->index();
325 DCHECK(variable_is_extracted(mpsolver_var_index));
326 if (mpsolver_var_index >= last_variable_index_) {
327 clp_->modifyCoefficient(
328 ct_index, MPSolverVarIndexToClpVarIndex(mpsolver_var_index),
329 entry.second);
330 }
331 }
332 }
333 }
334 }
335}
336
337// Define new constraints on old and new variables.
339 int total_num_rows = solver_->constraints_.size();
340 if (last_constraint_index_ < total_num_rows) {
341 // Find the length of the longest row.
342 int max_row_length = 0;
343 for (int i = last_constraint_index_; i < total_num_rows; ++i) {
344 MPConstraint* const ct = solver_->constraints_[i];
346 set_constraint_as_extracted(ct->index(), true);
347 if (ct->coefficients_.size() > max_row_length) {
348 max_row_length = ct->coefficients_.size();
349 }
350 }
351 // Make space for dummy variable.
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;
356 // Add each new constraint.
357 for (int i = last_constraint_index_; i < total_num_rows; ++i) {
358 MPConstraint* const ct = solver_->constraints_[i];
360 int size = ct->coefficients_.size();
361 if (size == 0) {
362 // Add dummy variable to be able to build the constraint.
363 indices[0] = kDummyVariableIndex;
364 coefs[0] = 1.0;
365 size = 1;
366 }
367 int j = 0;
368 for (const auto& entry : ct->coefficients_) {
369 const int mpsolver_var_index = entry.first->index();
370 DCHECK(variable_is_extracted(mpsolver_var_index));
371 indices[j] = MPSolverVarIndexToClpVarIndex(mpsolver_var_index);
372 coefs[j] = entry.second;
373 j++;
374 }
375 build_object.addRow(size, indices.get(), coefs.get(), ct->lb(), ct->ub());
376 }
377 // Add and name the rows.
378 clp_->addRows(build_object);
379 for (int i = last_constraint_index_; i < total_num_rows; ++i) {
380 MPConstraint* const ct = solver_->constraints_[i];
381 if (!ct->name().empty()) {
382 std::string name = ct->name();
383 clp_->setRowName(ct->index(), name);
384 }
385 }
386 }
387}
388
390 // Linear objective: set objective coefficients for all variables
391 // (some might have been modified)
392 for (const auto& entry : solver_->objective_->coefficients_) {
393 clp_->setObjectiveCoefficient(
394 MPSolverVarIndexToClpVarIndex(entry.first->index()), entry.second);
395 }
396
397 // Constant term. Use -offset instead of +offset because CLP does
398 // not follow conventions.
399 clp_->setObjectiveOffset(-solver_->Objective().offset());
400}
401
402// Extracts model and solve the LP/MIP. Returns the status of the search.
404 try {
405 WallTimer timer;
406 timer.Start();
407
410 Reset();
411 }
412
413 // Set log level.
414 CoinMessageHandler message_handler;
415 clp_->passInMessageHandler(&message_handler);
416 if (quiet_) {
417 message_handler.setLogLevel(1, 0);
418 clp_->setLogLevel(0);
419 } else {
420 message_handler.setLogLevel(1, 1);
421 clp_->setLogLevel(1);
422 }
423
424 // Special case if the model is empty since CLP is not able to
425 // handle this special case by itself.
426 if (solver_->variables_.empty() && solver_->constraints_.empty()) {
430 return result_status_;
431 }
432
433 ExtractModel();
434 VLOG(1) << absl::StrFormat("Model built in %.3f seconds.", timer.Get());
435
436 // Time limit.
437 if (solver_->time_limit() != 0) {
438 VLOG(1) << "Setting time limit = " << solver_->time_limit() << " ms.";
439 clp_->setMaximumSeconds(solver_->time_limit_in_secs());
440 } else {
441 clp_->setMaximumSeconds(-1.0);
442 }
443
444 // Start from a fresh set of default parameters and set them to
445 // specified values.
446 options_ = absl::make_unique<ClpSolve>();
447 SetParameters(param);
448
449 // Solve
450 timer.Restart();
451 clp_->initialSolve(*options_);
452 VLOG(1) << absl::StrFormat("Solved in %.3f seconds.", timer.Get());
453
454 // Check the status: optimal, infeasible, etc.
455 int tmp_status = clp_->status();
456 VLOG(1) << "clp result status: " << tmp_status;
457 switch (tmp_status) {
458 case CLP_SIMPLEX_FINISHED:
460 break;
461 case CLP_SIMPLEX_INFEASIBLE:
463 break;
464 case CLP_SIMPLEX_UNBOUNDED:
466 break;
467 case CLP_SIMPLEX_STOPPED:
469 break;
470 default:
472 break;
473 }
474
477 // Get the results
478 objective_value_ = clp_->objectiveValue();
479 VLOG(1) << "objective=" << objective_value_;
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) {
483 MPVariable* const var = solver_->variables_[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;
491 }
492 const double* const dual_values = clp_->getRowPrice();
493 for (int i = 0; i < solver_->constraints_.size(); ++i) {
494 MPConstraint* const ct = solver_->constraints_[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;
499 }
500 }
501
502 ResetParameters();
504 return result_status_;
505 } catch (CoinError& e) {
506 LOG(WARNING) << "Caught exception in Coin LP: " << e.message();
508 return result_status_;
509 }
510}
511
512MPSolver::BasisStatus CLPInterface::TransformCLPBasisStatus(
513 ClpSimplex::Status clp_basis_status) const {
514 switch (clp_basis_status) {
515 case ClpSimplex::isFree:
516 return MPSolver::FREE;
517 case ClpSimplex::basic:
518 return MPSolver::BASIC;
519 case ClpSimplex::atUpperBound:
521 case ClpSimplex::atLowerBound:
523 case ClpSimplex::superBasic:
524 return MPSolver::FREE;
525 case ClpSimplex::isFixed:
527 default:
528 LOG(FATAL) << "Unknown CLP basis status";
529 return MPSolver::FREE;
530 }
531}
532
533// ------ Query statistics on the solution and the solve ------
534
537 return clp_->getIterationCount();
538}
539
541 LOG(DFATAL) << "Number of nodes only available for discrete problems";
543}
544
546 DCHECK_LE(0, constraint_index);
547 DCHECK_GT(last_constraint_index_, constraint_index);
548 const ClpSimplex::Status clp_basis_status =
549 clp_->getRowStatus(constraint_index);
550 return TransformCLPBasisStatus(clp_basis_status);
551}
552
554 DCHECK_LE(0, variable_index);
555 DCHECK_GT(last_variable_index_, variable_index);
556 const ClpSimplex::Status clp_basis_status =
557 clp_->getColumnStatus(MPSolverVarIndexToClpVarIndex(variable_index));
558 return TransformCLPBasisStatus(clp_basis_status);
559}
560
561// ------ Parameters ------
562
563void CLPInterface::SetParameters(const MPSolverParameters& param) {
564 SetCommonParameters(param);
565}
566
567void CLPInterface::ResetParameters() {
568 clp_->setPrimalTolerance(MPSolverParameters::kDefaultPrimalTolerance);
569 clp_->setDualTolerance(MPSolverParameters::kDefaultDualTolerance);
570}
571
572void CLPInterface::SetRelativeMipGap(double value) {
573 LOG(WARNING) << "The relative MIP gap is only available "
574 << "for discrete problems.";
575}
576
577void CLPInterface::SetPrimalTolerance(double value) {
578 clp_->setPrimalTolerance(value);
579}
580
581void CLPInterface::SetDualTolerance(double value) {
582 clp_->setDualTolerance(value);
583}
584
585void CLPInterface::SetPresolveMode(int value) {
586 switch (value) {
588 options_->setPresolveType(ClpSolve::presolveOff);
589 break;
590 }
592 options_->setPresolveType(ClpSolve::presolveOn);
593 break;
594 }
595 default: {
597 }
598 }
599}
600
601void CLPInterface::SetScalingMode(int value) {
603}
604
605void CLPInterface::SetLpAlgorithm(int value) {
606 switch (value) {
608 options_->setSolveType(ClpSolve::useDual);
609 break;
610 }
612 options_->setSolveType(ClpSolve::usePrimal);
613 break;
614 }
616 options_->setSolveType(ClpSolve::useBarrier);
617 break;
618 }
619 default: {
621 value);
622 }
623 }
624}
625
627 return new CLPInterface(solver);
628}
629
630} // namespace operations_research
631#endif // #if defined(USE_CBC) || defined(USE_CLP)
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#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
CLPInterface(MPSolver *const solver)
void SetVariableInteger(int var_index, bool integer) override
void SetObjectiveOffset(double offset) override
std::string SolverVersion() const override
void AddVariable(MPVariable *const var) override
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.
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.
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)
bool constraint_is_extracted(int ct_index) const
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 &param)
This class stores parameter settings for LP and MIP solvers.
@ INCREMENTALITY_OFF
Start solve from scratch.
@ 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.
int index() const
Returns the index of the variable in the MPSolver::variables_.
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
const int WARNING
Definition: log_severity.h:31
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 * BuildCLPInterface(MPSolver *const solver)
int index
Definition: pack.cc:508
int64 coefficient