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