This page is for an old version of Hexaly Optimizer.
We recommend that you update your version and read the documentation for the
latest stable release.
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.
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).
/********** social_golfer.lsp **********/useio;/* Reads instance data. */functioninput(){localusage="\nUsage: localsolver social_golfer.lsp "+"inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]\n";if(inFileName==nil)throwusage;localinFile=io.openRead(inFileName);nbGroups=inFile.readInt();groupSize=inFile.readInt();nbWeeks=inFile.readInt();}/* Declares the optimization model. */functionmodel(){// 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 groupfor[win1..nbWeeks][gfin1..nbGolfers]constraintsum[grin1..nbGroups](x[w][gr][gf])==1;// each week, each group contains exactly groupSize golfersfor[win1..nbWeeks][grin1..nbGroups]constraintsum[gfin1..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[win1..nbWeeks][grin1..nbGroups][gf0in1..nbGolfers][gf1ingf0+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 groupsfor[gf0in1..nbGolfers][gf1ingf0+1..nbGolfers]{nb_meetings[gf0][gf1]<-sum[win1..nbWeeks][grin1..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 meetingsobj<-sum[gf0in1..nbGolfers][gf1ingf0+1..nbGolfers](redundant_meetings[gf0][gf1]);minimizeobj;}/* Parameterizes the solver. */functionparam(){if(lsTimeLimit==nil)lsTimeLimit=10;if(lsNbThreads==nil)lsNbThreads=1;}/* 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). */functionoutput(){if(solFileName==nil)return;localsolution=io.openWrite(solFileName);solution.println(obj.value);for[win1..nbWeeks]{for[grin1..nbGroups]{for[gfin1..nbGolfers]{if(x[w][gr][gf].value==true){solution.print(gf-1," ");}}solution.println();}solution.println();}}
########## social_golfer.py ##########importlocalsolverimportsysiflen(sys.argv)<2:print("Usage: python social_golfer.py inputFile [outputFile] [timeLimit]")sys.exit(1)defread_integers(filename):withopen(filename)asf:return[int(elem)foreleminf.read().split()]withlocalsolver.LocalSolver()asls:## Reads instance data#file_it=iter(read_integers(sys.argv[1]))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()forgfinrange(nb_golfers)]forgrinrange(nb_groups)]forwinrange(nb_weeks)]# each week, each golfer is assigned to exactly one groupforwinrange(nb_weeks):forgfinrange(nb_golfers):model.constraint(model.eq(model.sum(x[w][gr][gf]forgrinrange(nb_groups)),1))# each week, each group contains exactly group_size golfersforwinrange(nb_weeks):forgrinrange(nb_groups):model.constraint(model.eq(model.sum(x[w][gr][gf]forgfinrange(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_weeksforwinrange(nb_weeks):meetings[w]=[None]*nb_groupsforgrinrange(nb_groups):meetings[w][gr]=[None]*nb_golfersforgf0inrange(nb_golfers):meetings[w][gr][gf0]=[None]*nb_golfersforgf1inrange(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 groupsredundant_meetings=[None]*nb_golfersforgf0inrange(nb_golfers):redundant_meetings[gf0]=[None]*nb_golfersforgf1inrange(gf0+1,nb_golfers):nb_meetings=model.sum(meetings[w][gr][gf0][gf1]forwinrange(nb_weeks)forgrinrange(nb_groups))redundant_meetings[gf0][gf1]=model.max(nb_meetings-1,0)# the goal is to minimize the number of redundant meetingsobj=model.sum(redundant_meetings[gf0][gf1]forgf0inrange(nb_golfers)forgf1inrange(gf0+1,nb_golfers))model.minimize(obj)model.close()## Parameterizes the solver#ls.param.nb_threads=1iflen(sys.argv)>=4:ls.param.time_limit=int(sys.argv[3])else:ls.param.time_limit=10ls.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).#iflen(sys.argv)>=3:withopen(sys.argv[2],'w')asf:f.write("%d\n"%obj.value)forwinrange(nb_weeks):forgrinrange(nb_groups):forgfinrange(nb_golfers):ifx[w][gr][gf].value:f.write("%d "%(gf))f.write("\n")f.write("\n")
//********* social_golfer.cpp *********#include<iostream>#include<sstream>#include<fstream>#include<vector>#include"localsolver.h"usingnamespacelocalsolver;usingnamespacestd;classSocialGolfer{public:// Number of groups lsintnbGroups;// Size of each group lsintgroupSize;// Number of week lsintnbWeeks;// Number of golfers lsintnbGolfers;// Objective LSExpressionobj;// LocalSolver. LocalSolverlocalsolver;// Decisions variables vector<vector<vector<LSExpression>>>x;// Reads instance data voidreadInstance(conststring&fileName){ifstreaminfile;infile.exceptions(ifstream::failbit|ifstream::badbit);infile.open(fileName.c_str());infile>>nbGroups;infile>>groupSize;infile>>nbWeeks;infile.close();nbGolfers=nbGroups*groupSize;}// Declares the optimization model. voidsolve(intlimit){LSModelmodel=localsolver.getModel();// Decision variables// 0-1 decisions variables: x[w][gr][gf]=1 if golfer gf is in group gr on week wx.resize(nbWeeks);for(intw=0;w<nbWeeks;w++){x[w].resize(nbGroups);for(intgr=0;gr<nbGroups;gr++){x[w][gr].resize(nbGolfers);for(intgf=0;gf<nbGolfers;gf++){x[w][gr][gf]=model.boolVar();}}}// each week, each golfer is assigned to exactly one groupfor(intw=0;w<nbWeeks;w++){for(intgf=0;gf<nbGolfers;gf++){LSExpressionnbGroupsAssigned=model.sum();for(intgr=0;gr<nbGroups;gr++){nbGroupsAssigned+=x[w][gr][gf];}model.constraint(nbGroupsAssigned==1);}}// each week, each group contains exactly groupSize golfersfor(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){LSExpressionnbGolfersInGroup=model.sum();for(intgf=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(intw=0;w<nbWeeks;w++){meetings[w].resize(nbGroups);for(intgr=0;gr<nbGroups;gr++){meetings[w][gr].resize(nbGolfers);for(intgf0=0;gf0<nbGolfers;gf0++){meetings[w][gr][gf0].resize(nbGolfers);for(intgf1=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 groupsvector<vector<LSExpression>>redundantMeetings;redundantMeetings.resize(nbGolfers);for(intgf0=0;gf0<nbGolfers;gf0++){redundantMeetings[gf0].resize(nbGolfers);for(intgf1=gf0+1;gf1<nbGolfers;gf1++){LSExpressionnbMeetings=model.sum();for(intw=0;w<nbWeeks;w++){for(intgr=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 meetingsobj=model.sum();for(intgf0=0;gf0<nbGolfers;gf0++){for(intgf1=gf0+1;gf1<nbGolfers;gf1++){obj+=redundantMeetings[gf0][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).voidwriteSolution(conststring&fileName){ofstreamoutfile;outfile.exceptions(ofstream::failbit|ofstream::badbit);outfile.open(fileName.c_str());outfile<<obj.getValue()<<endl;for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){for(intgf=0;gf<nbGolfers;gf++){if(x[w][gr][gf].getValue()){outfile<<gf<<" ";}}outfile<<endl;}outfile<<endl;}}};intmain(intargc,char**argv){if(argc<2){cerr<<"Usage: solcial_golfer inputFile [outputFile] [timeLimit]"<<endl;return1;}constchar*instanceFile=argv[1];constchar*solFile=argc>2?argv[2]:NULL;constchar*strTimeLimit=argc>3?argv[3]:"10";try{SocialGolfermodel;model.readInstance(instanceFile);model.solve(atoi(strTimeLimit));if(solFile!=NULL)model.writeSolution(solFile);return0;}catch(constexception&e){cerr<<"An error occurred: "<<e.what()<<endl;return1;}}
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc SocialGolfer.cs /reference:localsolvernet.dll
SocialGolfer instances\c_4_3_3.in
/********** SocialGolfer.cs **********/usingSystem;usingSystem.IO;usinglocalsolver;publicclassSocialGolfer:IDisposable{// Number of groupsintnbGroups;// Size of each groupintgroupSize;// Number of weekintnbWeeks;// Number of golfersintnbGolfers;// SolverLocalSolverlocalsolver;// ObjectiveLSExpressionobj;// Decisions variablesLSExpression[,,]x;publicSocialGolfer(){localsolver=newLocalSolver();}// Reads instance data.publicvoidReadInstance(stringfileName){using(StreamReaderinput=newStreamReader(fileName)){vartokens=input.ReadLine().Split(' ');nbGroups=int.Parse(tokens[0]);groupSize=int.Parse(tokens[1]);nbWeeks=int.Parse(tokens[2]);}nbGolfers=nbGroups*groupSize;}publicvoidDispose(){if(localsolver!=null)localsolver.Dispose();}// Declares the optimization model.publicvoidSolve(intlimit){LSModelmodel=localsolver.GetModel();// Decision variables// 0-1 decisions variables: x[w,gr,gf]=1 if golfer gf is in group gr on week wx=newLSExpression[nbWeeks,nbGroups,nbGolfers];for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){for(intgf=0;gf<nbGolfers;gf++){x[w,gr,gf]=model.Bool();}}}// each week, each golfer is assigned to exactly one groupfor(intw=0;w<nbWeeks;w++){for(intgf=0;gf<nbGolfers;gf++){LSExpressionnbGroupsAssigned=model.Sum();for(intgr=0;gr<nbGroups;gr++){nbGroupsAssigned.AddOperand(x[w,gr,gf]);}model.Constraint(nbGroupsAssigned==1);}}// each week, each group contains exactly groupSize golfersfor(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){LSExpressionnbGolfersInGroup=model.Sum();for(intgf=0;gf<nbGolfers;gf++){nbGolfersInGroup.AddOperand(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.LSExpression[,,,]meetings=newLSExpression[nbWeeks,nbGroups,nbGolfers,nbGolfers];for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){for(intgf0=0;gf0<nbGolfers;gf0++){for(intgf1=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 groupsLSExpression[,]redundantMeetings=newLSExpression[nbGolfers,nbGolfers];for(intgf0=0;gf0<nbGolfers;gf0++){for(intgf1=gf0+1;gf1<nbGolfers;gf1++){LSExpressionnbMeetings=model.Sum();for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){nbMeetings.AddOperand(meetings[w,gr,gf0,gf1]);}}redundantMeetings[gf0,gf1]=model.Max(nbMeetings-1,0);}}// the goal is to minimize the number of redundant meetingsobj=model.Sum();for(intgf0=0;gf0<nbGolfers;gf0++){for(intgf1=gf0+1;gf1<nbGolfers;gf1++){obj.AddOperand(redundantMeetings[gf0,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).publicvoidWriteSolution(stringfileName){using(StreamWriteroutput=newStreamWriter(fileName)){output.WriteLine(obj.GetValue());for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){for(intgf=0;gf<nbGolfers;gf++){if(x[w,gr,gf].GetValue()==1)output.Write(gf+" ");}output.WriteLine();}output.WriteLine();}}}publicstaticvoidMain(string[]args){if(args.Length<1){Console.WriteLine("Usage: SocialGolfer inputFile [solFile] [timeLimit]");Environment.Exit(1);}stringinstanceFile=args[0];stringoutputFile=args.Length>1?args[1]:null;stringstrTimeLimit=args.Length>2?args[2]:"10";using(SocialGolfermodel=newSocialGolfer()){model.ReadInstance(instanceFile);model.Solve(int.Parse(strTimeLimit));if(outputFile!=null)model.WriteSolution(outputFile);}}}
/********** SocialGolfer.java **********/importjava.util.*;importjava.io.*;importlocalsolver.*;publicclassSocialGolfer{// Number of groupsprivateintnbGroups;// Size of each groupprivateintgroupSize;// Number of weekprivateintnbWeeks;// Number of golfersprivateintnbGolfers;// ObjectiveprivateLSExpressionobj;// LocalSolver.privatefinalLocalSolverlocalsolver;// Decisions variablesprivateLSExpression[][][]x;privateSocialGolfer(LocalSolverlocalsolver){this.localsolver=localsolver;}// Reads instance dataprivatevoidreadInstance(StringfileName)throwsIOException{try(Scannerinput=newScanner(newFile(fileName))){nbGroups=input.nextInt();groupSize=input.nextInt();nbWeeks=input.nextInt();}nbGolfers=nbGroups*groupSize;}// Declares the optimization model.privatevoidsolve(intlimit){LSModelmodel=localsolver.getModel();x=newLSExpression[nbWeeks][nbGroups][nbGolfers];// Decision variables// 0-1 decisions variables: x[w][gr][gf]=1 if golfer gf is in group gr on week wfor(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){for(intgf=0;gf<nbGolfers;gf++){x[w][gr][gf]=model.boolVar();}}}// each week, each golfer is assigned to exactly one groupfor(intw=0;w<nbWeeks;w++){for(intgf=0;gf<nbGolfers;gf++){LSExpressionnbGroupsAssigned=model.sum();for(intgr=0;gr<nbGroups;gr++){nbGroupsAssigned.addOperand(x[w][gr][gf]);}model.constraint(model.eq(nbGroupsAssigned,1));}}// each week, each group contains exactly groupSize golfersfor(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){LSExpressionnbGolfersInGroup=model.sum();for(intgf=0;gf<nbGolfers;gf++){nbGolfersInGroup.addOperand(x[w][gr][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=newLSExpression[nbWeeks][nbGroups][nbGolfers][nbGolfers];for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){for(intgf0=0;gf0<nbGolfers;gf0++){for(intgf1=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 groupsLSExpression[][]redundantMeetings;redundantMeetings=newLSExpression[nbGolfers][nbGolfers];for(intgf0=0;gf0<nbGolfers;gf0++){for(intgf1=gf0+1;gf1<nbGolfers;gf1++){LSExpressionnbMeetings=model.sum();for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){nbMeetings.addOperand(meetings[w][gr][gf0][gf1]);}}redundantMeetings[gf0][gf1]=model.max(model.sub(nbMeetings,1),0);}}// the goal is to minimize the number of redundant meetingsobj=model.sum();for(intgf0=0;gf0<nbGolfers;gf0++){for(intgf1=gf0+1;gf1<nbGolfers;gf1++){obj.addOperand(redundantMeetings[gf0][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).privatevoidwriteSolution(StringfileName)throwsIOException{try(PrintWriteroutput=newPrintWriter(fileName)){output.println(obj.getValue());for(intw=0;w<nbWeeks;w++){for(intgr=0;gr<nbGroups;gr++){for(intgf=0;gf<nbGolfers;gf++){if(x[w][gr][gf].getValue()==1){output.print(gf+" ");}}output.println();}output.println();}}}publicstaticvoidmain(String[]args){if(args.length<1){System.err.println("Usage: java SocialGolfer inputFile [outputFile] [timeLimit]");System.exit(1);}StringinstanceFile=args[0];StringoutputFile=args.length>1?args[1]:null;StringstrTimeLimit=args.length>2?args[2]:"10";try(LocalSolverlocalsolver=newLocalSolver()){SocialGolfermodel=newSocialGolfer(localsolver);model.readInstance(instanceFile);model.solve(Integer.parseInt(strTimeLimit));if(outputFile!=null){model.writeSolution(outputFile);}}catch(Exceptionex){System.err.println(ex);ex.printStackTrace();System.exit(1);}}}
Social golfer¶
Principles learned¶
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.
Download the exampleData¶
Each data file is made of only three numbers:
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 innbMeetings[gf0][gf1]
. Finally the number of redundant meetings for a pair of golfers ismax(0,nbMeetings[gf0][gf1]-1)
.