# Social Golfer¶

## Principles learned¶

• Create a generic model that uses data
• Use of n-ary operator “and”

## Problem¶ In a golf club, there are 32 social golfers, each of whom plays golf once a week, and always in groups of 4. The problem is to build a schedule of play for 10 weeks with maximum socialisation; that is, as few repeated meetings as possible. More generally the problem is to schedule m groups of n golfers over p weeks, with maximum socialisation. The complexity of the problem is unknown. The instance mentioned has a known solution with no repeated meeting. For more details see CSPLib or MathPuzzle.

## Data¶

Each data file is made of only three numbers:

• the number of groups
• the size of groups
• the number of weeks

## Program¶

The decisions variables are binaries x[w][gr][gf], equal to 1 if golfer gf is in group gr on week w. Then, the number of meetings between each pair of golfers is computed in nbMeetings[gf0][gf1]. Finally the number of redundant meetings for a pair of golfers is max(0,nbMeetings[gf0][gf1]-1).

Execution:
localsolver social_golfer.lsp inFileName=instances/c_4_3_3.in [lsTimeLimit=] [solFileName=]
/********** social_golfer.lsp **********/

use io;

function input() {
local usage = "\nUsage: localsolver social_golfer.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]\n";

if (inFileName == nil) throw usage;

}

/* Declares the optimization model. */
function model() {

// the number of golfers
nbGolfers = nbGroups*groupSize;

// 0-1 decisions variables: x[w][gr][gf]=1 if golfer gf is in group gr on week w.
x[1..nbWeeks][1..nbGroups][1..nbGolfers] <- bool();

// each week, each golfer is assigned to exactly one group
for[w in 1..nbWeeks][gf in 1..nbGolfers]
constraint sum[gr in 1..nbGroups](x[w][gr][gf]) == 1;

// each week, each group contains exactly groupSize golfers
for[w in 1..nbWeeks][gr in 1..nbGroups]
constraint sum[gf in 1..nbGolfers](x[w][gr][gf]) == groupSize;

// golfers gf0 and gf1 meet in group gr on week w if both are assigned to this group for week w.
meetings[w in 1..nbWeeks][gr in 1..nbGroups][gf0 in 1..nbGolfers][gf1 in gf0+1..nbGolfers]
<- and(x[w][gr][gf0], x[w][gr][gf1]);

// the number of meetings of golfers gf0 and gf1 is the sum of their meeting variables over all weeks and groups
for[gf0 in 1..nbGolfers][gf1 in gf0+1..nbGolfers] {
nb_meetings[gf0][gf1] <- sum[w in 1..nbWeeks][gr in 1..nbGroups](meetings[w][gr][gf0][gf1]);
redundant_meetings[gf0][gf1] <- max(nb_meetings[gf0][gf1] -1, 0);
}

// the goal is to minimize the number of redundant meetings
obj <- sum[gf0 in 1..nbGolfers][gf1 in gf0+1..nbGolfers](redundant_meetings[gf0][gf1]);
minimize obj;
}

/* Parameterizes the solver. */
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 10;
}

/* Writes the solution in a file following the following format:
* - the objective value
* - for each week and each group, write the golfers of the group
* (nbWeeks x nbGroupes lines of groupSize numbers).
*/
function output() {
if (solFileName == nil) return;
local solution = io.openWrite(solFileName);
solution.println(obj.value);
for [w in 1..nbWeeks]{
for [gr in 1..nbGroups]{
for [gf in 1..nbGolfers] {
if (x[w][gr][gf].value==true) {
solution.print(gf-1, " ");
}
}
solution.println();
}
solution.println();
}
}

Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python social_golfer.py instances\c_4_3_3.in
Execution (Linux)
export PYTHONPATH=/opt/localsolver_10_5/bin/python
python social_golfer.py instances/c_4_3_3.in
########## social_golfer.py ##########

import localsolver
import sys

if len(sys.argv) < 2:
print("Usage: python social_golfer.py inputFile [outputFile] [timeLimit]")
sys.exit(1)

with open(filename) as f:
return [int(elem) for elem in f.read().split()]

with localsolver.LocalSolver() as ls:

#
#
nb_groups = next(file_it)
group_size = next(file_it)
nb_weeks = next(file_it)
nb_golfers = nb_groups*group_size

#
# Declares the optimization model
#
model = ls.model

# 0-1 decisions variables: x[w][gr][gf]=1 if golfer gf is in group gr on week w.
x = [[[model.bool() for gf in range(nb_golfers)] for gr in range(nb_groups)] for w in range(nb_weeks)]

# each week, each golfer is assigned to exactly one group
for w in range(nb_weeks):
for gf in range(nb_golfers):
model.constraint(model.eq(model.sum(x[w][gr][gf] for gr in range(nb_groups)), 1))

# each week, each group contains exactly group_size golfers
for w in range(nb_weeks):
for gr in range(nb_groups):
model.constraint(model.eq(model.sum(x[w][gr][gf] for gf in range(nb_golfers)), group_size))

# golfers gf0 and gf1 meet in group gr on week w if both are assigned to this group for week w.
meetings = [None]*nb_weeks
for w in range(nb_weeks):
meetings[w] = [None]*nb_groups
for gr in range(nb_groups):
meetings[w][gr] = [None]*nb_golfers
for gf0 in range(nb_golfers):
meetings[w][gr][gf0] = [None]*nb_golfers
for gf1 in range(gf0+1, nb_golfers):
meetings[w][gr][gf0][gf1] = model.and_(x[w][gr][gf0], x[w][gr][gf1])

# the number of meetings of golfers gf0 and gf1 is the sum of their meeting variables over all weeks and groups
redundant_meetings = [None]*nb_golfers
for gf0 in range(nb_golfers):
redundant_meetings[gf0] = [None]*nb_golfers
for gf1 in range(gf0+1, nb_golfers):
nb_meetings = model.sum(meetings[w][gr][gf0][gf1] for w in range(nb_weeks) for gr in range(nb_groups))
redundant_meetings[gf0][gf1] = model.max(nb_meetings - 1, 0)

# the goal is to minimize the number of redundant meetings
obj = model.sum(redundant_meetings[gf0][gf1] for gf0 in range(nb_golfers) for gf1 in range(gf0+1, nb_golfers))
model.minimize(obj)

model.close()

#
# Parameterizes the solver
#
if len(sys.argv) >= 4: ls.param.time_limit = int(sys.argv)
else: ls.param.time_limit = 10

ls.solve()

# Writes the solution in a file following the following format:
# - the objective value
# - for each week and each group, write the golfers of the group
# (nb_weeks x nbGroupes lines of group_size numbers).
#
if len(sys.argv) >= 3:
with open(sys.argv, 'w') as f:
f.write("%d\n" % obj.value)
for w in range(nb_weeks):
for gr in range(nb_groups):
for gf in range(nb_golfers):
if x[w][gr][gf].value:
f.write("%d " % (gf))
f.write("\n")
f.write("\n")

Compilation / Execution (Windows)
cl /EHsc social_golfer.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver105.lib
social_golfer instances\c_4_3_3.in
Compilation / Execution (Linux)
g++ social_golfer.cpp -I/opt/localsolver_10_5/include -llocalsolver105 -lpthread -o social_golfer
./social_golfer instances/c_4_3_3.in
//********* social_golfer.cpp *********

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

class SocialGolfer{
public:

// Number of groups
lsint nbGroups;
// Size of each group
lsint groupSize;
// Number of week
lsint nbWeeks;
// Number of golfers
lsint nbGolfers;

// Objective
LSExpression obj;

// LocalSolver.
LocalSolver localsolver;

// Decisions variables
vector< vector< vector< LSExpression > > > x;

void readInstance(const string & fileName) {
ifstream infile;
infile.open(fileName.c_str());

infile >> nbGroups;
infile >> groupSize;
infile >> nbWeeks;
infile.close();

nbGolfers = nbGroups*groupSize;
}

// Declares the optimization model.
void solve(int limit) {
LSModel model = localsolver.getModel();

// Decision variables
// 0-1 decisions variables: x[w][gr][gf]=1 if golfer gf is in group gr on week w
x.resize(nbWeeks);
for (int w = 0; w < nbWeeks; w++) {
x[w].resize(nbGroups);
for (int gr = 0; gr < nbGroups; gr++) {
x[w][gr].resize(nbGolfers);
for (int gf = 0; gf < nbGolfers; gf++) {
x[w][gr][gf]=model.boolVar();
}
}
}

// each week, each golfer is assigned to exactly one group
for (int w = 0; w < nbWeeks; w++) {
for (int gf = 0; gf < nbGolfers; gf++) {
LSExpression nbGroupsAssigned = model.sum();
for (int gr = 0; gr < nbGroups; gr++) {
}
model.constraint(nbGroupsAssigned == 1);
}
}

// each week, each group contains exactly groupSize golfers
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
LSExpression nbGolfersInGroup = model.sum();
for (int gf = 0; gf < nbGolfers; gf++) {
}
model.constraint(nbGolfersInGroup == groupSize);
}
}

// golfers gf0 and gf1 meet in group gr on week w if both are assigned to this group for week w.
vector< vector< vector< vector< LSExpression > > > > meetings;
meetings.resize(nbWeeks);
for (int w = 0; w < nbWeeks; w++) {
meetings[w].resize(nbGroups);
for (int gr = 0; gr < nbGroups; gr++) {
meetings[w][gr].resize(nbGolfers);
for (int gf0 = 0; gf0 < nbGolfers; gf0++) {
meetings[w][gr][gf0].resize(nbGolfers);
for (int gf1 = gf0+1; gf1 < nbGolfers; gf1++) {
meetings[w][gr][gf0][gf1] = model.and_(x[w][gr][gf0], x[w][gr][gf1]);
}
}
}
}

// the number of meetings of golfers gf0 and gf1 is the sum of their meeting variables over all weeks and groups
vector< vector< LSExpression> > redundantMeetings;
redundantMeetings.resize(nbGolfers);
for (int gf0 = 0; gf0 < nbGolfers; gf0++) {
redundantMeetings[gf0].resize(nbGolfers);
for (int gf1 = gf0+1; gf1 < nbGolfers; gf1++) {
LSExpression nbMeetings = model.sum();
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
}
}
redundantMeetings[gf0][gf1] = model.max(nbMeetings -1, 0);
}
}

// the goal is to minimize the number of redundant meetings
obj = model.sum();
for (int gf0 = 0; gf0 < nbGolfers; gf0++) {
for (int gf1 = gf0+1; gf1 < nbGolfers; gf1++) {
}
}
model.minimize(obj);

model.close();
// Parameterizes the solver.
localsolver.getParam().setTimeLimit(limit);

localsolver.solve();
}

// Writes the solution in a file following the following format:
//  - the objective value
//  - for each week and each group, write the golfers of the group
// (nbWeeks x nbGroupes lines of groupSize numbers).
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());

outfile << obj.getValue() << endl;
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
for (int gf = 0; gf < nbGolfers; gf++) {
if (x[w][gr][gf].getValue()) {
outfile << gf << " ";
}
}
outfile << endl;
}
outfile << endl;
}
}
};

int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: solcial_golfer inputFile [outputFile] [timeLimit]" << endl;
return 1;
}

const char* instanceFile = argv;
const char* solFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "10";

try {
SocialGolfer model;
model.solve(atoi(strTimeLimit));
if (solFile != NULL) model.writeSolution(solFile);
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}

Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc SocialGolfer.cs /reference:localsolvernet.dll
SocialGolfer instances\c_4_3_3.in
/********** SocialGolfer.cs **********/

using System;
using System.IO;
using localsolver;

public class SocialGolfer : IDisposable
{
// Number of groups
int nbGroups;
// Size of each group
int groupSize;
// Number of week
int nbWeeks;
// Number of golfers
int nbGolfers;

// Solver
LocalSolver localsolver;

// Objective
LSExpression obj;

// Decisions variables
LSExpression[,,] x;

public SocialGolfer()
{
localsolver = new LocalSolver();
}

{
{
nbGroups = int.Parse(tokens);
groupSize = int.Parse(tokens);
nbWeeks = int.Parse(tokens);
}
nbGolfers = nbGroups * groupSize;
}

public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}

// Declares the optimization model.
public void Solve(int limit)
{
LSModel model = localsolver.GetModel();

// Decision variables
// 0-1 decisions variables: x[w,gr,gf]=1 if golfer gf is in group gr on week w
x = new LSExpression[nbWeeks, nbGroups, nbGolfers];
for (int w = 0; w < nbWeeks; w++)
{
for (int gr = 0; gr < nbGroups; gr++)
{
for (int gf = 0; gf < nbGolfers; gf++)
{
x[w, gr, gf] = model.Bool();
}
}
}

// each week, each golfer is assigned to exactly one group
for (int w = 0; w < nbWeeks; w++)
{
for (int gf = 0; gf < nbGolfers; gf++)
{
LSExpression nbGroupsAssigned = model.Sum();
for (int gr = 0; gr < nbGroups; gr++)
{
}
model.Constraint(nbGroupsAssigned == 1);
}
}

// each week, each group contains exactly groupSize golfers
for (int w = 0; w < nbWeeks; w++)
{
for (int gr = 0; gr < nbGroups; gr++)
{
LSExpression nbGolfersInGroup = model.Sum();
for (int gf = 0; gf < nbGolfers; gf++)
{
}
model.Constraint(nbGolfersInGroup == groupSize);
}
}

// golfers gf0 and gf1 meet in group gr on week w if both are assigned to this group for week w.
LSExpression[,,,] meetings = new LSExpression[nbWeeks, nbGroups, nbGolfers, nbGolfers];
for (int w = 0; w < nbWeeks; w++)
{
for (int gr = 0; gr < nbGroups; gr++)
{
for (int gf0 = 0; gf0 < nbGolfers; gf0++)
{
for (int gf1 = gf0 + 1; gf1 < nbGolfers; gf1++)
{
meetings[w, gr, gf0, gf1] = model.And(x[w, gr, gf0], x[w, gr, gf1]);
}
}
}
}

// the number of meetings of golfers gf0 and gf1 is the sum of their meeting variables over all weeks and groups
LSExpression[,] redundantMeetings = new LSExpression[nbGolfers, nbGolfers];
for (int gf0 = 0; gf0 < nbGolfers; gf0++)
{
for (int gf1 = gf0 + 1; gf1 < nbGolfers; gf1++)
{
LSExpression nbMeetings = model.Sum();
for (int w = 0; w < nbWeeks; w++)
{
for (int gr = 0; gr < nbGroups; gr++)
{
}
}
redundantMeetings[gf0, gf1] = model.Max(nbMeetings - 1, 0);
}
}

// the goal is to minimize the number of redundant meetings
obj = model.Sum();
for (int gf0 = 0; gf0 < nbGolfers; gf0++)
{
for (int gf1 = gf0 + 1; gf1 < nbGolfers; gf1++)
{
}
}
model.Minimize(obj);

model.Close();

// Parameterizes the solver.
localsolver.GetParam().SetTimeLimit(limit);
localsolver.Solve();
}

// Writes the solution in a file following the following format:
// - the objective value
// - for each week and each group, write the golfers of the group
// (nbWeeks x nbGroupes lines of groupSize numbers).
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(obj.GetValue());
for (int w = 0; w < nbWeeks; w++)
{
for (int gr = 0; gr < nbGroups; gr++)
{
for (int gf = 0; gf < nbGolfers; gf++)
{
if (x[w, gr, gf].GetValue() == 1) output.Write(gf + " ");
}
output.WriteLine();
}
output.WriteLine();
}
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: SocialGolfer inputFile [solFile] [timeLimit]");
Environment.Exit(1);
}

string instanceFile = args;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "10";

using (SocialGolfer model = new SocialGolfer())
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}

Compilation / Execution (Windows)
javac SocialGolfer.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. SocialGolfer instances\c_4_3_3.in
Compilation / Execution (Linux)
javac SocialGolfer.java -cp /opt/localsolver_10_5/bin/localsolver.jar
java -cp /opt/localsolver_10_5/bin/localsolver.jar:. SocialGolfer instances/c_4_3_3.in
/********** SocialGolfer.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class SocialGolfer {
// Number of groups
private int nbGroups;
// Size of each group
private int groupSize;
// Number of week
private int nbWeeks;
// Number of golfers
private int nbGolfers;

// Objective
private LSExpression obj;

// LocalSolver.
private final LocalSolver localsolver;

// Decisions variables
private LSExpression[][][] x;

private SocialGolfer(LocalSolver localsolver) {
this.localsolver = localsolver;
}

private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
nbGroups = input.nextInt();
groupSize = input.nextInt();
nbWeeks = input.nextInt();
}
nbGolfers = nbGroups * groupSize;
}

// Declares the optimization model.
private void solve(int limit) {
LSModel model = localsolver.getModel();

x = new LSExpression[nbWeeks][nbGroups][nbGolfers];

// Decision variables
// 0-1 decisions variables: x[w][gr][gf]=1 if golfer gf is in group gr on week w
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
for (int gf = 0; gf < nbGolfers; gf++) {
x[w][gr][gf] = model.boolVar();
}
}
}

// each week, each golfer is assigned to exactly one group
for (int w = 0; w < nbWeeks; w++) {
for (int gf = 0; gf < nbGolfers; gf++) {
LSExpression nbGroupsAssigned = model.sum();
for (int gr = 0; gr < nbGroups; gr++) {
}
model.constraint(model.eq(nbGroupsAssigned, 1));
}
}

// each week, each group contains exactly groupSize golfers
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
LSExpression nbGolfersInGroup = model.sum();
for (int gf = 0; gf < nbGolfers; gf++) {
}
model.constraint(model.eq(nbGolfersInGroup, groupSize));
}
}

// golfers gf0 and gf1 meet in group gr on week w if both are assigned to this group for week w.
LSExpression[][][][] meetings = new LSExpression[nbWeeks][nbGroups][nbGolfers][nbGolfers];
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
for (int gf0 = 0; gf0 < nbGolfers; gf0++) {
for (int gf1 = gf0 + 1; gf1 < nbGolfers; gf1++) {
meetings[w][gr][gf0][gf1] = model.and(x[w][gr][gf0], x[w][gr][gf1]);
}
}
}
}

// the number of meetings of golfers gf0 and gf1 is the sum of their meeting variables over
// all weeks and groups
LSExpression[][] redundantMeetings;
redundantMeetings = new LSExpression[nbGolfers][nbGolfers];
for (int gf0 = 0; gf0 < nbGolfers; gf0++) {
for (int gf1 = gf0 + 1; gf1 < nbGolfers; gf1++) {
LSExpression nbMeetings = model.sum();
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
}
}
redundantMeetings[gf0][gf1] = model.max(model.sub(nbMeetings, 1), 0);
}
}

// the goal is to minimize the number of redundant meetings
obj = model.sum();
for (int gf0 = 0; gf0 < nbGolfers; gf0++) {
for (int gf1 = gf0 + 1; gf1 < nbGolfers; gf1++) {
}
}
model.minimize(obj);

model.close();

// Parameterizes the solver.
localsolver.getParam().setTimeLimit(limit);

localsolver.solve();
}

// Writes the solution in a file following the following format:
// - the objective value
// - for each week and each group, write the golfers of the group
// (nbWeeks x nbGroupes lines of groupSize numbers).
private void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
output.println(obj.getValue());
for (int w = 0; w < nbWeeks; w++) {
for (int gr = 0; gr < nbGroups; gr++) {
for (int gf = 0; gf < nbGolfers; gf++) {
if (x[w][gr][gf].getValue() == 1) {
output.print(gf + " ");
}
}
output.println();
}
output.println();
}
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java SocialGolfer inputFile [outputFile] [timeLimit]");
System.exit(1);
}

String instanceFile = args;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "10";

try (LocalSolver localsolver = new LocalSolver()) {
SocialGolfer model = new SocialGolfer(localsolver);