1 // Copyright 2010-2021 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 // This problem is inspired by the Dobble game (aka Spot-It in the
15 // USA). In this game, we have 57 cards, 57 symbols, and 8 symbols
16 // per card. We want to assign symbols per card such that any two
17 // cards have exactly one symbol in common. These numbers can be
18 // generalized: we have N cards, each with K different symbols, and
19 // there are N different symbols overall.
20 //
21 // This is a feasibility problem. We transform that into an
22 // optimization problem where we penalize cards whose intersection is
23 // of cardinality different from 1. A feasible solution of the
24 // original problem is a solution with a zero cost.
25 //
26 // Furthermore, we solve this problem using local search, and with a
27 // dedicated constraint.
28 //
29 // The purpose of the example is to demonstrates how to write local
30 // search operators and local search filters.
31
32 #include <algorithm>
33 #include <cstdint>
34 #include <cstdlib>
35 #include <vector>
36
37 #include "absl/flags/parse.h"
38 #include "absl/flags/usage.h"
39 #include "absl/random/random.h"
40 #include "absl/strings/str_format.h"
41 #include "ortools/base/commandlineflags.h"
42 #include "ortools/base/integral_types.h"
43 #include "ortools/base/map_util.h"
44 #include "ortools/constraint_solver/constraint_solveri.h"
45 #include "ortools/util/bitset.h"
46
47 ABSL_FLAG(int, symbols_per_card, 8, "Number of symbols per card.");
48 ABSL_FLAG(int, ls_seed, 1,
49 "Seed for the random number generator (used by "
50 "the Local Neighborhood Search).");
51 ABSL_FLAG(bool, use_filter, true,
52 "Use filter in the local search to prune moves.");
53 ABSL_FLAG(int, num_swaps, 4,
54 "If num_swap > 0, the search for an optimal "
55 "solution will be allowed to use an operator that swaps the "
56 "symbols of up to num_swap pairs ((card1, symbol on card1), "
57 "(card2, symbol on card2)).");
58 ABSL_FLAG(int, time_limit_in_ms, 60000,
59 "Time limit for the global search in ms.");
60
61 namespace operations_research {
62
63 // ----- Dedicated constraint to count the symbols shared by two cards -----
64
65 // This constraint maintains:
66 // sum_i(card1_symbol_vars[i]*card2_symbol_vars[i]) == count_var.
67 // with all card_symbol_vars[i] being boolean variables.
68 class SymbolsSharedByTwoCardsConstraint : public Constraint {
69 public:
70 // This constructor does not take any ownership on its arguments.
SymbolsSharedByTwoCardsConstraint(Solver * const solver,const std::vector<IntVar * > & card1_symbol_vars,const std::vector<IntVar * > & card2_symbol_vars,IntVar * const num_symbols_in_common_var)71 SymbolsSharedByTwoCardsConstraint(
72 Solver* const solver, const std::vector<IntVar*>& card1_symbol_vars,
73 const std::vector<IntVar*>& card2_symbol_vars,
74 IntVar* const num_symbols_in_common_var)
75 : Constraint(solver),
76 card1_symbol_vars_(card1_symbol_vars),
77 card2_symbol_vars_(card2_symbol_vars),
78 num_symbols_(card1_symbol_vars.size()),
79 num_symbols_in_common_var_(num_symbols_in_common_var) {
80 // Checks that cards have the same size.
81 CHECK_EQ(card1_symbol_vars.size(), card2_symbol_vars.size());
82
83 // Verify that we are really dealing with boolean variables.
84 for (int i = 0; i < num_symbols_; ++i) {
85 CHECK_GE(card1_symbol_vars_[i]->Min(), 0);
86 CHECK_GE(card2_symbol_vars_[i]->Min(), 0);
87 CHECK_LE(card1_symbol_vars_[i]->Max(), 1);
88 CHECK_LE(card2_symbol_vars_[i]->Max(), 1);
89 }
90 }
91
~SymbolsSharedByTwoCardsConstraint()92 ~SymbolsSharedByTwoCardsConstraint() override {}
93
94 // Adds observers (named Demon) to variable events. These demons are
95 // responsible for implementing the propagation algorithm of the
96 // constraint.
Post()97 void Post() override {
98 // Create a demon 'global_demon' that will bind events on
99 // variables to the calling of the 'InitialPropagate()' method. As
100 // this method is expensive, 'global_demon' has a low priority. As
101 // such, InitialPropagate will be called after all normal demons
102 // and constraints have reached a fixed point. Note
103 // that ownership of the 'global_demon' belongs to the solver.
104 Demon* const global_demon =
105 solver()->MakeDelayedConstraintInitialPropagateCallback(this);
106 // Attach to all variables.
107 for (int i = 0; i < num_symbols_; ++i) {
108 card1_symbol_vars_[i]->WhenBound(global_demon);
109 card2_symbol_vars_[i]->WhenBound(global_demon);
110 }
111 // Attach to cardinality variable.
112 num_symbols_in_common_var_->WhenBound(global_demon);
113 }
114
115 // This is the main propagation method.
116 //
117 // It scans all card1_symbol_vars * card2_symbol_vars and increments 3
118 // counters:
119 // - min_symbols_in_common if both booleans variables are bound to true.
120 // - max_symbols_in_common if both booleans are not bound to false.
121 //
122 // Then we know that num_symbols_in_common_var is in the range
123 // [min_symbols_in_common .. max_symbols_in_common].
124 //
125 // Now, if num_symbols_in_common_var->Max() ==
126 // min_symbols_in_common, then all products that contribute to
127 // max_symbols_in_common but not to min_symbols_in_common should be
128 // set to 0.
129 //
130 // Conversely, if num_symbols_in_common_var->Min() ==
131 // max_symbols_in_common, then all products that contribute to
132 // max_symbols_in_common should be set to 1.
InitialPropagate()133 void InitialPropagate() override {
134 int max_symbols_in_common = 0;
135 int min_symbols_in_common = 0;
136 for (int i = 0; i < num_symbols_; ++i) {
137 if (card1_symbol_vars_[i]->Min() == 1 &&
138 card2_symbol_vars_[i]->Min() == 1) {
139 min_symbols_in_common++;
140 }
141 if (card1_symbol_vars_[i]->Max() == 1 &&
142 card2_symbol_vars_[i]->Max() == 1) {
143 max_symbols_in_common++;
144 }
145 }
146 num_symbols_in_common_var_->SetRange(min_symbols_in_common,
147 max_symbols_in_common);
148 // If min_symbols_in_common == max_symbols_in_common, it means
149 // that num_symbols_in_common_var_ is already fully determined: we
150 // have nothing to do.
151 if (min_symbols_in_common == max_symbols_in_common) {
152 DCHECK_EQ(min_symbols_in_common, num_symbols_in_common_var_->Max());
153 DCHECK_EQ(min_symbols_in_common, num_symbols_in_common_var_->Min());
154 return;
155 }
156 if (num_symbols_in_common_var_->Max() == min_symbols_in_common) {
157 // All undecided product terms should be forced to 0.
158 for (int i = 0; i < num_symbols_; ++i) {
159 // If both Min() are 0, then we can't force either variable to
160 // be zero (even if we know that their product is zero),
161 // because either variable could be 1 as long as the other is
162 // 0.
163 if (card1_symbol_vars_[i]->Min() == 1 &&
164 card2_symbol_vars_[i]->Min() == 0) {
165 card2_symbol_vars_[i]->SetValue(0);
166 } else if (card2_symbol_vars_[i]->Min() == 1 &&
167 card1_symbol_vars_[i]->Min() == 0) {
168 card1_symbol_vars_[i]->SetValue(0);
169 }
170 }
171 } else if (num_symbols_in_common_var_->Min() == max_symbols_in_common) {
172 // All undecided product terms should be forced to 1.
173 for (int i = 0; i < num_symbols_; ++i) {
174 if (card1_symbol_vars_[i]->Max() == 1 &&
175 card2_symbol_vars_[i]->Max() == 1) {
176 // Note that we also force already-decided product terms,
177 // but this doesn't change anything.
178 card1_symbol_vars_[i]->SetValue(1);
179 card2_symbol_vars_[i]->SetValue(1);
180 }
181 }
182 }
183 }
184
185 private:
186 std::vector<IntVar*> card1_symbol_vars_;
187 std::vector<IntVar*> card2_symbol_vars_;
188 const int num_symbols_;
189 IntVar* const num_symbols_in_common_var_;
190 };
191
192 // Creates two integer variables: one that counts the number of
193 // symbols common to two cards, and one that counts the absolute
194 // difference between the first var and 1 (i.e. the violation of the
195 // objective). Returns the latter (both vars are owned by the Solver
196 // anyway).
CreateViolationVar(Solver * const solver,const std::vector<IntVar * > & card1_symbol_vars,const std::vector<IntVar * > & card2_symbol_vars,int num_symbols_per_card)197 IntVar* CreateViolationVar(Solver* const solver,
198 const std::vector<IntVar*>& card1_symbol_vars,
199 const std::vector<IntVar*>& card2_symbol_vars,
200 int num_symbols_per_card) {
201 IntVar* const num_symbols_in_common_var =
202 solver->MakeIntVar(0, num_symbols_per_card);
203 // RevAlloc transfers the ownership of the constraint to the solver.
204 solver->AddConstraint(solver->RevAlloc(new SymbolsSharedByTwoCardsConstraint(
205 solver, card1_symbol_vars, card2_symbol_vars,
206 num_symbols_in_common_var)));
207 return solver->MakeAbs(solver->MakeSum(num_symbols_in_common_var, -1))->Var();
208 }
209
210 // ---------- Local Search ----------
211
212 // The "local search", or "local neighborhood search", works like
213 // this: starting from a given solution to the problem, other
214 // solutions in its neighborhood are generated from it, some of them
215 // might be selected (because they're better, for example) to become a
216 // starting point for other neighborhood searches, and so on.. The
217 // detailed search algorithm can vary and depends on the problem to
218 // solve.
219 //
220 // The fundamental building block for the local search is the "search
221 // operator", which has three fundamental methods in its API:
222 //
223 // - Its constructor, which keeps (mutable) references to the
224 // solver's internal variables (here, the card symbol variables).
225 //
226 // - OnStart(), which is called at the start of a local search, and
227 // after each solution (i.e. when the local search starts again from
228 // that new solution). The solver variables are supposed to represent
229 // a valid solution at this point. This method is used by the search
230 // operator to initialize its state and be ready to start the
231 // exploration of the neighborhood of the given solution.
232 //
233 // - MakeOneNeighbor(), which picks a neighbor of the initial
234 // solution, and changes the solver's internal variables accordingly
235 // to represent that new state.
236 //
237 // All local search operators on this problem will derive from the
238 // parent class below, which contains some shared code to store a
239 // compact representation of which symbols appeal on each cards.
240 class DobbleOperator : public IntVarLocalSearchOperator {
241 public:
DobbleOperator(const std::vector<IntVar * > & card_symbol_vars,int num_cards,int num_symbols,int num_symbols_per_card)242 DobbleOperator(const std::vector<IntVar*>& card_symbol_vars, int num_cards,
243 int num_symbols, int num_symbols_per_card)
244 : IntVarLocalSearchOperator(card_symbol_vars),
245 num_cards_(num_cards),
246 num_symbols_(num_symbols),
247 num_symbols_per_card_(num_symbols_per_card),
248 symbols_per_card_(num_cards) {
249 CHECK_GT(num_cards, 0);
250 CHECK_GT(num_symbols, 0);
251 CHECK_GT(num_symbols_per_card, 0);
252 for (int card = 0; card < num_cards; ++card) {
253 symbols_per_card_[card].assign(num_symbols_per_card, -1);
254 }
255 }
256
~DobbleOperator()257 ~DobbleOperator() override {}
258
259 protected:
260 // OnStart() simply stores the current symbols per card in
261 // symbols_per_card_, and defers further initialization to the
262 // subclass's InitNeighborhoodSearch() method.
OnStart()263 void OnStart() override {
264 for (int card = 0; card < num_cards_; ++card) {
265 int found = 0;
266 for (int symbol = 0; symbol < num_symbols_; ++symbol) {
267 if (Value(VarIndex(card, symbol)) == 1) {
268 symbols_per_card_[card][found++] = symbol;
269 }
270 }
271 DCHECK_EQ(num_symbols_per_card_, found);
272 }
273 InitNeighborhoodSearch();
274 }
275
276 virtual void InitNeighborhoodSearch() = 0;
277
278 // Find the index of the variable corresponding to the given symbol
279 // on the given card.
VarIndex(int card,int symbol)280 int VarIndex(int card, int symbol) { return card * num_symbols_ + symbol; }
281
282 // Move symbol1 from card1 to card2, and symbol2 from card2 to card1.
SwapTwoSymbolsOnCards(int card1,int symbol1,int card2,int symbol2)283 void SwapTwoSymbolsOnCards(int card1, int symbol1, int card2, int symbol2) {
284 SetValue(VarIndex(card1, symbol1), 0);
285 SetValue(VarIndex(card2, symbol2), 0);
286 SetValue(VarIndex(card1, symbol2), 1);
287 SetValue(VarIndex(card2, symbol1), 1);
288 }
289
290 const int num_cards_;
291 const int num_symbols_;
292 const int num_symbols_per_card_;
293 std::vector<std::vector<int> > symbols_per_card_;
294 };
295
296 // ----- Swap 2 symbols -----
297
298 // This operator explores *all* pairs (card1, some symbol on card1),
299 // (card2, some symbol on card2) and swaps the symbols between the two
300 // cards.
301 //
302 // Note that this could create invalid moves (for example, by adding a
303 // symbol to a card that already had it); see the DobbleFilter class
304 // below to see how we filter those out.
305 class SwapSymbols : public DobbleOperator {
306 public:
SwapSymbols(const std::vector<IntVar * > & card_symbol_vars,int num_cards,int num_symbols,int num_symbols_per_card)307 SwapSymbols(const std::vector<IntVar*>& card_symbol_vars, int num_cards,
308 int num_symbols, int num_symbols_per_card)
309 : DobbleOperator(card_symbol_vars, num_cards, num_symbols,
310 num_symbols_per_card),
311 current_card1_(-1),
312 current_card2_(-1),
313 current_symbol1_(-1),
314 current_symbol2_(-1) {}
315
~SwapSymbols()316 ~SwapSymbols() override {}
317
318 // Finds the next swap, returns false when it has finished.
MakeOneNeighbor()319 bool MakeOneNeighbor() override {
320 if (!PickNextSwap()) {
321 VLOG(1) << "finished neighborhood";
322 return false;
323 }
324
325 const int symbol1 = symbols_per_card_[current_card1_][current_symbol1_];
326 const int symbol2 = symbols_per_card_[current_card2_][current_symbol2_];
327 SwapTwoSymbolsOnCards(current_card1_, symbol1, current_card2_, symbol2);
328 return true;
329 }
330
331 private:
332 // Reinit the exploration loop.
InitNeighborhoodSearch()333 void InitNeighborhoodSearch() override {
334 current_card1_ = 0;
335 current_card2_ = 1;
336 current_symbol1_ = 0;
337 current_symbol2_ = -1;
338 }
339
340 // Compute the next move. It returns false when there are none.
PickNextSwap()341 bool PickNextSwap() {
342 current_symbol2_++;
343 if (current_symbol2_ == num_symbols_per_card_) {
344 current_symbol2_ = 0;
345 current_symbol1_++;
346 if (current_symbol1_ == num_symbols_per_card_) {
347 current_symbol1_ = 0;
348 current_card2_++;
349 if (current_card2_ == num_cards_) {
350 current_card1_++;
351 current_card2_ = current_card1_ + 1;
352 }
353 }
354 }
355 return current_card1_ < num_cards_ - 1;
356 }
357
358 int current_card1_;
359 int current_card2_;
360 int current_symbol1_;
361 int current_symbol2_;
362 };
363
364 // Multiple swaps of two symbols. This operator is an expanded version
365 // of the previous operator.
366 //
367 // At each step, it will pick a number num_swaps at random in
368 // [2 .. max_num_swaps], and then pick num_swaps random pairs (card1,
369 // some symbol on card1), (card2, some symbol on card2), and swap the
370 // symbols of each pair.
371 //
372 // As the search space (the "neighborhood") is huge, we use a
373 // randomized "infinite" version instead of an iterative, exhaustive
374 // one.
375 class SwapSymbolsOnCardPairs : public DobbleOperator {
376 public:
SwapSymbolsOnCardPairs(const std::vector<IntVar * > & card_symbol_vars,int num_cards,int num_symbols,int num_symbols_per_card,int max_num_swaps)377 SwapSymbolsOnCardPairs(const std::vector<IntVar*>& card_symbol_vars,
378 int num_cards, int num_symbols,
379 int num_symbols_per_card, int max_num_swaps)
380 : DobbleOperator(card_symbol_vars, num_cards, num_symbols,
381 num_symbols_per_card),
382 rand_(absl::GetFlag(FLAGS_ls_seed)),
383 max_num_swaps_(max_num_swaps) {
384 CHECK_GE(max_num_swaps, 2);
385 }
386
~SwapSymbolsOnCardPairs()387 ~SwapSymbolsOnCardPairs() override {}
388
389 protected:
MakeOneNeighbor()390 bool MakeOneNeighbor() override {
391 const int num_swaps =
392 absl::Uniform<int32_t>(rand_, 0, max_num_swaps_ - 1) + 2;
393 for (int i = 0; i < num_swaps; ++i) {
394 const int card_1 = absl::Uniform<int32_t>(rand_, 0, num_cards_);
395 const int symbol_index_1 =
396 absl::Uniform<int32_t>(rand_, 0, num_symbols_per_card_);
397 const int symbol_1 = symbols_per_card_[card_1][symbol_index_1];
398 const int card_2 = absl::Uniform<int32_t>(rand_, 0, num_cards_);
399 const int symbol_index_2 =
400 absl::Uniform<int32_t>(rand_, 0, num_symbols_per_card_);
401 const int symbol_2 = symbols_per_card_[card_2][symbol_index_2];
402 SwapTwoSymbolsOnCards(card_1, symbol_1, card_2, symbol_2);
403 }
404 return true;
405 }
406
InitNeighborhoodSearch()407 void InitNeighborhoodSearch() override {}
408
409 private:
410 std::mt19937 rand_;
411 const int max_num_swaps_;
412 };
413
414 // ----- Local Search Filter -----
415
416 // A filter is responsible for rejecting a local search move faster
417 // than what the propagation of the constraint solver would do.
418 // Its API consists in:
419 // - The constructor, which takes as input a reference to all the
420 // variables relevant to the filter.
421 // - OnSynchronize(), called at the beginning of the search and
422 // after each move to a new solution (when the local search
423 // restarts from it).
424 // - Accept(), which takes as input an attempted move (in the form
425 // of a Delta to tentatively apply to the variables), and returns
426 // true iff this move is found valid.
427 //
428 // To decide if a move is valid, first this DobbleFilter builds a
429 // bitmap of symbols per card. Then for each move, it updates the
430 // bitmap according to the move and checks the following constraints:
431 // - First, each card still has num_symbols_per_card symbols. - The
432 // cost of the assignment described by the move is better than the
433 // current one.
434
435 // After the check is done, the original bitmap is restored if the
436 // move was rejected, so as to be ready for the next evaluation.
437 //
438 // Please note that this filter uses a fixed size bitset and
439 // effectively limits the number of cards to 63, and thus the number
440 // of symbols per card to 8.
441 class DobbleFilter : public IntVarLocalSearchFilter {
442 public:
DobbleFilter(const std::vector<IntVar * > & card_symbol_vars,int num_cards,int num_symbols,int num_symbols_per_card)443 DobbleFilter(const std::vector<IntVar*>& card_symbol_vars, int num_cards,
444 int num_symbols, int num_symbols_per_card)
445 : IntVarLocalSearchFilter(card_symbol_vars),
446 num_cards_(num_cards),
447 num_symbols_(num_symbols),
448 num_symbols_per_card_(num_symbols_per_card),
449 temporary_bitset_(0),
450 symbol_bitmask_per_card_(num_cards, 0),
451 violation_costs_(num_cards_, std::vector<int>(num_cards_, 0)) {}
452
453 // We build the current bitmap and the matrix of violation cost
454 // between any two cards.
OnSynchronize(const Assignment * delta)455 void OnSynchronize(const Assignment* delta) override {
456 symbol_bitmask_per_card_.assign(num_cards_, 0);
457 for (int card = 0; card < num_cards_; ++card) {
458 for (int symbol = 0; symbol < num_symbols_; ++symbol) {
459 if (Value(VarIndex(card, symbol))) {
460 SetBit64(&symbol_bitmask_per_card_[card], symbol);
461 }
462 }
463 }
464 for (int card1 = 0; card1 < num_cards_; ++card1) {
465 for (int card2 = 0; card2 < num_cards_; ++card2) {
466 violation_costs_[card1][card2] = ViolationCost(BitCount64(
467 symbol_bitmask_per_card_[card1] & symbol_bitmask_per_card_[card2]));
468 }
469 }
470 DCHECK(CheckCards());
471 }
472
473 // The LocalSearchFilter::Accept() API also takes a deltadelta,
474 // which is the difference between the current delta and the last
475 // delta that was given to Accept() -- but we don't use it here.
Accept(const Assignment * delta,const Assignment * unused_deltadelta,int64_t objective_min,int64_t objective_max)476 bool Accept(const Assignment* delta, const Assignment* unused_deltadelta,
477 int64_t objective_min, int64_t objective_max) override {
478 const Assignment::IntContainer& solution_delta = delta->IntVarContainer();
479 const int solution_delta_size = solution_delta.Size();
480
481 // The input const Assignment* delta given to Accept() may
482 // actually contain "Deactivated" elements, which represent
483 // variables that have been freed -- they are not bound to a
484 // single value anymore. This happens with LNS-type (Large
485 // Neighborhood Search) LocalSearchOperator, which are not used in
486 // this example as of 2012-01; and we refer the reader to
487 // ./routing.cc for an example of such LNS-type operators.
488 //
489 // For didactical purposes, we will assume for a moment that a
490 // LNS-type operator might be applied. The Filter will still be
491 // called, but our DobbleFilter here won't be able to work, since
492 // it needs every variable to be bound (i.e. have a fixed value),
493 // in the assignment that it considers. Therefore, we include here
494 // a snippet of code that will detect if the input assignment is
495 // not fully bound. For further details, read ./routing.cc -- but
496 // we strongly advise the reader to first try and understand all
497 // of this file.
498 for (int i = 0; i < solution_delta_size; ++i) {
499 if (!solution_delta.Element(i).Activated()) {
500 VLOG(1) << "Element #" << i << " of the delta assignment given to"
501 << " DobbleFilter::Accept() is not activated (i.e. its variable"
502 << " is not bound to a single value anymore). This means that"
503 << " we are in a LNS phase, and the DobbleFilter won't be able"
504 << " to filter anything. Returning true.";
505 return true;
506 }
507 }
508 VLOG(1) << "No LNS, size = " << solution_delta_size;
509
510 // Collect the set of cards that have been modified by this move.
511 std::vector<int> touched_cards;
512 ComputeTouchedCards(solution_delta, &touched_cards);
513
514 // Check basic metrics to fail fast.
515 if (!CheckCards()) {
516 RestoreBitsetPerCard();
517 DCHECK(CheckCards());
518 VLOG(1) << "reject by size";
519 return false;
520 }
521
522 // Compute new cost.
523 const int cost_delta = ComputeNewCost(touched_cards);
524
525 // Reset the data structure to the state before the evaluation.
526 RestoreBitsetPerCard();
527
528 // And exit (this is only valid for a greedy descent and would
529 // reject valid moves in tabu search for instance).
530 if (cost_delta >= 0) {
531 VLOG(1) << "reject";
532 }
533 return cost_delta < 0;
534 }
535
536 private:
537 // Undo information after an evaluation.
538 struct UndoChange {
UndoChangeoperations_research::DobbleFilter::UndoChange539 UndoChange(int c, uint64_t b) : card(c), bitset(b) {}
540 int card;
541 uint64_t bitset;
542 };
543
VarIndex(int card,int symbol)544 int VarIndex(int card, int symbol) { return card * num_symbols_ + symbol; }
545
ClearBitset()546 void ClearBitset() { temporary_bitset_ = 0; }
547
548 // For each touched card, compare against all others to compute the
549 // delta in term of cost. We use an bitset to avoid counting twice
550 // between two cards appearing in the local search move.
ComputeNewCost(const std::vector<int> & touched_cards)551 int ComputeNewCost(const std::vector<int>& touched_cards) {
552 ClearBitset();
553 int cost_delta = 0;
554 for (int i = 0; i < touched_cards.size(); ++i) {
555 const int touched = touched_cards[i];
556 SetBit64(&temporary_bitset_, touched);
557 const uint64_t card_bitset = symbol_bitmask_per_card_[touched];
558 const std::vector<int>& row_cost = violation_costs_[touched];
559 for (int other_card = 0; other_card < num_cards_; ++other_card) {
560 if (!IsBitSet64(&temporary_bitset_, other_card)) {
561 cost_delta += ViolationCost(
562 BitCount64(card_bitset & symbol_bitmask_per_card_[other_card]));
563 cost_delta -= row_cost[other_card];
564 }
565 }
566 }
567 return cost_delta;
568 }
569
570 // Collects all card indices appearing in the local search move.
ComputeTouchedCards(const Assignment::IntContainer & solution_delta,std::vector<int> * const touched_cards)571 void ComputeTouchedCards(const Assignment::IntContainer& solution_delta,
572 std::vector<int>* const touched_cards) {
573 ClearBitset();
574 const int solution_delta_size = solution_delta.Size();
575 const int kUnassigned = -1;
576 for (int index = 0; index < solution_delta_size; ++index) {
577 int64_t touched_var = kUnassigned;
578 FindIndex(solution_delta.Element(index).Var(), &touched_var);
579 CHECK_NE(touched_var, kUnassigned);
580 const int card = touched_var / num_symbols_;
581 const int symbol = touched_var % num_symbols_;
582 const int new_value = solution_delta.Element(index).Value();
583 if (!IsBitSet64(&temporary_bitset_, card)) {
584 SaveRestoreInformation(card);
585 touched_cards->push_back(card);
586 SetBit64(&temporary_bitset_, card);
587 }
588 if (new_value) {
589 SetBit64(&symbol_bitmask_per_card_[card], symbol);
590 } else {
591 ClearBit64(&symbol_bitmask_per_card_[card], symbol);
592 }
593 }
594 }
595
596 // Undo all modifications done when evaluating a move.
RestoreBitsetPerCard()597 void RestoreBitsetPerCard() {
598 for (int i = 0; i < restore_information_.size(); ++i) {
599 symbol_bitmask_per_card_[restore_information_[i].card] =
600 restore_information_[i].bitset;
601 }
602 restore_information_.clear();
603 }
604
605 // Stores undo information for a given card.
SaveRestoreInformation(int card)606 void SaveRestoreInformation(int card) {
607 restore_information_.push_back(
608 UndoChange(card, symbol_bitmask_per_card_[card]));
609 }
610
611 // Checks that after the local search move, each card would still have
612 // num_symbols_per_card symbols on it.
CheckCards()613 bool CheckCards() {
614 for (int i = 0; i < num_cards_; ++i) {
615 if (num_symbols_per_card_ != BitCount64(symbol_bitmask_per_card_[i])) {
616 VLOG(1) << "card " << i << " has bitset of size "
617 << BitCount64(symbol_bitmask_per_card_[i]);
618 return false;
619 }
620 }
621 return true;
622 }
623
ViolationCost(uint64_t cardinality) const624 int ViolationCost(uint64_t cardinality) const {
625 return (cardinality > 0 ? cardinality - 1 : 1);
626 }
627
628 const int num_cards_;
629 const int num_symbols_;
630 const int num_symbols_per_card_;
631 uint64_t temporary_bitset_;
632 std::vector<uint64_t> symbol_bitmask_per_card_;
633 std::vector<std::vector<int> > violation_costs_;
634 std::vector<UndoChange> restore_information_;
635 };
636
637 // ----- Main Method -----
638
SolveDobble(int num_cards,int num_symbols,int num_symbols_per_card)639 void SolveDobble(int num_cards, int num_symbols, int num_symbols_per_card) {
640 LOG(INFO) << "Solving dobble assignment problem:";
641 LOG(INFO) << " - " << num_cards << " cards";
642 LOG(INFO) << " - " << num_symbols << " symbols";
643 LOG(INFO) << " - " << num_symbols_per_card << " symbols per card";
644
645 // Creates the solver.
646 Solver solver("dobble");
647 // Creates the matrix of boolean variables (cards * symbols).
648 std::vector<std::vector<IntVar*> > card_symbol_vars(num_cards);
649 std::vector<IntVar*> all_card_symbol_vars;
650 for (int card_index = 0; card_index < num_cards; ++card_index) {
651 solver.MakeBoolVarArray(num_symbols,
652 absl::StrFormat("card_%i_", card_index),
653 &card_symbol_vars[card_index]);
654 for (int symbol_index = 0; symbol_index < num_symbols; ++symbol_index) {
655 all_card_symbol_vars.push_back(
656 card_symbol_vars[card_index][symbol_index]);
657 }
658 }
659 // Creates cardinality intersection variables and remember the
660 // violation variables.
661 std::vector<IntVar*> violation_vars;
662 for (int card1 = 0; card1 < num_cards; ++card1) {
663 for (int card2 = 0; card2 < num_cards; ++card2) {
664 if (card1 != card2) {
665 violation_vars.push_back(
666 CreateViolationVar(&solver, card_symbol_vars[card1],
667 card_symbol_vars[card2], num_symbols_per_card));
668 }
669 }
670 }
671 // Create the objective variable.
672 IntVar* const objective_var = solver.MakeSum(violation_vars)->Var();
673
674 // Add constraint: there must be exactly num_symbols_per_card
675 // symbols per card.
676 for (int card = 0; card < num_cards; ++card) {
677 solver.AddConstraint(
678 solver.MakeSumEquality(card_symbol_vars[card], num_symbols_per_card));
679 }
680
681 // IMPORTANT OPTIMIZATION:
682 // Add constraint: each symbol appears on exactly
683 // num_symbols_per_card cards (i.e. symbols are evenly
684 // distributed). This constraint is actually redundant, because it
685 // is a (non-trivial) consequence of the other constraints and of
686 // the model. But adding it makes the search go faster.
687 for (int symbol_index = 0; symbol_index < num_symbols; ++symbol_index) {
688 std::vector<IntVar*> tmp;
689 for (int card_index = 0; card_index < num_cards; ++card_index) {
690 tmp.push_back(card_symbol_vars[card_index][symbol_index]);
691 }
692 solver.AddConstraint(solver.MakeSumEquality(tmp, num_symbols_per_card));
693 }
694
695 // Search.
696 LOG(INFO) << "Solving with Local Search";
697 LOG(INFO) << " - time limit = " << absl::GetFlag(FLAGS_time_limit_in_ms)
698 << " ms";
699
700 // Start a DecisionBuilder phase to find a first solution, using the
701 // strategy "Pick some random, yet unassigned card symbol variable
702 // and set its value to 1".
703 DecisionBuilder* const build_db = solver.MakePhase(
704 all_card_symbol_vars, Solver::CHOOSE_RANDOM, // Solver::IntVarStrategy
705 Solver::ASSIGN_MAX_VALUE); // Solver::IntValueStrategy
706
707 // Creates local search operators.
708 std::vector<LocalSearchOperator*> operators;
709 LocalSearchOperator* const switch_operator = solver.RevAlloc(new SwapSymbols(
710 all_card_symbol_vars, num_cards, num_symbols, num_symbols_per_card));
711 operators.push_back(switch_operator);
712 LOG(INFO) << " - add switch operator";
713 if (absl::GetFlag(FLAGS_num_swaps) > 0) {
714 LocalSearchOperator* const swaps_operator =
715 solver.RevAlloc(new SwapSymbolsOnCardPairs(
716 all_card_symbol_vars, num_cards, num_symbols, num_symbols_per_card,
717 absl::GetFlag(FLAGS_num_swaps)));
718 operators.push_back(swaps_operator);
719 LOG(INFO) << " - add swaps operator with at most "
720 << absl::GetFlag(FLAGS_num_swaps) << " swaps";
721 }
722
723 // Creates filter.
724 std::vector<LocalSearchFilter*> filters;
725 if (absl::GetFlag(FLAGS_use_filter)) {
726 filters.push_back(solver.RevAlloc(new DobbleFilter(
727 all_card_symbol_vars, num_cards, num_symbols, num_symbols_per_card)));
728 }
729 LocalSearchFilterManager* ls_manager =
730 solver.RevAlloc(new LocalSearchFilterManager(std::move(filters)));
731 // Main decision builder that regroups the first solution decision
732 // builder and the combination of local search operators and
733 // filters.
734 DecisionBuilder* const final_db = solver.MakeLocalSearchPhase(
735 all_card_symbol_vars, build_db,
736 solver.MakeLocalSearchPhaseParameters(
737 objective_var, solver.ConcatenateOperators(operators, true),
738 nullptr, // Sub decision builder, not needed here.
739 nullptr, // Limit the search for improving move, we will stop
740 // the exploration of the local search at the first
741 // improving solution (first accept).
742 ls_manager));
743
744 std::vector<SearchMonitor*> monitors;
745 // Optimize var search monitor.
746 OptimizeVar* const optimize = solver.MakeMinimize(objective_var, 1);
747 monitors.push_back(optimize);
748
749 // Search log.
750 SearchMonitor* const log = solver.MakeSearchLog(100000, optimize);
751 monitors.push_back(log);
752
753 // Search limit.
754 SearchLimit* const time_limit = solver.MakeTimeLimit(
755 absl::Milliseconds(absl::GetFlag(FLAGS_time_limit_in_ms)));
756 monitors.push_back(time_limit);
757
758 // And solve!
759 solver.Solve(final_db, monitors);
760 }
761 } // namespace operations_research
762
main(int argc,char ** argv)763 int main(int argc, char** argv) {
764 google::InitGoogleLogging(argv[0]);
765 absl::ParseCommandLine(argc, argv);
766 // These constants comes directly from the dobble game.
767 // There are actually 55 cards, but we can create up to 57 cards.
768 const int kSymbolsPerCard = absl::GetFlag(FLAGS_symbols_per_card);
769 const int kCards = kSymbolsPerCard * (kSymbolsPerCard - 1) + 1;
770 const int kSymbols = kCards;
771 operations_research::SolveDobble(kCards, kSymbols, kSymbolsPerCard);
772 return EXIT_SUCCESS;
773 }
774