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"
24#include "ortools/bop/bop_parameters.pb.h"
27
28namespace operations_research {
29namespace {
30
31MPSolver::ResultStatus TranslateProblemStatus(bop::BopSolveStatus status) {
32 switch (status) {
34 return MPSolver::OPTIMAL;
36 return MPSolver::FEASIBLE;
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
217void BopInterface::SetVariableBounds(int index, double lb, double ub) {
218 NonIncrementalChange();
219}
220
222 NonIncrementalChange();
223}
224
225void 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
252void BopInterface::SetObjectiveOffset(double value) { NonIncrementalChange(); }
253
254void BopInterface::ClearObjective() { NonIncrementalChange(); }
255
257 LOG(DFATAL) << "Number of iterations not available";
259}
260
262 LOG(DFATAL) << "Number of nodes not available";
264}
265
267 return row_status_[constraint_index];
268}
269
271 return column_status_[variable_index];
272}
273
274bool BopInterface::IsContinuous() const { return false; }
275bool BopInterface::IsLP() const { return false; }
276bool BopInterface::IsMIP() const { return true; }
277
278std::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
288void* 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
380void 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 ...
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.
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 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)
glop::Fractional objective_value() const
const glop::DenseRow & variable_values() 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