OR-Tools  8.2
glop_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 "ortools/base/hash.h"
20 #include "ortools/base/logging.h"
21 #include "ortools/glop/lp_solver.h"
22 #include "ortools/glop/parameters.pb.h"
29 
30 namespace operations_research {
31 
32 namespace {} // Anonymous namespace
33 
35  public:
36  explicit GLOPInterface(MPSolver* const solver);
37  ~GLOPInterface() override;
38 
39  // ----- Solve -----
40  MPSolver::ResultStatus Solve(const MPSolverParameters& param) override;
41  bool InterruptSolve() override;
42 
43  // ----- Model modifications and extraction -----
44  void Reset() override;
45  void SetOptimizationDirection(bool maximize) override;
46  void SetVariableBounds(int index, double lb, double ub) override;
47  void SetVariableInteger(int index, bool integer) override;
48  void SetConstraintBounds(int index, double lb, double ub) override;
49  void AddRowConstraint(MPConstraint* const ct) override;
50  void AddVariable(MPVariable* const var) override;
51  void SetCoefficient(MPConstraint* const constraint,
52  const MPVariable* const variable, double new_value,
53  double old_value) override;
54  void ClearConstraint(MPConstraint* const constraint) override;
55  void SetObjectiveCoefficient(const MPVariable* const variable,
56  double coefficient) override;
57  void SetObjectiveOffset(double value) override;
58  void ClearObjective() override;
59 
60  // ------ Query statistics on the solution and the solve ------
61  int64 iterations() const override;
62  int64 nodes() const override;
63  MPSolver::BasisStatus row_status(int constraint_index) const override;
64  MPSolver::BasisStatus column_status(int variable_index) const override;
65 
66  // ----- Misc -----
67  bool IsContinuous() const override;
68  bool IsLP() const override;
69  bool IsMIP() const override;
70 
71  std::string SolverVersion() const override;
72  void* underlying_solver() override;
73 
74  void ExtractNewVariables() override;
75  void ExtractNewConstraints() override;
76  void ExtractObjective() override;
77 
78  void SetStartingLpBasis(
79  const std::vector<MPSolver::BasisStatus>& variable_statuses,
80  const std::vector<MPSolver::BasisStatus>& constraint_statuses) override;
81 
82  void SetParameters(const MPSolverParameters& param) override;
83  void SetRelativeMipGap(double value) override;
84  void SetPrimalTolerance(double value) override;
85  void SetDualTolerance(double value) override;
86  void SetPresolveMode(int value) override;
87  void SetScalingMode(int value) override;
88  void SetLpAlgorithm(int value) override;
90  const std::string& parameters) override;
91 
92  private:
93  void NonIncrementalChange();
94 
95  glop::LinearProgram linear_program_;
96  glop::LPSolver lp_solver_;
97  std::vector<MPSolver::BasisStatus> column_status_;
98  std::vector<MPSolver::BasisStatus> row_status_;
99  glop::GlopParameters parameters_;
100  std::atomic<bool> interrupt_solver_;
101 };
102 
104  : MPSolverInterface(solver),
105  linear_program_(),
106  lp_solver_(),
107  column_status_(),
108  row_status_(),
109  parameters_(),
110  interrupt_solver_(false) {}
111 
113 
115  // Re-extract the problem from scratch. We don't support modifying the
116  // LinearProgram in sync with changes done in the MPSolver.
118  linear_program_.Clear();
119  interrupt_solver_ = false;
120  ExtractModel();
121  SetParameters(param);
122 
123  linear_program_.SetMaximizationProblem(maximize_);
124  linear_program_.CleanUp();
125 
126  // Time limit.
127  if (solver_->time_limit()) {
128  VLOG(1) << "Setting time limit = " << solver_->time_limit() << " ms.";
129  parameters_.set_max_time_in_seconds(
130  static_cast<double>(solver_->time_limit()) / 1000.0);
131  }
132 
134  solver_->solver_specific_parameter_string_);
135  lp_solver_.SetParameters(parameters_);
136  std::unique_ptr<TimeLimit> time_limit =
137  TimeLimit::FromParameters(parameters_);
138  time_limit->RegisterExternalBooleanAsLimit(&interrupt_solver_);
139  const glop::ProblemStatus status =
140  lp_solver_.SolveWithTimeLimit(linear_program_, time_limit.get());
141 
142  // The solution must be marked as synchronized even when no solution exists.
145  objective_value_ = lp_solver_.GetObjectiveValue();
146 
147  const size_t num_vars = solver_->variables_.size();
148  column_status_.resize(num_vars, MPSolver::FREE);
149  for (int var_id = 0; var_id < num_vars; ++var_id) {
150  MPVariable* const var = solver_->variables_[var_id];
151  const glop::ColIndex lp_solver_var_id(var->index());
152 
153  const glop::Fractional solution_value =
154  lp_solver_.variable_values()[lp_solver_var_id];
155  var->set_solution_value(static_cast<double>(solution_value));
156 
157  const glop::Fractional reduced_cost =
158  lp_solver_.reduced_costs()[lp_solver_var_id];
159  var->set_reduced_cost(static_cast<double>(reduced_cost));
160 
161  const glop::VariableStatus variable_status =
162  lp_solver_.variable_statuses()[lp_solver_var_id];
163  column_status_.at(var_id) = GlopToMPSolverVariableStatus(variable_status);
164  }
165 
166  const size_t num_constraints = solver_->constraints_.size();
167  row_status_.resize(num_constraints, MPSolver::FREE);
168  for (int ct_id = 0; ct_id < num_constraints; ++ct_id) {
169  MPConstraint* const ct = solver_->constraints_[ct_id];
170  const glop::RowIndex lp_solver_ct_id(ct->index());
171 
172  const glop::Fractional dual_value =
173  lp_solver_.dual_values()[lp_solver_ct_id];
174  ct->set_dual_value(static_cast<double>(dual_value));
175 
176  const glop::ConstraintStatus constraint_status =
177  lp_solver_.constraint_statuses()[lp_solver_ct_id];
178  row_status_.at(ct_id) = GlopToMPSolverConstraintStatus(constraint_status);
179  }
180 
181  return result_status_;
182 }
183 
185  interrupt_solver_ = true;
186  return true;
187 }
188 
190  // Ignore any incremental info for the next solve. Note that the parameters
191  // will not be reset as we re-read them on each Solve().
192  lp_solver_.Clear();
193 }
194 
196  NonIncrementalChange();
197 }
198 
199 void GLOPInterface::SetVariableBounds(int index, double lb, double ub) {
200  NonIncrementalChange();
201 }
202 
203 void GLOPInterface::SetVariableInteger(int index, bool integer) {
204  LOG(WARNING) << "Glop doesn't deal with integer variables.";
205 }
206 
207 void GLOPInterface::SetConstraintBounds(int index, double lb, double ub) {
208  NonIncrementalChange();
209 }
210 
212  NonIncrementalChange();
213 }
214 
216  NonIncrementalChange();
217 }
218 
220  const MPVariable* const variable,
221  double new_value, double old_value) {
222  NonIncrementalChange();
223 }
224 
226  NonIncrementalChange();
227 }
228 
230  double coefficient) {
231  NonIncrementalChange();
232 }
233 
234 void GLOPInterface::SetObjectiveOffset(double value) { NonIncrementalChange(); }
235 
236 void GLOPInterface::ClearObjective() { NonIncrementalChange(); }
237 
239  return lp_solver_.GetNumberOfSimplexIterations();
240 }
241 
243  LOG(DFATAL) << "Number of nodes only available for discrete problems";
244  return kUnknownNumberOfNodes;
245 }
246 
248  return row_status_[constraint_index];
249 }
250 
252  return column_status_[variable_index];
253 }
254 
255 bool GLOPInterface::IsContinuous() const { return true; }
256 
257 bool GLOPInterface::IsLP() const { return true; }
258 
259 bool GLOPInterface::IsMIP() const { return false; }
260 
261 std::string GLOPInterface::SolverVersion() const {
262  // TODO(user): Decide how to version glop. Add a GetVersion() to LPSolver.
263  return "Glop-0.0";
264 }
265 
266 void* GLOPInterface::underlying_solver() { return &lp_solver_; }
267 
271 
272  const glop::ColIndex num_cols(solver_->variables_.size());
273  for (glop::ColIndex col(last_variable_index_); col < num_cols; ++col) {
274  MPVariable* const var = solver_->variables_[col.value()];
275  const glop::ColIndex new_col = linear_program_.CreateNewVariable();
276  DCHECK_EQ(new_col, col);
277  set_variable_as_extracted(col.value(), true);
278  linear_program_.SetVariableBounds(col, var->lb(), var->ub());
279  }
280 }
281 
284 
285  const glop::RowIndex num_rows(solver_->constraints_.size());
286  for (glop::RowIndex row(0); row < num_rows; ++row) {
287  MPConstraint* const ct = solver_->constraints_[row.value()];
288  set_constraint_as_extracted(row.value(), true);
289 
290  const double lb = ct->lb();
291  const double ub = ct->ub();
292  const glop::RowIndex new_row = linear_program_.CreateNewConstraint();
293  DCHECK_EQ(new_row, row);
294  linear_program_.SetConstraintBounds(row, lb, ub);
295 
296  for (const auto& entry : ct->coefficients_) {
297  const int var_index = entry.first->index();
298  DCHECK(variable_is_extracted(var_index));
299  const glop::ColIndex col(var_index);
300  const double coeff = entry.second;
301  linear_program_.SetCoefficient(row, col, coeff);
302  }
303  }
304 }
305 
307  linear_program_.SetObjectiveOffset(solver_->Objective().offset());
308  for (const auto& entry : solver_->objective_->coefficients_) {
309  const int var_index = entry.first->index();
310  const glop::ColIndex col(var_index);
311  const double coeff = entry.second;
312  linear_program_.SetObjectiveCoefficient(col, coeff);
313  }
314 }
315 
317  const std::vector<MPSolver::BasisStatus>& variable_statuses,
318  const std::vector<MPSolver::BasisStatus>& constraint_statuses) {
319  glop::VariableStatusRow glop_variable_statuses;
320  glop::ConstraintStatusColumn glop_constraint_statuses;
321  for (const MPSolver::BasisStatus& status : variable_statuses) {
322  glop_variable_statuses.push_back(MPSolverToGlopVariableStatus(status));
323  }
324  for (const MPSolver::BasisStatus& status : constraint_statuses) {
325  glop_constraint_statuses.push_back(MPSolverToGlopConstraintStatus(status));
326  }
327  lp_solver_.SetInitialBasis(glop_variable_statuses, glop_constraint_statuses);
328 }
329 
331  parameters_.Clear();
332  parameters_.set_log_search_progress(!quiet_);
333  SetCommonParameters(param);
335 }
336 
340  value);
341  }
342 }
343 
345  // TODO(user): Modify parameters_ with the correct value.
346  // The problem is that this is set by default by the wrapper to 1e-7 and for
347  // now we want to use higher default tolerances in Glop.
350  value);
351  }
352 }
353 
355  // TODO(user): Modify parameters_ with the correct value.
356  // The problem is that this is set by default by the wrapper to 1e-7 and for
357  // now we want to use higher default tolerances in Glop.
360  }
361 }
362 
364  switch (value) {
366  parameters_.set_use_preprocessing(false);
367  break;
369  parameters_.set_use_preprocessing(true);
370  break;
371  default:
374  }
375  }
376 }
377 
379  switch (value) {
381  parameters_.set_use_scaling(false);
382  break;
384  parameters_.set_use_scaling(true);
385  break;
386  default:
389  }
390  }
391 }
392 
394  switch (value) {
396  parameters_.set_use_dual_simplex(true);
397  break;
399  parameters_.set_use_dual_simplex(false);
400  break;
401  default:
404  value);
405  }
406  }
407 }
408 
410  const std::string& parameters) {
411  // NOTE(user): Android build uses protocol buffers in lite mode, and
412  // parsing data from text format is not supported there. To allow solver
413  // specific parameters from string on Android, we first need to switch to
414  // non-lite version of protocol buffers.
415  if (ProtobufTextFormatMergeFromString(parameters, &parameters_)) {
416  lp_solver_.SetParameters(parameters_);
417  return true;
418  }
419  return false;
420 }
421 
422 void GLOPInterface::NonIncrementalChange() {
423  // The current implementation is not incremental.
425 }
426 
427 // Register GLOP in the global linear solver factory.
429  return new GLOPInterface(solver);
430 }
431 
432 } // 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
void push_back(const value_type &x)
void SetScalingMode(int value) override
void SetDualTolerance(double value) override
void AddRowConstraint(MPConstraint *const ct) override
void SetLpAlgorithm(int value) 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
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
GLOPInterface(MPSolver *const solver)
void SetOptimizationDirection(bool maximize) override
MPSolver::BasisStatus column_status(int variable_index) const override
int64 iterations() const override
void SetStartingLpBasis(const std::vector< MPSolver::BasisStatus > &variable_statuses, const std::vector< MPSolver::BasisStatus > &constraint_statuses) 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.
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)
void set_constraint_as_extracted(int ct_index, bool extracted)
bool variable_is_extracted(int var_index) const
void SetDoubleParamToUnsupportedValue(MPSolverParameters::DoubleParam param, double value)
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.
@ DUAL_TOLERANCE
Advanced usage: tolerance for dual feasibility of basic solutions.
@ PRIMAL_TOLERANCE
Advanced usage: tolerance for primal feasibility of basic solutions.
@ RELATIVE_MIP_GAP
Limit for relative MIP gap.
@ LP_ALGORITHM
Algorithm to solve linear programs.
@ SCALING
Advanced usage: enable or disable matrix scaling.
@ PRESOLVE
Advanced usage: presolve mode.
int GetIntegerParam(MPSolverParameters::IntegerParam param) const
Returns the value of an integer parameter.
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
void SetInitialBasis(const VariableStatusRow &variable_statuses, const ConstraintStatusColumn &constraint_statuses)
Definition: lp_solver.cc:230
const ConstraintStatusColumn & constraint_statuses() const
Definition: lp_solver.h:116
const VariableStatusRow & variable_statuses() const
Definition: lp_solver.h:102
const DenseColumn & dual_values() const
Definition: lp_solver.h:112
const DenseRow & variable_values() const
Definition: lp_solver.h:100
Fractional GetObjectiveValue() const
Definition: lp_solver.cc:476
const DenseRow & reduced_costs() const
Definition: lp_solver.h:101
ABSL_MUST_USE_RESULT ProblemStatus SolveWithTimeLimit(const LinearProgram &lp, TimeLimit *time_limit)
Definition: lp_solver.cc:127
void SetParameters(const GlopParameters &parameters)
Definition: lp_solver.cc:113
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 SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
void SetMaximizationProblem(bool maximize)
Definition: lp_data.cc:342
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...
MPSolver::BasisStatus GlopToMPSolverVariableStatus(glop::VariableStatus s)
Definition: glop_utils.cc:57
bool ProtobufTextFormatMergeFromString(const std::string &proto_text_string, ProtoType *proto)
MPSolver::BasisStatus GlopToMPSolverConstraintStatus(glop::ConstraintStatus s)
Definition: glop_utils.cc:91
MPSolver::ResultStatus GlopToMPSolverResultStatus(glop::ProblemStatus s)
Definition: glop_utils.cc:18
glop::VariableStatus MPSolverToGlopVariableStatus(MPSolver::BasisStatus s)
Definition: glop_utils.cc:74
MPSolverInterface * BuildGLOPInterface(MPSolver *const solver)
glop::ConstraintStatus MPSolverToGlopConstraintStatus(MPSolver::BasisStatus s)
Definition: glop_utils.cc:108
int index
Definition: pack.cc:508
int64 coefficient