OR-Tools  8.2
sat_solver_utils.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 
15 
16 #include "absl/memory/memory.h"
17 #include "ortools/glop/parameters.pb.h"
20 
21 namespace operations_research {
22 
23 #define ADD_LP_PREPROCESSOR(name) \
24  names.push_back(#name); \
25  lp_preprocessors.push_back(absl::make_unique<name>(&glop_params));
26 
27 MPSolverResponseStatus ApplyMipPresolveSteps(
28  bool log_info, const glop::GlopParameters& glop_params, MPModelProto* model,
29  std::vector<std::unique_ptr<glop::Preprocessor>>* for_postsolve) {
30  CHECK(model != nullptr);
31 
32  // TODO(user): General constraints are currently not supported.
33  if (!model->general_constraint().empty()) {
34  return MPSolverResponseStatus::MPSOLVER_NOT_SOLVED;
35  }
36 
37  // We need to copy the hint because LinearProgramToMPModelProto() loose it.
38  const bool hint_is_present = model->has_solution_hint();
39  const auto copy_of_hint = model->solution_hint();
40 
41  // TODO(user): Remove this back and forth conversion. We could convert
42  // the LinearProgram directly to a CpModelProto, or we could have a custom
43  // implementation of these presolve steps.
46 
47  // These presolve might change the problem size.
48  //
49  // TODO(user): transform the hint instead of disabling presolve.
50  if (!hint_is_present) {
51  const std::string header =
52  "Running basic LP presolve, initial problem dimensions: ";
53  LOG_IF(INFO, log_info) << header << lp.GetDimensionString();
54  std::vector<std::string> names;
55  std::vector<std::unique_ptr<glop::Preprocessor>> lp_preprocessors;
60 
61  // TODO(user): Usually it is good to run the ImpliedFreePreprocessor before
62  // this one. However this seems to cause problem on atm20-100.mps. Moreover,
63  // for the conversion, it is better to have tight bounds even if the bound
64  // propagator is supposed to undo what this presolve would have done.
66 
67  for (int i = 0; i < lp_preprocessors.size(); ++i) {
68  auto& preprocessor = lp_preprocessors[i];
69  preprocessor->UseInMipContext();
70  const bool need_postsolve = preprocessor->Run(&lp);
71  names[i].resize(header.size(), ' '); // padding.
72  LOG_IF(INFO, log_info) << names[i] << lp.GetDimensionString();
73  const glop::ProblemStatus status = preprocessor->status();
74  if (status != glop::ProblemStatus::INIT) {
77  return MPSolverResponseStatus::MPSOLVER_INFEASIBLE;
78  }
79  return MPSolverResponseStatus::MPSOLVER_NOT_SOLVED;
80  }
81  if (need_postsolve) for_postsolve->push_back(std::move(preprocessor));
82  }
83  }
84 
85  // Finally, we make sure all domains contain zero.
86  if (!hint_is_present) {
87  auto shift_bounds =
88  absl::make_unique<glop::ShiftVariableBoundsPreprocessor>(&glop_params);
89  shift_bounds->UseInMipContext();
90  if (shift_bounds->Run(&lp)) {
91  for_postsolve->push_back(std::move(shift_bounds));
92  }
93  }
94 
96 
97  // Restore the hint, note that none of the presolve steps we run here change
98  // the number of variables in the model.
99  if (hint_is_present) {
100  *model->mutable_solution_hint() = copy_of_hint;
101  }
102 
103  return MPSolverResponseStatus::MPSOLVER_NOT_SOLVED;
104 }
105 
106 #undef ADD_LP_PREPROCESSOR
107 
108 } // namespace operations_research
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define CHECK(condition)
Definition: base/logging.h:495
std::string GetDimensionString() const
Definition: lp_data.cc:424
GRBmodel * model
const int INFO
Definition: log_severity.h:31
void MPModelProtoToLinearProgram(const MPModelProto &input, LinearProgram *output)
Definition: proto_utils.cc:51
void LinearProgramToMPModelProto(const LinearProgram &input, MPModelProto *output)
Definition: proto_utils.cc:20
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
MPSolverResponseStatus ApplyMipPresolveSteps(bool log_info, const glop::GlopParameters &glop_params, MPModelProto *model, std::vector< std::unique_ptr< glop::Preprocessor >> *for_postsolve)
#define ADD_LP_PREPROCESSOR(name)