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"
22#include "ortools/glop/parameters.pb.h"
29
30namespace operations_research {
31
32namespace {} // 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
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
199void GLOPInterface::SetVariableBounds(int index, double lb, double ub) {
200 NonIncrementalChange();
201}
202
204 LOG(WARNING) << "Glop doesn't deal with integer variables.";
205}
206
207void 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
234void GLOPInterface::SetObjectiveOffset(double value) { NonIncrementalChange(); }
235
236void GLOPInterface::ClearObjective() { NonIncrementalChange(); }
237
239 return lp_solver_.GetNumberOfSimplexIterations();
240}
241
243 LOG(DFATAL) << "Number of nodes only available for discrete problems";
245}
246
248 return row_status_[constraint_index];
249}
250
252 return column_status_[variable_index];
253}
254
255bool GLOPInterface::IsContinuous() const { return true; }
256
257bool GLOPInterface::IsLP() const { return true; }
258
259bool GLOPInterface::IsMIP() const { return false; }
260
261std::string GLOPInterface::SolverVersion() const {
262 // TODO(user): Decide how to version glop. Add a GetVersion() to LPSolver.
263 return "Glop-0.0";
264}
265
266void* 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.
416 lp_solver_.SetParameters(parameters_);
417 return true;
418 }
419 return false;
420}
421
422void 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 ...
ResultStatus
The status of solving the problem.
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)
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 DenseColumn & dual_values() const
Definition: lp_solver.h:112
const VariableStatusRow & variable_statuses() const
Definition: lp_solver.h:102
const ConstraintStatusColumn & constraint_statuses() const
Definition: lp_solver.h:116
Fractional GetObjectiveValue() const
Definition: lp_solver.cc:476
const DenseRow & variable_values() const
Definition: lp_solver.h:100
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...
bool ProtobufTextFormatMergeFromString(const std::string &proto_text_string, ProtoType *proto)
MPSolver::BasisStatus GlopToMPSolverVariableStatus(glop::VariableStatus s)
Definition: glop_utils.cc:57
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