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 
23 namespace operations_research {
24 namespace 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_;
176  absl::StrongVector<IntegerVariable, bool> can_freely_decrease_;
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,
228  const PresolveContext& context,
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.
243  int64 CanFreelyDecreaseUntil(int ref) const {
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.
269 void 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.
277 bool 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 RefIsPositive(int ref)
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 VariableIsPositive(IntegerVariable i)
Definition: integer.h:130
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...