OR-Tools  8.2
var_domination.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_SAT_VAR_DOMINATION_H_
15#define OR_TOOLS_SAT_VAR_DOMINATION_H_
16
20#include "ortools/sat/integer.h"
22
23namespace operations_research {
24namespace sat {
25
26// A variable X is say to dominate a variable Y if, from any feasible solution,
27// doing X++ and Y-- is also feasible (modulo the domain of X and Y) and has the
28// same or a better objective value.
29//
30// Note that we also look for dominance between the negation of the variables.
31// So we detect all (X++, Y++), (X--, Y--), (X++, Y--) and (X--, Y++) cases.
32// We reuse both ref / Negated(ref) and translate that to IntegerVariable for
33// indexing vectors.
34//
35// Once detected, dominance relation can lead to more propagation. Note however,
36// that we will loose feasible solution that are dominated by better solutions.
37// In particular, in a linear constraint sum coeff * Xi <= rhs with positive
38// coeff, if an X is dominated by a set of other variable in the constraint,
39// then its upper bound can be propagated assuming the dominating variables are
40// at their upper bound. This can in many case result in X being fixed to its
41// lower bound.
42//
43// TODO(user): We have a lot of benchmarks and tests that shows that we don't
44// report wrong relations, but we lack unit test that make sure we don't miss
45// any. Try to improve the situation.
47 public:
49
50 // This is the translation used from "ref" to IntegerVariable. The API
51 // understand the cp_mode.proto ref, but internally we only store
52 // IntegerVariable.
53 static IntegerVariable RefToIntegerVariable(int ref) {
54 return RefIsPositive(ref) ? IntegerVariable(2 * ref)
55 : IntegerVariable(2 * NegatedRef(ref) + 1);
56 }
57 static int IntegerVariableToRef(IntegerVariable var) {
58 return VariableIsPositive(var) ? var.value() / 2
59 : NegatedRef(var.value() / 2);
60 }
61
62 // Reset the class to a clean state.
63 // At the beginning, we assume that there is no constraint.
64 void Reset(int num_variables);
65
66 // These functions are used to encode all of our constraints.
67 // The algorithm work in two passes, so one should do:
68 // - 1/ Convert all problem constraints to one or more calls
69 // - 2/ Call EndFirstPhase()
70 // - 3/ Redo 1. Only the one sided constraint need to be processed again. But
71 // calling the others will just do nothing, so it is fine too.
72 // - 4/ Call EndSecondPhase()
73 //
74 // The names are pretty self-explanatory. A few linear constraint ex:
75 // - To encode terms = cte, one should call ActivityShouldNotChange()
76 // - To encode terms >= cte, one should call ActivityShouldNotDecrease()
77 // - To encode terms <= cte, one should call ActivityShouldNotIncrease()
78 //
79 // The coeffs vector can be left empty, in which case all variable are assumed
80 // to have the same coefficients. CanOnlyDominateEachOther() is basically the
81 // same as ActivityShouldNotChange() without any coefficients.
82 //
83 // Note(user): It is better complexity wise to first refine the underlying
84 // partition as much as possible, and then process all
85 // ActivityShouldNotIncrease() and ActivityShouldNotDecrease() in two passes.
86 // Experiment with it, it might require changing the API slightly since the
87 // increase / decrease functions also refine the partition.
88 void CanOnlyDominateEachOther(absl::Span<const int> refs);
89 void ActivityShouldNotChange(absl::Span<const int> refs,
90 absl::Span<const int64> coeffs);
91 void ActivityShouldNotDecrease(absl::Span<const int> enforcements,
92 absl::Span<const int> refs,
93 absl::Span<const int64> coeffs);
94 void ActivityShouldNotIncrease(absl::Span<const int> enforcements,
95 absl::Span<const int> refs,
96 absl::Span<const int64> coeffs);
97
98 // EndFirstPhase() must be called once all constraints have been processed
99 // once. One then needs to redo the calls to ActivityShouldNotIncrease() and
100 // ActivityShouldNotDecrease(). And finally call EndSecondPhase() before
101 // querying the domination information.
102 void EndFirstPhase();
103 void EndSecondPhase();
104
105 // This is true if this variable was never restricted by any call. We can thus
106 // fix it to its lower bound.
107 bool CanFreelyDecrease(int ref) const;
108 bool CanFreelyDecrease(IntegerVariable var) const;
109
110 // Returns a set of variable dominating the given ones. Note that to keep the
111 // algo efficient, this might not include all the possible dominations.
112 //
113 // Note: we never include as part of the dominating candidate variables that
114 // can freely increase.
115 absl::Span<const IntegerVariable> DominatingVariables(int ref) const;
116 absl::Span<const IntegerVariable> DominatingVariables(
117 IntegerVariable var) const;
118
119 // Returns readable string with the possible valid combinations of the form
120 // (var++/--, dom++/--) to facilitate debugging.
121 std::string DominationDebugString(IntegerVariable var) const;
122
123 private:
124 struct IntegerVariableWithRank {
125 IntegerVariable var;
126 int part;
127 int64 rank;
128
129 bool operator<(const IntegerVariableWithRank& o) const {
130 return rank < o.rank;
131 }
132 };
133
134 // This refine the partition can_dominate_partition_ with the given set.
135 void RefinePartition(std::vector<int>* vars);
136
137 // Convert the input from the public API into tmp_ranks_.
138 void MakeRankEqualToStartOfPart(absl::Span<IntegerVariableWithRank> span);
139 void FillTempRanks(bool reverse_references,
140 absl::Span<const int> enforcements,
141 absl::Span<const int> refs,
142 absl::Span<const int64> coeffs);
143
144 // First phase functions. We will keep for each variable a list of possible
145 // candidates which is as short as possible.
146 absl::Span<const IntegerVariable> InitialDominatingCandidates(
147 IntegerVariable var) const;
148 void ProcessTempRanks();
149 void Initialize(absl::Span<IntegerVariableWithRank> span);
150
151 // Second phase function to filter the current candidate lists.
152 void FilterUsingTempRanks();
153
154 // Debug function.
155 void CheckUsingTempRanks();
156
157 // Starts at zero on Reset(), move to one on EndFirstPhase() and to 2 on
158 // EndSecondPhase(). This is used for debug checks and to control what happen
159 // on the constraint processing functions.
160 int phase_ = 0;
161
162 // The variables will be sorted by non-decreasking rank. The rank is also the
163 // start of the first variable in tmp_ranks_ with this rank.
164 //
165 // Note that the rank should be int, but to reuse the same vector when we
166 // construct it, we need int64. See FillTempRanks().
167 std::vector<IntegerVariableWithRank> tmp_ranks_;
168
169 // This do not change after EndFirstPhase().
170 //
171 // We will add to the Dynamic partion, a set of subset S, each meaning that
172 // any variable in S can only dominate or be dominated by another variable in
173 // S.
174 std::vector<int> tmp_vars_;
175 std::unique_ptr<DynamicPartition> partition_;
177
178 // For all one sided constraints, we keep the bitmap of constraint indices
179 // modulo 64 that block on the lower side each variable.
180 int64 ct_index_for_signature_ = 0;
181 absl::StrongVector<IntegerVariable, uint64> block_down_signatures_;
182
183 // Used by FilterUsingTempRanks().
184 int num_vars_with_negation_;
186
187 // We don't use absl::Span() because the underlying buffer can be resized.
188 // This however serve the same purpose.
189 struct IntegerVariableSpan {
190 int start = 0;
191 int size = 0;
192 };
193
194 // This hold the first phase best candidate.
195 // Warning, the initial candidates span can overlap in the shared_buffer_.
196 std::vector<IntegerVariable> shared_buffer_;
198
199 // This will hold the final result.
200 // Buffer with independent content for each vars.
201 std::vector<IntegerVariable> buffer_;
203};
204
205// This detects variables that can move freely in one direction, or that can
206// move freely as long as their value do not cross a bound.
207//
208// TODO(user): This is actually an important step to do before scaling as it can
209// usually reduce really large bounds!
211 public:
212 // Reset the class to a clean state.
213 // This must be called before processing the constraints.
214 void Reset(int num_variables) {
215 can_freely_decrease_until_.assign(2 * num_variables, kMinIntegerValue);
216 num_locks_.assign(2 * num_variables, 0);
217 locking_ct_index_.assign(2 * num_variables, -1);
218 }
219
220 // All constraints should be mapped to one of more call to these functions.
221 void CannotDecrease(absl::Span<const int> refs, int ct_index = -1);
222 void CannotIncrease(absl::Span<const int> refs, int ct_index = -1);
223 void CannotMove(absl::Span<const int> refs);
224
225 // Most of the logic here deals with linear constraints.
226 template <typename LinearProto>
227 void ProcessLinearConstraint(bool is_objective,
229 const LinearProto& linear, int64 min_activity,
230 int64 max_activity);
231
232 // Once ALL constraints have been processed, call this to fix variables or
233 // reduce their domain if possible.
234 //
235 // Note that this also tighten some constraint that are the only one blocking
236 // in one direction. Currently we only do that for implication, so that if we
237 // have two Booleans such that a + b <= 1 we transform that to = 1 and we
238 // remove one variable since we have now an equivalence relation.
240
241 // The given ref can always freely decrease until the returned value.
242 // Note that this does not take into account the domain of the variable.
244 return can_freely_decrease_until_[RefToIntegerVariable(ref)].value();
245 }
246
247 private:
248 // We encode proto ref as IntegerVariable for indexing vectors.
249 static IntegerVariable RefToIntegerVariable(int ref) {
250 return RefIsPositive(ref) ? IntegerVariable(2 * ref)
251 : IntegerVariable(2 * NegatedRef(ref) + 1);
252 }
253
254 // Starts with kMaxIntegerValue, and decrease as constraints are processed.
255 absl::StrongVector<IntegerVariable, IntegerValue> can_freely_decrease_until_;
256
257 // How many times can_freely_decrease_until_[var] was set by a constraints.
258 // If only one constraint is blocking, we can do more presolve.
260
261 // If num_locks_[var] == 1, this will be the unique constraint that block var
262 // in this direction. Note that it can be set to -1 if this wasn't recorded.
264};
265
266// Detect the variable dominance relations within the given model. Note that
267// to avoid doing too much work, we might miss some relations. This does two
268// full scan of the model.
269void DetectDominanceRelations(const PresolveContext& context,
270 VarDomination* var_domination,
271 DualBoundStrengthening* dual_bound_strengthening);
272
273// Once detected, exploit the dominance relations that appear in the same
274// constraint. This does a full scan of the model.
275//
276// Return false if the problem is infeasible.
277bool ExploitDominanceRelations(const VarDomination& var_domination,
278 PresolveContext* context);
279
280} // namespace sat
281} // namespace operations_research
282
283#endif // OR_TOOLS_SAT_VAR_DOMINATION_H_
void assign(size_type n, const value_type &val)
void CannotMove(absl::Span< const int > refs)
void ProcessLinearConstraint(bool is_objective, const PresolveContext &context, const LinearProto &linear, int64 min_activity, int64 max_activity)
void CannotIncrease(absl::Span< const int > refs, int ct_index=-1)
void CannotDecrease(absl::Span< const int > refs, int ct_index=-1)
void ActivityShouldNotDecrease(absl::Span< const int > enforcements, absl::Span< const int > refs, absl::Span< const int64 > coeffs)
void ActivityShouldNotIncrease(absl::Span< const int > enforcements, absl::Span< const int > refs, absl::Span< const int64 > coeffs)
static int IntegerVariableToRef(IntegerVariable var)
void ActivityShouldNotChange(absl::Span< const int > refs, absl::Span< const int64 > coeffs)
absl::Span< const IntegerVariable > DominatingVariables(int ref) const
std::string DominationDebugString(IntegerVariable var) const
static IntegerVariable RefToIntegerVariable(int ref)
void CanOnlyDominateEachOther(absl::Span< const int > refs)
IntVar * var
Definition: expr_array.cc:1858
GurobiMPCallbackContext * context
int64_t int64
bool VariableIsPositive(IntegerVariable i)
Definition: integer.h:130
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
void DetectDominanceRelations(const PresolveContext &context, VarDomination *var_domination, DualBoundStrengthening *dual_bound_strengthening)
bool ExploitDominanceRelations(const VarDomination &var_domination, PresolveContext *context)
bool RefIsPositive(int ref)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...