First Stab at CP for SR (stable roommates) ------------------------------------------ The model is based on the binary constraint proposed in SARA 2005 and IJCAI2005 and CPAIOR-2014 The cost is O(n^3) for the binary constraint models. The binary constraint is posted between all pairs of agents that find each other acceptable in a stable roommates instance where preference lists may be incomplete (i.e. SRI). The n-ary constraint is a single object posted over the array of agents and is O(n^2) complexity (optimal) Directories ----------- codeyyyymmdd is where the java source files reside data contains stable roommates problem instance choco is where choco jar file has been placed choco ----- The choco constraint programming toolkit is used, consequently choco-solver-2.1.5.jar must be in the classpath. This has been placed into the choco directory The Models ---------- We have 2 models: (a) SR: using toolkit constraints and enumerated domained variables. (b) SRNary: using the specialized n-ary constraint. All the models have a constrained integer variable for each agent, with a domain of ranks 0 to L_i, where L_i is the length of agent_i preference list. If the agent is assigned the value n this means the agent_i is matched to agent_i. Internally, ranks run from 0 to n, as do agent indices, therefore everything is shifted down one to zero. To Run ------ To get a first solution >> java SR* fname option where SR* is SR or SRNary, fname is the filename of an problem instance and option is one of first, all, count or propagation. NOTE: if the option is omitted then it defaults to first. The Output ---------- For the following options we get the following output first: a solution is delivered as a list of pairs followed by run time statistics all: all solutions are output plus run time statistics count: the number of solutions are output and runtime statistics propagate: the phase1 table is output with restricted runtime statistics Run Time Statistics ------------------- For options all, first and count nodes: number of "decisions" made by choco modelTime: time to create the model solveTime: time spent searching for solutions totalTime: time to read, model and solve modelSize: the size of the model in kilobytes When option is propagate nodes and solveTime are omitted To Generate Random Problem Instances ----------------------------------- Use the program RandomRoommate >> java RandomRoommate 20 will output a random instance with n=20 >> java RandomRoomate 20 0.5 will output a random instances of a stable roommates problem with incomplete preference lists, where the probability of an agent occurring in a preference list is 0.5 Examples -------- From within the code directory >> java SRNary ../data/sr10.txt all (1,7) (2,3) (4,9) (5,10) (6,8) (1,7) (2,8) (3,5) (4,9) (6,10) (1,7) (2,8) (3,6) (4,9) (5,10) (1,4) (2,8) (3,6) (5,7) (9,10) (1,4) (2,9) (3,6) (5,7) (8,10) (1,4) (2,3) (5,7) (6,8) (9,10) (1,3) (2,4) (5,7) (6,8) (9,10) nodes: 12 modelTime: 161 solveTime: 16 totalTime: 212 modelSize: 7735 >> java SRNary ../data/sr10.txt propagate 1: 8 2 3 6 4 7 2: 4 3 8 9 5 1 10 6 3: 5 6 2 1 7 10 4: 9 1 6 2 5: 7 10 8 2 6 3 6: 2 8 3 4 10 1 5 9 7: 1 8 3 5 8: 10 2 5 6 7 1 9: 6 2 10 4 10: 3 6 5 2 9 8 modelTime: 163 totalTime: 201 modelSize: 7735 NOTE ---- The code also works for stable roommates ... just make an SRI instance that is bipartite Mac? --- See Martin Van der Linden's blog https://martinvdlinden.wordpress.com/2016/04/01/finding-all-stable-matchings-in-roommate-and-marriage-problems/ Patrick Prosser 04/04/2016