or-tools/examples/cpp/dobble_ls.cc File Reference

#include <algorithm>
#include <vector>
#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/concise_iterator.h"
#include "base/map-util.h"
#include "constraint_solver/constraint_solveri.h"
#include "util/bitset.h"
#include "base/random.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Classes
class	operations_research::SymbolsSharedByTwoCardsConstraint
	Dedicated constraint to count the symbols shared by two cards. More...
class	operations_research::DobbleOperator
	Local Search. More...
class	operations_research::SwapSymbols
	Swap 2 symbols. More...
class	operations_research::SwapSymbolsOnCardPairs
	Multiple swaps of two symbols. More...
class	operations_research::DobbleFilter
	Local Search Filter. More...
struct	operations_research::DobbleFilter::UndoChange
	Undo information after an evaluation.
Functions
	DEFINE_int32 (symbols_per_card, 8,"Number of symbols per card.")
	Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.
	DEFINE_int32 (ls_seed, 1,"Seed for the random number generator (used by ""the Local Neighborhood Search).")
	DEFINE_bool (use_filter, true,"Use filter in the local search to prune moves.")
	DEFINE_int32 (num_swaps, 4,"If num_swap > 0, the search for an optimal ""solution will be allowed to use an operator that swaps the ""symbols of up to num_swap pairs ((card1, symbol on card1), ""(card2, symbol on card2)).")
	DEFINE_int32 (time_limit_in_ms, 60000,"Time limit for the global search in ms.")
IntVar *	operations_research::CreateViolationVar (Solver *const solver, const std::vector< IntVar * > &card1_symbol_vars, const std::vector< IntVar * > &card2_symbol_vars, int num_symbols_per_card)
	Creates two integer variables: one that counts the number of symbols common to two cards, and one that counts the absolute difference between the first var and 1 (i.e.
void	operations_research::SolveDobble (int num_cards, int num_symbols, int num_symbols_per_card)
	Main Method.
int	main (int argc, char **argv)
	namespace operations_research

---

Function Documentation

DEFINE_bool	(	use_filter	,
		true	,
		"Use filter in the local search to prune moves."
	)

DEFINE_int32	(	time_limit_in_ms	,
		60000	,
		"Time limit for the global search in ms."
	)

DEFINE_int32	(	num_swaps	,
		4	,
		"If	num_swap,
		0	,
		the search for an optimal""solution will be allowed to use an operator that swaps the""symbols of up to num_swap pairs((card1, symbol on card1),""(card2, symbol on card2))."
	)

DEFINE_int32	(	ls_seed	,
		1	,
		"Seed for the random number generator (used by ""the Local Neighborhood Search)."
	)

DEFINE_int32	(	symbols_per_card	,
		8	,
		"Number of symbols per card."
	)

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. This problem is inspired by the Dobble game (aka Spot-It in the USA). In this game, we have 57 cards, 57 symbols, and 8 symbols per card. We want to assign symbols per card such that any two cards have exactly one symbol in common. These numbers can be generalized: we have N cards, each with K different symbols, and there are N different symbols overall.

This is a feasability problem. We transform that into an optimization problem where we penalize cards whose intersection is of cardinality different from 1. A feasible solution of the original problem is a solution with a zero cost.

Furthermore, we solve this problem using local search, and with a dedicated constraint.

The purpose of the example is to demonstrates how to write local search operators and local search filters.

int main	(	int	argc,
		char **	argv
	)

namespace operations_research

Definition at line 803 of file dobble_ls.cc.