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
21namespace 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
27MPSolverResponseStatus 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)