OR-Tools  8.2
bop_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 #include <atomic>
15 #include <string>
16 #include <vector>
17 
18 #include "google/protobuf/text_format.h"
20 #include "ortools/base/file.h"
21 #include "ortools/base/hash.h"
23 #include "ortools/base/logging.h"
24 #include "ortools/bop/bop_parameters.pb.h"
27 
28 namespace operations_research {
29 namespace {
30 
31 MPSolver::ResultStatus TranslateProblemStatus(bop::BopSolveStatus status) {
32  switch (status) {
34  return MPSolver::OPTIMAL;
36  return MPSolver::FEASIBLE;
38  return MPSolver::NOT_SOLVED;
40  return MPSolver::INFEASIBLE;
42  return MPSolver::ABNORMAL;
43  }
44  LOG(DFATAL) << "Invalid bop::BopSolveStatus";
45  return MPSolver::ABNORMAL;
46 }
47 
48 } // Anonymous namespace
49 
51  public:
52  explicit BopInterface(MPSolver* const solver);
53  ~BopInterface() override;
54 
55  // ----- Solve -----
56  MPSolver::ResultStatus Solve(const MPSolverParameters& param) override;
57 
58  // ----- Model modifications and extraction -----
59  void Reset() override;
60  void SetOptimizationDirection(bool maximize) override;
61  void SetVariableBounds(int index, double lb, double ub) override;
62  void SetVariableInteger(int index, bool integer) override;
63  void SetConstraintBounds(int index, double lb, double ub) override;
64  void AddRowConstraint(MPConstraint* const ct) override;
65  void AddVariable(MPVariable* const var) override;
66  void SetCoefficient(MPConstraint* const constraint,
67  const MPVariable* const variable, double new_value,
68  double old_value) override;
69  void ClearConstraint(MPConstraint* const constraint) override;
70  void SetObjectiveCoefficient(const MPVariable* const variable,
71  double coefficient) override;
72  void SetObjectiveOffset(double value) override;
73  void ClearObjective() override;
74 
75  // ------ Query statistics on the solution and the solve ------
76  int64 iterations() const override;
77  int64 nodes() const override;
78  MPSolver::BasisStatus row_status(int constraint_index) const override;
79  MPSolver::BasisStatus column_status(int variable_index) const override;
80 
81  // ----- Misc -----
82  bool IsContinuous() const override;
83  bool IsLP() const override;
84  bool IsMIP() const override;
85 
86  std::string SolverVersion() const override;
87  bool InterruptSolve() override;
88  void* underlying_solver() override;
89 
90  void ExtractNewVariables() override;
91  void ExtractNewConstraints() override;
92  void ExtractObjective() override;
93 
94  void SetParameters(const MPSolverParameters& param) override;
95  void SetRelativeMipGap(double value) override;
96  void SetPrimalTolerance(double value) override;
97  void SetDualTolerance(double value) override;
98  void SetPresolveMode(int value) override;
99  void SetScalingMode(int value) override;
100  void SetLpAlgorithm(int value) override;
102  const std::string& parameters) override;
103 
104  private:
105  void NonIncrementalChange();
106 
107  glop::LinearProgram linear_program_;
108  bop::IntegralSolver bop_solver_;
109  std::vector<MPSolver::BasisStatus> column_status_;
110  std::vector<MPSolver::BasisStatus> row_status_;
111  bop::BopParameters parameters_;
112  std::atomic<bool> interrupt_solver_;
113 };
114 
116  : MPSolverInterface(solver),
117  linear_program_(),
118  bop_solver_(),
119  column_status_(),
120  row_status_(),
121  parameters_(),
122  interrupt_solver_(false) {}
123 
125 
127  // Check whenever the solve has already been stopped by the user.
128  if (interrupt_solver_) {
129  Reset();
130  // linear_solver.cc as DCHECK_EQ that interface_->result_status_ is the same
131  // as the status returned by interface_->Solve().
133  return result_status_;
134  }
135 
136  // Reset extraction as this interface is not incremental yet.
137  Reset();
138  ExtractModel();
139  SetParameters(param);
140 
141  linear_program_.SetMaximizationProblem(maximize_);
142  linear_program_.CleanUp();
143 
144  // Time limit.
145  if (solver_->time_limit()) {
146  VLOG(1) << "Setting time limit = " << solver_->time_limit() << " ms.";
147  parameters_.set_max_time_in_seconds(
148  static_cast<double>(solver_->time_limit()) / 1000.0);
149  }
150  parameters_.set_log_search_progress(!quiet());
151 
152  glop::DenseRow initial_solution;
153  if (!solver_->solution_hint_.empty()) {
154  const int num_vars = solver_->variables_.size();
155  if (solver_->solution_hint_.size() != num_vars) {
156  LOG(WARNING) << "Bop currently doesn't handle partial solution hints. "
157  << "Filling the missing positions with zeros...";
158  }
159  initial_solution.assign(glop::ColIndex(num_vars), glop::Fractional(0.0));
160  for (const std::pair<const MPVariable*, double>& p :
161  solver_->solution_hint_) {
162  initial_solution[glop::ColIndex(p.first->index())] =
163  glop::Fractional(p.second);
164  }
165  }
166 
168  solver_->solver_specific_parameter_string_);
169  bop_solver_.SetParameters(parameters_);
170  std::unique_ptr<TimeLimit> time_limit =
171  TimeLimit::FromParameters(parameters_);
172  time_limit->RegisterExternalBooleanAsLimit(&interrupt_solver_);
173  const bop::BopSolveStatus status =
174  initial_solution.empty()
175  ? bop_solver_.SolveWithTimeLimit(linear_program_, time_limit.get())
176  : bop_solver_.SolveWithTimeLimit(linear_program_, initial_solution,
177  time_limit.get());
178 
179  // The solution must be marked as synchronized even when no solution exists.
181  result_status_ = TranslateProblemStatus(status);
184  // Get the results.
185  objective_value_ = bop_solver_.objective_value();
186  best_objective_bound_ = bop_solver_.best_bound();
187 
188  // TODO(user): Implement the column status.
189  const size_t num_vars = solver_->variables_.size();
190  column_status_.resize(num_vars, MPSolver::FREE);
191  for (int var_id = 0; var_id < num_vars; ++var_id) {
192  MPVariable* const var = solver_->variables_[var_id];
193  const glop::ColIndex lp_solver_var_id(var->index());
194  const glop::Fractional solution_value =
195  bop_solver_.variable_values()[lp_solver_var_id];
196  var->set_solution_value(static_cast<double>(solution_value));
197  }
198 
199  // TODO(user): Implement the row status.
200  const size_t num_constraints = solver_->constraints_.size();
201  row_status_.resize(num_constraints, MPSolver::FREE);
202  }
203 
204  return result_status_;
205 }
206 
209  linear_program_.Clear();
210  interrupt_solver_ = false;
211 }
212 
214  NonIncrementalChange();
215 }
216 
217 void BopInterface::SetVariableBounds(int index, double lb, double ub) {
218  NonIncrementalChange();
219 }
220 
221 void BopInterface::SetVariableInteger(int index, bool integer) {
222  NonIncrementalChange();
223 }
224 
225 void BopInterface::SetConstraintBounds(int index, double lb, double ub) {
226  NonIncrementalChange();
227 }
228 
230  NonIncrementalChange();
231 }
232 
234  NonIncrementalChange();
235 }
236 
238  const MPVariable* const variable,
239  double new_value, double old_value) {
240  NonIncrementalChange();
241 }
242 
244  NonIncrementalChange();
245 }
246 
248  double coefficient) {
249  NonIncrementalChange();
250 }
251 
252 void BopInterface::SetObjectiveOffset(double value) { NonIncrementalChange(); }
253 
254 void BopInterface::ClearObjective() { NonIncrementalChange(); }
255 
257  LOG(DFATAL) << "Number of iterations not available";
259 }
260 
262  LOG(DFATAL) << "Number of nodes not available";
263  return kUnknownNumberOfNodes;
264 }
265 
266 MPSolver::BasisStatus BopInterface::row_status(int constraint_index) const {
267  return row_status_[constraint_index];
268 }
269 
271  return column_status_[variable_index];
272 }
273 
274 bool BopInterface::IsContinuous() const { return false; }
275 bool BopInterface::IsLP() const { return false; }
276 bool BopInterface::IsMIP() const { return true; }
277 
278 std::string BopInterface::SolverVersion() const {
279  // TODO(user): Decide how to version bop.
280  return "Bop-0.0";
281 }
282 
284  interrupt_solver_ = true;
285  return true;
286 }
287 
288 void* BopInterface::underlying_solver() { return &bop_solver_; }
289 
290 // TODO(user): remove duplication with GlopInterface.
294 
295  const glop::ColIndex num_cols(solver_->variables_.size());
296  for (glop::ColIndex col(last_variable_index_); col < num_cols; ++col) {
297  MPVariable* const var = solver_->variables_[col.value()];
298  const glop::ColIndex new_col = linear_program_.CreateNewVariable();
299  DCHECK_EQ(new_col, col);
300  set_variable_as_extracted(col.value(), true);
301  linear_program_.SetVariableBounds(col, var->lb(), var->ub());
302  if (var->integer()) {
303  linear_program_.SetVariableType(
305  }
306  }
307 }
308 
309 // TODO(user): remove duplication with GlopInterface.
312 
313  const glop::RowIndex num_rows(solver_->constraints_.size());
314  for (glop::RowIndex row(0); row < num_rows; ++row) {
315  MPConstraint* const ct = solver_->constraints_[row.value()];
316  set_constraint_as_extracted(row.value(), true);
317 
318  const double lb = ct->lb();
319  const double ub = ct->ub();
320  const glop::RowIndex new_row = linear_program_.CreateNewConstraint();
321  DCHECK_EQ(new_row, row);
322  linear_program_.SetConstraintBounds(row, lb, ub);
323 
324  for (const auto& entry : ct->coefficients_) {
325  const int var_index = entry.first->index();
326  DCHECK(variable_is_extracted(var_index));
327  const glop::ColIndex col(var_index);
328  const double coeff = entry.second;
329  linear_program_.SetCoefficient(row, col, coeff);
330  }
331  }
332 }
333 
334 // TODO(user): remove duplication with GlopInterface.
336  linear_program_.SetObjectiveOffset(solver_->Objective().offset());
337  for (const auto& entry : solver_->objective_->coefficients_) {
338  const int var_index = entry.first->index();
339  const glop::ColIndex col(var_index);
340  const double coeff = entry.second;
341  linear_program_.SetObjectiveCoefficient(col, coeff);
342  }
343 }
344 
346  parameters_.Clear();
347  SetCommonParameters(param);
348 }
349 
350 // All these have no effect.
356 
358  switch (value) {
360  // TODO(user): add this to BopParameters.
361  break;
363  // TODO(user): add this to BopParameters.
364  break;
365  default:
368  }
369  }
370 }
371 
373  const std::string& parameters) {
374  const bool ok =
375  google::protobuf::TextFormat::MergeFromString(parameters, &parameters_);
376  bop_solver_.SetParameters(parameters_);
377  return ok;
378 }
379 
380 void BopInterface::NonIncrementalChange() {
381  // The current implementation is not incremental.
383 }
384 
385 // Register BOP in the global linear solver factory.
387  return new BopInterface(solver);
388 }
389 
390 } // namespace operations_research
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
bool empty() const
void SetScalingMode(int value) override
void SetDualTolerance(double value) override
void AddRowConstraint(MPConstraint *const ct) override
void SetLpAlgorithm(int value) override
int64 nodes() const override
bool IsContinuous() const override
MPSolver::ResultStatus Solve(const MPSolverParameters &param) override
void SetPrimalTolerance(double value) override
void ClearConstraint(MPConstraint *const constraint) override
bool SetSolverSpecificParametersAsString(const std::string &parameters) 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 SetObjectiveOffset(double value) override
void SetVariableInteger(int index, bool integer) override
void SetParameters(const MPSolverParameters &param) override
BopInterface(MPSolver *const solver)
std::string SolverVersion() const override
void SetRelativeMipGap(double value) override
void SetConstraintBounds(int index, double lb, double ub) override
void SetPresolveMode(int value) override
void SetVariableBounds(int index, double lb, double ub) override
void AddVariable(MPVariable *const var) 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 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 ...
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.
@ ABNORMAL
abnormal, i.e., error of some kind.
bool SetSolverSpecificParametersAsString(const std::string &parameters)
Advanced usage: pass solver specific parameters in text format.
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 variable_is_extracted(int var_index) const
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.
@ PRESOLVE
Advanced usage: presolve mode.
The class for variables of a Mathematical Programming (MP) model.
static std::unique_ptr< TimeLimit > FromParameters(const Parameters &parameters)
Creates a time limit object initialized from an object that provides methods max_time_in_seconds() an...
Definition: time_limit.h:159
ABSL_MUST_USE_RESULT BopSolveStatus SolveWithTimeLimit(const glop::LinearProgram &linear_problem, TimeLimit *time_limit)
const glop::DenseRow & variable_values() const
glop::Fractional objective_value() const
void SetParameters(const BopParameters &parameters)
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:248
void SetObjectiveOffset(Fractional objective_offset)
Definition: lp_data.cc:330
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Definition: lp_data.cc:316
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:308
void SetVariableType(ColIndex col, VariableType type)
Definition: lp_data.cc:235
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
void SetMaximizationProblem(bool maximize)
Definition: lp_data.cc:342
void assign(IntType size, const T &v)
Definition: lp_types.h:274
SatParameters parameters
SharedTimeLimit * time_limit
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
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
MPSolverInterface * BuildBopInterface(MPSolver *const solver)
int index
Definition: pack.cc:508
int64 coefficient