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

#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/logging.h"
#include "base/scoped_ptr.h"
#include "constraint_solver/constraint_solver.h"
#include "constraint_solver/constraint_solveri.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Functions
	DEFINE_int32 (num_teams, 10,"Number of teams in the problem.")
	Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.
	DEFINE_int32 (time_limit, 20000,"Time limit in ms.")
	General solving parameters.
	DEFINE_bool (run_all_heuristics, true,"Run all heuristics in impact search, see DefaultPhaseParameters"" in constraint_solver/constraint_solver.h for details.")
	Search tweaking parameters. These are defined to illustrate their effect.
	DEFINE_int32 (heuristics_period, 30,"Frequency to run all heuristics, see DefaultPhaseParameters"" in constraint_solver/constraint_solver.h for details.")
	DEFINE_double (restart_log_size, 8.0,"Threshold for automatic restarting the search in default phase,"" see DefaultPhaseParameters in ""constraint_solver/constraint_solver.h for details.")
void	operations_research::ComputeOneDayOneTeamTuples (int num_teams, IntTupleSet *const tuples)
	Utility functions to help create the model.
void	operations_research::AddOneDayOneTeamConstraint (Solver *const solver, IntVar *const opponent, IntVar *const home_away, IntVar *const signed_opponent, const IntTupleSet &intra_day_tuples)
void	operations_research::ComputeOneDayTuples (int num_teams, IntTupleSet *const day_tuples)
	Constraints for one day and all teams.
void	operations_research::AddOneTeamConstraints (Solver *const solver, const std::vector< IntVar * > &opponents, const std::vector< IntVar * > &home_aways, const std::vector< IntVar * > &signed_opponents, const IntTupleSet &home_away_tuples, IntVar *const break_var, int num_teams)
	Adds all constraints relating to one teams and the complete schedule.
void	operations_research::ComputeOneTeamHomeAwayTuples (int num_teams, IntTupleSet *const home_away_tuples)
	Constraints for one team and all days.
void	operations_research::SportsScheduling (int num_teams)
	Main solving method.
int	main (int argc, char **argv)
Variables
static const char	kUsage []
	namespace operations_research

---

Function Documentation

DEFINE_bool	(	run_all_heuristics	,
		true	,
		"Run all heuristics in impact	search,
		see DefaultPhaseParameters""in constraint_solver/constraint_solver.h for details."
	)

Search tweaking parameters. These are defined to illustrate their effect.

DEFINE_double	(	restart_log_size	,
		8.	0,
		"Threshold for automatic restarting the search in default	phase,
		""see DefaultPhaseParameters in""constraint_solver/constraint_solver.h for details."
	)

DEFINE_int32	(	heuristics_period	,
		30	,
		"Frequency to run all	heuristics,
		see DefaultPhaseParameters""in constraint_solver/constraint_solver.h for details."
	)

DEFINE_int32	(	time_limit	,
		20000	,
		"Time limit in ms."
	)

General solving parameters.

DEFINE_int32	(	num_teams	,
		10	,
		"Number of teams in the problem."
	)

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. Sports scheduling problem.

We want to solve the problem of scheduling of team matches in a double round robin tournament. Given a number of teams, we want each team to encounter all other teams, twice, once at home, and once away. Furthermore, you cannot meet the same team twice in the same half-season.

Finally, there are constraints on the sequence of home or aways:

• You cannot have 3 consecutive homes or three consecutive aways.
• A break is a sequence of two homes or two aways, the overall objective of the optimization problem is to minimize the total number of breaks.

We model this problem with three matrices of variables, each with num_teams rows and 2*(num_teams - 1) columns: the var [i][j] corresponds to the match of team i at day j. There are 2*(num_teams - 1) columns because each team meets num_teams - 1 opponents twice. - The 'opponent' var [i][j] is the index of the opposing team.

• The 'home_away' var [i][j] is a boolean: 1 for 'playing away', 0 for 'playing at home'.
• The 'opponent_and_home_away' var [i][j] is the 'opponent' var [i][j] + num_teams * the 'home_away' var [i][j]. This aggregated variable will be useful to state constraints of the model and to do search on it.

We use an original approch in this model as most of the constraints will be pre-computed and asserted using an AllowedAssignment constraint (see Solver::MakeAllowedAssignment() in constraint_solver.h). In particular:

• Each day, we have a perfect matching between teams (A meets B <=> B meets A, and A is at home <=> B is away). A cannot meet itself.
• For each team, over the length of the tournament, we have constraints on the sequence of home-aways. We will precompute all possible sequences of home_aways, as well as the corresponding number of breaks for that team.
• For a given team and a given day, the link between the opponent var, the home_away var and the aggregated var (see third matrix of variables) is also maintained using a AllowedAssignment constraint.

Usage: run this with --helpshort for a short usage manual. Problem main flags.

int main	(	int	argc,
		char **	argv
	)

Definition at line 419 of file sports_scheduling.cc.

---

Variable Documentation

const char kUsage[] [static]

Initial value:

    "Usage: see flags.\nThis program runs a sports scheduling problem."
    "There is no output besides the debug LOGs of the solver."

namespace operations_research

Definition at line 415 of file sports_scheduling.cc.