OR-Tools  8.2
bop_fs.h
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#ifndef OR_TOOLS_BOP_BOP_FS_H_
15#define OR_TOOLS_BOP_BOP_FS_H_
16
17#include <cstdint>
18#include <string>
19
24#include "ortools/base/macros.h"
25#include "ortools/base/random.h"
27#include "ortools/bop/bop_parameters.pb.h"
32#include "ortools/sat/boolean_problem.pb.h"
35
36namespace operations_research {
37namespace bop {
38
39// Tries to find a first solution using SAT and a given assignment preference.
40// This optimizer will never run again once it has found a solution except if
41// the policy is kNotGuided in which case it will be ran again.
43 public:
44 // The different guiding heuristics
45 enum class Policy {
46 kNotGuided, // The default SAT solver.
47 kLpGuided, // Guided by the values of the linear relaxation.
48 kObjectiveGuided, // Guided by the objective coefficient.
49 kUserGuided, // Guided by the problem assignment_preference().
50 };
51 GuidedSatFirstSolutionGenerator(const std::string& name, Policy policy);
53
54 bool ShouldBeRun(const ProblemState& problem_state) const override;
55
56 // Note that if the last call to Optimize() returned CONTINUE and if the
57 // problem didn't change, calling this will resume the solve from its last
58 // position.
59 Status Optimize(const BopParameters& parameters,
60 const ProblemState& problem_state, LearnedInfo* learned_info,
61 TimeLimit* time_limit) override;
62
63 private:
64 BopOptimizerBase::Status SynchronizeIfNeeded(
65 const ProblemState& problem_state);
66
67 const Policy policy_;
68 bool abort_;
69 int64_t state_update_stamp_;
70 std::unique_ptr<sat::SatSolver> sat_solver_;
71};
72
73// This class implements an optimizer that tries various random search
74// strategies, each with a really low conflict limit. It can be used to generate
75// a first solution or to improve an existing one.
76//
77// By opposition to all the other optimizers, this one doesn't return right away
78// when a new solution is found. Instead, it continues to improve it as long as
79// it has time.
80//
81// TODO(user): Coupled with some Local Search it might be used to diversify
82// the solutions. To try.
84 public:
85 BopRandomFirstSolutionGenerator(const std::string& name,
86 const BopParameters& parameters,
87 sat::SatSolver* sat_propagator,
88 MTRandom* random);
90
91 bool ShouldBeRun(const ProblemState& problem_state) const override;
92 Status Optimize(const BopParameters& parameters,
93 const ProblemState& problem_state, LearnedInfo* learned_info,
94 TimeLimit* time_limit) override;
95
96 private:
97 BopOptimizerBase::Status SynchronizeIfNeeded(
98 const ProblemState& problem_state);
99
100 int random_seed_;
101 MTRandom* random_;
102 sat::SatSolver* sat_propagator_;
103};
104
105// This class computes the linear relaxation of the state problem.
106// Optimize() fills the relaxed values (possibly floating values) that can be
107// used by other optimizers as BopSatLpFirstSolutionGenerator for instance,
108// and the lower bound.
110 public:
111 LinearRelaxation(const BopParameters& parameters, const std::string& name);
112 ~LinearRelaxation() override;
113
114 bool ShouldBeRun(const ProblemState& problem_state) const override;
115 Status Optimize(const BopParameters& parameters,
116 const ProblemState& problem_state, LearnedInfo* learned_info,
117 TimeLimit* time_limit) override;
118
119 private:
120 BopOptimizerBase::Status SynchronizeIfNeeded(
121 const ProblemState& problem_state);
122
123 // Runs Glop to solve the current lp_model_.
124 // Updates the time limit and returns the status of the solve.
125 // Note that when the solve is incremental, the preprocessor is deactivated,
126 // and the dual simplex is used.
127 glop::ProblemStatus Solve(bool incremental_solve, TimeLimit* time_limit);
128
129 // Computes and returns a better best bound using strong branching, i.e.
130 // doing a what-if analysis on each variable v: compute the best bound when
131 // v is assigned to true, compute the best bound when v is assigned to false,
132 // and then use those best bounds to improve the overall best bound.
133 // As a side effect, it might fix some variables.
134 double ComputeLowerBoundUsingStrongBranching(LearnedInfo* learned_info,
136
137 // Returns true when the cost is worse than the cost of the current solution.
138 // If they are within the given tolerance, returns false.
139 bool CostIsWorseThanSolution(double scaled_cost, double tolerance) const;
140
141 const BopParameters parameters_;
142 int64_t state_update_stamp_;
143 bool lp_model_loaded_;
144 int num_full_solves_;
145 glop::LinearProgram lp_model_;
146 glop::LPSolver lp_solver_;
147 double scaling_;
148 double offset_;
149 int num_fixed_variables_;
150 bool problem_already_solved_;
151 double scaled_solution_cost_;
152};
153
154} // namespace bop
155} // namespace operations_research
156#endif // OR_TOOLS_BOP_BOP_FS_H_
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
const std::string & name() const
Definition: bop_base.h:49
bool ShouldBeRun(const ProblemState &problem_state) const override
Definition: bop_fs.cc:223
BopRandomFirstSolutionGenerator(const std::string &name, const BopParameters &parameters, sat::SatSolver *sat_propagator, MTRandom *random)
Definition: bop_fs.cc:213
Status Optimize(const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit) override
Definition: bop_fs.cc:228
bool ShouldBeRun(const ProblemState &problem_state) const override
Definition: bop_fs.cc:147
GuidedSatFirstSolutionGenerator(const std::string &name, Policy policy)
Definition: bop_fs.cc:79
Status Optimize(const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit) override
Definition: bop_fs.cc:160
bool ShouldBeRun(const ProblemState &problem_state) const override
Definition: bop_fs.cc:442
Status Optimize(const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit) override
Definition: bop_fs.cc:447
LinearRelaxation(const BopParameters &parameters, const std::string &name)
Definition: bop_fs.cc:343
SatParameters parameters
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Fractional scaled_cost