OR-Tools  8.2
subsolver.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// Simple framework for choosing and distributing a solver "sub-tasks" on a set
15// of threads.
16
17#ifndef OR_TOOLS_SAT_SUBSOLVER_H_
18#define OR_TOOLS_SAT_SUBSOLVER_H_
19
20#include <algorithm>
21#include <cmath>
22#include <cstdint>
23#include <functional>
24#include <string>
25#include <vector>
26
28
29#if !defined(__PORTABLE_PLATFORM__)
31#endif // __PORTABLE_PLATFORM__
32
33namespace operations_research {
34namespace sat {
35
36// The API used for distributing work. Each subsolver can generate tasks and
37// synchronize itself with the rest of the world.
38//
39// Note that currently only the main thread interact with subsolvers. Only the
40// tasks generated by GenerateTask() are executed in parallel in a threadpool.
41class SubSolver {
42 public:
43 explicit SubSolver(const std::string& name) : name_(name) {}
44 virtual ~SubSolver() {}
45
46 // Returns true iff GenerateTask() can be called.
47 //
48 // Note(user): In the current design, a SubSolver is never deleted until the
49 // end of the Solve() that created it. But is is okay to always return false
50 // here and release the memory used by the Subsolver internal if there is no
51 // need to call this Subsolver ever again. The overhead of iterating over it
52 // in the main solver loop should be minimal.
53 virtual bool TaskIsAvailable() = 0;
54
55 // Returns a task to run. The task_id is just an ever increasing counter that
56 // correspond to the number of total calls to GenerateTask().
57 //
58 // TODO(user): We could use a more complex selection logic and pass in the
59 // deterministic time limit this subtask should run for. Unclear at this
60 // stage.
61 virtual std::function<void()> GenerateTask(int64 task_id) = 0;
62
63 // Synchronizes with the external world from this SubSolver point of view.
64 // Also incorporate the results of the latest completed tasks if any.
65 //
66 // Note(user): The intended implementation for determinism is that tasks
67 // update asynchronously (and so non-deterministically) global "shared"
68 // classes, but this global state is incorporated by the Subsolver only when
69 // Synchronize() is called.
70 virtual void Synchronize() = 0;
71
72 // Returns the score as updated by the completed tasks before the last
73 // Synchronize() call. Everything else being equal, we prefer to run a
74 // SubSolver with the highest score.
75 //
76 // TODO(user): This is unused for now.
77 double score() const { return score_; }
78
79 // Returns the total deterministic time spend by the completed tasks before
80 // the last Synchronize() call.
81 double deterministic_time() const { return deterministic_time_; }
82
83 // Returns the name of this SubSolver. Used in logs.
84 std::string name() const { return name_; }
85
86 protected:
87 const std::string name_;
88 double score_ = 0.0;
89 double deterministic_time_ = 0.0;
90};
91
92// A simple wrapper to add a synchronization point in the list of subsolvers.
94 public:
95 explicit SynchronizationPoint(std::function<void()> f)
96 : SubSolver(""), f_(std::move(f)) {}
97 bool TaskIsAvailable() final { return false; }
98 std::function<void()> GenerateTask(int64 task_id) final { return nullptr; }
99 void Synchronize() final { f_(); }
100
101 private:
102 std::function<void()> f_;
103};
104
105// Executes the following loop:
106// 1/ Synchronize all in given order.
107// 2/ generate and schedule one task from the current "best" subsolver.
108// 3/ repeat until no extra task can be generated and all tasks are done.
109//
110// The complexity of each selection is in O(num_subsolvers), but that should
111// be okay given that we don't expect more than 100 such subsolvers.
112//
113// Note that it is okay to incorporate "special" subsolver that never produce
114// any tasks. This can be used to synchronize classes used by many subsolvers
115// just once for instance.
117 const std::vector<std::unique_ptr<SubSolver>>& subsolvers, int num_threads);
118
119// Similar to NonDeterministicLoop() except this should result in a
120// deterministic solver provided that all SubSolver respect the Synchronize()
121// contract.
122//
123// Executes the following loop:
124// 1/ Synchronize all in given order.
125// 2/ generate and schedule up to batch_size tasks using an heuristic to select
126// which one to run.
127// 3/ wait for all task to finish.
128// 4/ repeat until no task can be generated in step 2.
130 const std::vector<std::unique_ptr<SubSolver>>& subsolvers, int num_threads,
131 int batch_size);
132
133// Same as above, but specialized implementation for the case num_threads=1.
134// This avoids using a Threadpool altogether. It should have the same behavior
135// than the functions above with num_threads=1 and batch_size=1. Note that an
136// higher batch size will not behave in the same way, even if num_threads=1.
137void SequentialLoop(const std::vector<std::unique_ptr<SubSolver>>& subsolvers);
138
139} // namespace sat
140} // namespace operations_research
141
142#endif // OR_TOOLS_SAT_SUBSOLVER_H_
virtual std::function< void()> GenerateTask(int64 task_id)=0
SubSolver(const std::string &name)
Definition: subsolver.h:43
std::function< void()> GenerateTask(int64 task_id) final
Definition: subsolver.h:98
SynchronizationPoint(std::function< void()> f)
Definition: subsolver.h:95
int64_t int64
void DeterministicLoop(const std::vector< std::unique_ptr< SubSolver > > &subsolvers, int num_threads, int batch_size)
Definition: subsolver.cc:84
void SequentialLoop(const std::vector< std::unique_ptr< SubSolver > > &subsolvers)
Definition: subsolver.cc:54
void NonDeterministicLoop(const std::vector< std::unique_ptr< SubSolver > > &subsolvers, int num_threads)
Definition: subsolver.cc:116
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
STL namespace.