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 play 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\python27\
python social_golfer.py instances\c_4_3_3.in
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
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 = file_it.next()
group_size = file_it.next()
nb_weeks = file_it.next()
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.create_phase().time_limit = int(sys.argv[3])
else: ls.create_phase().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[2], '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\localsolver.dll.lib
social_golfer instances\c_4_3_3.in
Compilation / Execution (Linux)
g++ social_golfer.cpp -I/opt/localsolver_XXX/include -llocalsolver -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;

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++){
nbGroupsAssigned += x[w][gr][gf];
}
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++){
nbGolfersInGroup += x[w][gr][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++){
nbMeetings += meetings[w][gr][gf0][gf1];
}
}
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++){
obj += redundantMeetings[gf0][gf1];
}
}
model.minimize(obj);

model.close();
// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.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[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "10";

try {
SocialGolfer model;
model.solve(atoi(strTimeLimit));
if(solFile != NULL) model.writeSolution(solFile);
return 0;
} catch (const exception& e){
cerr << "Error occurred: " << e.what() << endl;
return 1;
}
}
```
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.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[0]);
groupSize = int.Parse(tokens[1]);
nbWeeks = int.Parse(tokens[2]);
}
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.
LSPhase phase = localsolver.CreatePhase();
phase.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[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "10";

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_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/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 LocalSolver localsolver;

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

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) {
localsolver = new LocalSolver();
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.
LSPhase phase = localsolver.createPhase();
phase.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[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "10";

try {
SocialGolfer model = new SocialGolfer();