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 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
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=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()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.create_phase().time_limit=int(sys.argv[3])else:ls.create_phase().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):if(x[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(fileName.c_str());if(!infile.is_open()){cerr<<"File "<<fileName<<" cannot be opened."<<endl;exit(1);}infile>>nbGroups;infile>>groupSize;infile>>nbWeeks;infile.close();nbGolfers=nbGroups*groupSize;}/* Declares the optimization model. */voidsolve(intlimit){try{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. */LSPhasephase=localsolver.createPhase();phase.setTimeLimit(limit);localsolver.solve();}catch(constLSException&e){cout<<"LSException:"<<e.getMessage()<<endl;exit(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).voidwriteSolution(conststring&fileName){ofstreamoutfile(fileName.c_str());if(!outfile.is_open()){cerr<<"File "<<fileName<<" cannot be opened."<<endl;exit(1);}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;}outfile.close();}};intmain(intargc,char**argv){if(argc<2){cout<<"Usage: solcial_golfer inputFile [outputFile] [timeLimit]"<<endl;exit(1);}constchar*instanceFile=argv[1];constchar*solFile=argc>2?argv[2]:NULL;constchar*strTimeLimit=argc>3?argv[3]:"10";SocialGolfermodel;model.readInstance(instanceFile);model.solve(atoi(strTimeLimit));if(solFile!=NULL)model.writeSolution(solFile);return0;}
/********** SocialGolfer.java **********/importjava.util.*;importjava.io.*;importlocalsolver.*;publicclassSocialGolfer{/* Number of groups */intnbGroups;/* Size of each group */intgroupSize;/* Number of week */intnbWeeks;/* Number of golfers */intnbGolfers;/* Objective */LSExpressionobj;/* LocalSolver. */LocalSolverlocalsolver;/* Decisions variables */LSExpression[][][]x;/* Reads instance data */voidreadInstance(StringfileName){try{Scannerinput=newScanner(newFile(fileName));nbGroups=input.nextInt();groupSize=input.nextInt();nbWeeks=input.nextInt();input.close();}catch(IOExceptionex){ex.printStackTrace();}nbGolfers=nbGroups*groupSize;}/* Declares the optimization model. */voidsolve(intlimit){try{localsolver=newLocalSolver();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. */LSPhasephase=localsolver.createPhase();phase.setTimeLimit(limit);localsolver.solve();}catch(LSExceptione){System.out.println("LSException:"+e.getMessage());System.exit(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).*/voidwriteSolution(StringfileName){try{BufferedWriteroutput=newBufferedWriter(newFileWriter(fileName));output.write(obj.getValue()+"\n");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.write("\n");}output.write("\n");}output.close();}catch(IOExceptionex){ex.printStackTrace();}}publicstaticvoidmain(String[]args){if(args.length<1){System.out.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";SocialGolfermodel=newSocialGolfer();model.readInstance(instanceFile);model.solve(Integer.parseInt(strTimeLimit));if(outputFile!=null){model.writeSolution(outputFile);}}}
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc SocialGolfer.cs /reference:localsolvernet.dll
SocialGolfer instances\c_4_3_3.in
/********** SocialGolfer.cs **********/usingSystem;usingSystem.IO;usingSystem.Collections.Generic;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(){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. */LSPhasephase=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). */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]");System.Environment.Exit(1);}stringinstanceFile=args[0];stringoutputFile=args.Length>1?args[1]:null;stringstrTimeLimit=args.Length>2?args[2]:"10";SocialGolfermodel=newSocialGolfer();model.ReadInstance(instanceFile);model.Solve(int.Parse(strTimeLimit));if(outputFile!=null)model.WriteSolution(outputFile);}}
Social golfer¶
Principles learned¶
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
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)
.