Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
331 lines (288 sloc) 11.7 KB
// Copyright 2010-2018 Google LLC
// 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.
// - If team A meets team B, the reverse match cannot happen less that 6 weeks
// after.
//
// We model this problem with three matrices of variables, each with
// num_teams rows and 2*(num_teams - 1) columns: the var at position [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 'signed_opponent' 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.
#include "absl/strings/str_cat.h"
#include "ortools/base/commandlineflags.h"
#include "ortools/base/integral_types.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
// Problem main flags.
DEFINE_int32(num_teams, 10, "Number of teams in the problem.");
DEFINE_string(params, "", "Sat parameters.");
namespace operations_research {
namespace sat {
void FirstModel(int num_teams) {
const int num_days = 2 * num_teams - 2;
const int kNoRematch = 6;
CpModelBuilder builder;
// Calendar variables.
std::vector<std::vector<IntVar>> opponents(num_teams);
std::vector<std::vector<BoolVar>> home_aways(num_teams);
std::vector<std::vector<IntVar>> signed_opponents(num_teams);
for (int t = 0; t < num_teams; ++t) {
for (int d = 0; d < num_days; ++d) {
Domain opponent_domain(0, num_teams - 1);
Domain signed_opponent_domain(0, 2 * num_teams - 1);
IntVar opp = builder.NewIntVar(opponent_domain)
.WithName(absl::StrCat("opponent_", t, "_", d));
BoolVar home =
builder.NewBoolVar().WithName(absl::StrCat("home_aways", t, "_", d));
IntVar signed_opp =
builder.NewIntVar(signed_opponent_domain)
.WithName(absl::StrCat("signed_opponent_", t, "_", d));
opponents[t].push_back(opp);
home_aways[t].push_back(home);
signed_opponents[t].push_back(signed_opp);
// One team cannot meet itself.
builder.AddNotEqual(opp, t);
builder.AddNotEqual(signed_opp, t);
builder.AddNotEqual(signed_opp, t + num_teams);
// Link opponent, home_away, and signed_opponent.
builder.AddEquality(opp, signed_opp).OnlyEnforceIf(Not(home));
builder.AddEquality(LinearExpr(opp).AddConstant(num_teams), signed_opp)
.OnlyEnforceIf(home);
}
}
// One day constraints.
for (int d = 0; d < num_days; ++d) {
std::vector<IntVar> day_opponents;
std::vector<IntVar> day_home_aways;
for (int t = 0; t < num_teams; ++t) {
day_opponents.push_back(opponents[t][d]);
day_home_aways.push_back(home_aways[t][d]);
}
builder.AddInverseConstraint(day_opponents, day_opponents);
for (int first_team = 0; first_team < num_teams; ++first_team) {
IntVar first_home = day_home_aways[first_team];
IntVar second_home = builder.NewBoolVar();
builder.AddVariableElement(day_opponents[first_team], day_home_aways,
second_home);
builder.AddEquality(LinearExpr::Sum({first_home, second_home}), 1);
}
builder.AddEquality(LinearExpr::Sum(day_home_aways), num_teams / 2);
}
// One team constraints.
for (int t = 0; t < num_teams; ++t) {
builder.AddAllDifferent(signed_opponents[t]);
const std::vector<IntVar> first_part(opponents[t].begin(),
opponents[t].begin() + num_teams - 1);
builder.AddAllDifferent(first_part);
const std::vector<IntVar> second_part(opponents[t].begin() + num_teams - 1,
opponents[t].end());
builder.AddAllDifferent(second_part);
for (int day = num_teams - kNoRematch; day < num_teams - 1; ++day) {
const std::vector<IntVar> moving(opponents[t].begin() + day,
opponents[t].begin() + day + kNoRematch);
builder.AddAllDifferent(moving);
}
builder.AddEquality(LinearExpr::BooleanSum(home_aways[t]), num_teams - 1);
// Forbid sequence of 3 homes or 3 aways.
for (int start = 0; start < num_days - 2; ++start) {
builder.AddBoolOr({home_aways[t][start], home_aways[t][start + 1],
home_aways[t][start + 2]});
builder.AddBoolOr({Not(home_aways[t][start]),
Not(home_aways[t][start + 1]),
Not(home_aways[t][start + 2])});
}
}
// Objective.
std::vector<BoolVar> breaks;
for (int t = 0; t < num_teams; ++t) {
for (int d = 0; d < num_days - 1; ++d) {
BoolVar break_var =
builder.NewBoolVar().WithName(absl::StrCat("break_", t, "_", d));
builder.AddBoolOr(
{Not(home_aways[t][d]), Not(home_aways[t][d + 1]), break_var});
builder.AddBoolOr({home_aways[t][d], home_aways[t][d + 1], break_var});
breaks.push_back(break_var);
}
}
builder.Minimize(LinearExpr::BooleanSum(breaks));
Model model;
if (!FLAGS_params.empty()) {
model.Add(NewSatParameters(FLAGS_params));
}
const CpSolverResponse response = SolveCpModel(builder.Build(), &model);
LOG(INFO) << CpSolverResponseStats(response);
if (response.status() == CpSolverStatus::OPTIMAL ||
response.status() == CpSolverStatus::FEASIBLE) {
for (int t = 0; t < num_teams; ++t) {
std::string output;
for (int d = 0; d < num_days; ++d) {
const int opponent = SolutionIntegerValue(response, opponents[t][d]);
const bool home = SolutionBooleanValue(response, home_aways[t][d]);
if (home) {
output += absl::StrCat(" %2d@", opponent);
} else {
output += absl::StrCat(" %2d ", opponent);
}
}
LOG(INFO) << output;
}
}
}
void SecondModel(int num_teams) {
const int num_days = 2 * num_teams - 2;
// const int kNoRematch = 6;
const int matches_per_day = num_teams - 1;
CpModelBuilder builder;
// Does team i receive team j at home on day d?
std::vector<std::vector<std::vector<BoolVar>>> fixtures(num_days);
for (int d = 0; d < num_days; ++d) {
fixtures[d].resize(num_teams);
for (int i = 0; i < num_teams; ++i) {
fixtures[d][i].resize(num_teams);
for (int j = 0; j < num_teams; ++j) {
if (i == j) {
fixtures[d][i][i] = builder.FalseVar();
} else {
fixtures[d][i][j] = builder.NewBoolVar();
}
}
}
}
// Is team t at home on day d?
std::vector<std::vector<BoolVar>> at_home(num_days);
for (int d = 0; d < num_days; ++d) {
for (int t = 0; t < num_teams; ++t) {
at_home[d].push_back(builder.NewBoolVar());
}
}
// Each day, Team t plays either at home or away.
for (int d = 0; d < num_days; ++d) {
for (int team = 0; team < num_teams; ++team) {
std::vector<BoolVar> possible_opponents;
for (int other = 0; other < num_teams; ++other) {
if (team == other)
continue;
possible_opponents.push_back(fixtures[d][team][other]);
possible_opponents.push_back(fixtures[d][other][team]);
}
builder.AddEquality(LinearExpr::BooleanSum(possible_opponents), 1);
}
}
// Each fixture happens once per season.
for (int team = 0; team < num_teams; ++team) {
for (int other = 0; other < num_teams; ++other) {
if (team == other)
continue;
std::vector<BoolVar> possible_days;
for (int d = 0; d < num_days; ++d) {
possible_days.push_back(fixtures[d][team][other]);
}
builder.AddEquality(LinearExpr::BooleanSum(possible_days), 1);
}
}
// Meet each opponent once per season.
for (int team = 0; team < num_teams; ++team) {
for (int other = 0; other < num_teams; ++other) {
if (team == other)
continue;
std::vector<BoolVar> first_half;
std::vector<BoolVar> second_half;
for (int d = 0; d < matches_per_day; ++d) {
first_half.push_back(fixtures[d][team][other]);
first_half.push_back(fixtures[d][other][team]);
second_half.push_back(fixtures[d + matches_per_day][team][other]);
second_half.push_back(fixtures[d + matches_per_day][other][team]);
}
builder.AddEquality(LinearExpr::BooleanSum(first_half), 1);
builder.AddEquality(LinearExpr::BooleanSum(second_half), 1);
}
}
// Maintain at_home[day][team].
for (int d = 0; d < num_days; ++d) {
for (int team = 0; team < num_teams; ++team) {
for (int other = 0; other < num_teams; ++other) {
if (team == other)
continue;
builder.AddImplication(fixtures[d][team][other], at_home[d][team]);
builder.AddImplication(fixtures[d][team][other],
Not(at_home[d][other]));
}
}
}
// Forbid sequence of 3 homes or 3 aways.
for (int team = 0; team < num_teams; ++team) {
for (int d = 0; d < num_days - 2; ++d) {
builder.AddBoolOr(
{at_home[d][team], at_home[d + 1][team], at_home[d + 2][team]});
builder.AddBoolOr({Not(at_home[d][team]), Not(at_home[d + 1][team]),
Not(at_home[d + 2][team])});
}
}
// Objective.
std::vector<BoolVar> breaks;
for (int t = 0; t < num_teams; ++t) {
for (int d = 0; d < num_days - 1; ++d) {
BoolVar break_var = builder.NewBoolVar();
builder.AddBoolOr(
{Not(at_home[d][t]), Not(at_home[d + 1][t]), break_var});
builder.AddBoolOr({at_home[d][t], at_home[d + 1][t], break_var});
builder.AddBoolOr(
{Not(at_home[d][t]), at_home[d + 1][t], Not(break_var)});
builder.AddBoolOr(
{at_home[d][t], Not(at_home[d + 1][t]), Not(break_var)});
breaks.push_back(break_var);
}
}
builder.AddGreaterOrEqual(LinearExpr::BooleanSum(breaks), 2 * num_teams - 4);
builder.Minimize(LinearExpr::BooleanSum(breaks));
Model model;
if (!FLAGS_params.empty()) {
model.Add(NewSatParameters(FLAGS_params));
}
const CpSolverResponse response = SolveCpModel(builder.Build(), &model);
LOG(INFO) << CpSolverResponseStats(response);
}
} // namespace sat
} // namespace operations_research
static const char kUsage[] =
"Usage: see flags.\nThis program runs a sports scheduling problem."
"There is no output besides the debug LOGs of the solver.";
int main(int argc, char **argv) {
gflags::SetUsageMessage(kUsage);
gflags::ParseCommandLineFlags(&argc, &argv, true);
CHECK_EQ(0, FLAGS_num_teams % 2) << "The number of teams must be even";
CHECK_GE(FLAGS_num_teams, 2) << "At least 2 teams";
operations_research::sat::SecondModel(FLAGS_num_teams);
return EXIT_SUCCESS;
}
You can’t perform that action at this time.