Reducing the search space efficiently in clingo

Question

I am struggling to scale a constraint problem (it breaks down for large values and / or if I try to optimise instead of just looking for any solution). I've taken some steps to break the search space down based on advice from some previous questions but it's still stalling. Are there any more techniques that can help me optimise this computation?

%%% constants %%%
#const nRounds = 4.
#const nPlayers = 20.
#const nRooms = 4.
#const nDecks = 7.

player(1..nPlayers).
room(1..nRooms).
deck(1..nDecks).
writer(1,1;2,2;3,3;4,4).

% For reference - that's what I started with:
%nRounds { seat(Player, 1..nRooms, 1..nDecks) } nRounds :- player(Player).

% Now instead I'm using a few building blocks
% Each player shall only play nRounds decks
nRounds { what(Player, 1..nDecks) } nRounds :- player(Player).
% Each player shall only play in up to nRounds rooms.
1 { where(Player, 1..nRooms) } nRounds :- player(Player).
% For each deck, 3 or 4 players can play in each room.
3 { who(1..nPlayers, Room, Deck) } 4 :- room(Room), deck(Deck).
% Putting it all together, hopefully, this leads to fewer combinations than the original monolithic choice rule.
{ seat(Player, Room, Deck) } :- what(Player, Deck), where(Player, Room), who(Player, Room, Deck).

% A player can only play a deck in a single room.
:- seat(Player, Room1, Deck), seat(Player, Room2, Deck), Room1 != Room2.
% A player must play nRounds decks overall.
:- player(Player), #count { Room, Deck: seat(Player, Room, Deck) } != nRounds.
% Any deck in any room must be played by 3-4 players.
legal_player_count(3..4).
:- room(Room), deck(Deck),
  Players = #count { Player: seat(Player, Room, Deck) },
  Players > 0,
  not legal_player_count(Players).
% Writers cannot play their own decks.
:- writer(Player, Deck), seat(Player, _, Deck).
% At least one non-playing player per room.
:- deck(Deck),
  Playing = #count { Player, Room: seat(Player, Room, Deck) },
  Rooms = #count { Room: seat(_, Room, Deck) },
  nPlayers - Playing < Rooms.

%:- room(R1), deck(D), room(R2), X = #sum { P: seat(P, R1, D) }, Y = #sum { P: seat(P, R2, D) }, R1 > R2, X > Y.

#minimize { D: decks(D) }.

#show decks/1.
#show seat/3.
% #show common_games/3.

When, or if, this becomes manageable I am hoping to add more optimisation objectives to choose the best configurations along the lines of:

% Input points(P, R, D, X) to report points.
% winner(P, R, D) :- points(P, R, D, X), X = #max { Y : points(_, R, D, Y) }.
% Compute each player's rank based on each round:
% rank(P, D, R) :- points(P, Room, D, X), winner(Winner, Room, D), D_ = D - 1,
%   rank(P, D_, R_),
%   R = some_combination_of(X, P=Winner, R_).
% latest_rank(P, R) :- D = #max { DD: rank(P, DD, _) }, rank(P, D, R).

% Total number of decks played throughout the night (for minimisation?)
decks(Decks) :- Decks = #count { Deck: seat(_, _, Deck) }.
% Total number of games played together by the same players (for minimisation)
% The total sum of this predicate is invariant
% Minimisation should took place by a superlinear value (e.g. square)
common_games(Player1, Player2, Games) :-
  player(Player1), player(Player2), Player1 != Player2,
  Games = #count { Room, Deck:
    seat(Player1, Room, Deck),
    seat(Player2, Room, Deck)
  }, Games > 0.

% For example:
% common_game_penalty(X) :- X = #sum { Y*Y, P1, P2 : common_games(P1, P2, Y) }.

% Another rank-based penalty needs to be added once the rank mechanics are there

% Then the 2 types of penalties need to be combined and / or passed to the optimiser

Update - Problem description

• P players gather for a quiz night. D decks and R rooms are available to play.
• Each room can only ever host either 3 or 4 players (due to the rules of the game, not space).
• Each Deck is played at most once and is played in multiple rooms simultaneously - so in a sense Deck is kind of synonymous to "Round".
• Each player can only play the same Deck at most once.
• Each player only gets to play N times during the night (N is pretty much fixed and it's 4).
• So if 9 decks are played during the night (i.e. if there are lots of players present), each will play 4 out of these 9.
• Therefore, it is not necessary for each player to play in each "deck/round". In fact, for each deck there is a writer and it is usually one of the players present.
• Naturally, the writer cannot play their own deck so they have to stay out for that round. Additionally, for each deck/round, somebody must read the questions in each room so if 16 players are present and there are 4 rooms, it is impossible for all 16 players to play. It is possible to have 4 rooms with 3 players each (and the remaining 4 players read out the questions) or to have 3 rooms with 4 players each (with 3 players reading out the questions and 1 spectating).

Hopefully, this clears up the confusion, if not I can try to give more elaborate examples but basically, say if you have 4 rooms and 30 players:

• You pick 16 who'll play and 4 more who'll read out the questions
• Then you have 16 people who played their 1/4 deck/rounds and 14 who are still at 0/4
• So then you can either let the other 14 people play (4,4,3,3 players per room) or continue maximising the room utility so that after the second round everyone played at least once and 2/30 players have already played 2/4 games.
• So then you continue picking some number of people until everyone has played exactly 4 decks/rounds.

P.S. You have 2 notions of round - one at a personal level where everyone has 4 to play and the other at the league level where there is some number of decks >4 and each deck is considered "a round" in the eyes of everyone present. From what I understood this was the most confusing bit about the setup that I didn't clarify well at the beginning.

Answer 1

I have rewritten the encoding with your new specification without too much optimizations to get the problem straight.

Remarks: I assume that one that "reads the questions" is the writer ? I assured that there is 1 writer per room available but I didn't name it.

#const nPlayers = 20.                                                                                                  
#const nRooms = 4.                                                                                                     
#const nDecks = 6.                                                                                                     

player(1..nPlayers).                                                                                                   
room(1..nRooms).                                                                                                       
deck(1..nDecks).                                                                                                       

% player P plays in room R in round D                                                                                  
{plays(P,R,D)} :- deck(D), room(R), player(P).                                                                         

% a player may only play in a single room each round
:- player(P), deck(D), 1 < #sum {1,R : plays(P,R,D)}.                                                                  

% not more than 4 players per room                                                                                     
:- deck(D), room(R), 4 < #sum {1,P : plays(P,R,D)}.                                                                    
% not less than 3 players per room                                                                                     
:- deck(D), room(R), 3 > #sum {1,P : plays(P,R,D)}.                                                                    

plays(P,D) :- plays(P,R,D).                                                                                            
% at least one writer per room (we need at least one player not playing for each room, we do not care who does it)     
:- deck(D), nRooms > #sum {1,P : not plays(P,D), player(P)}.                                                           

% each player only plays 4 times during the night                                                                      
:- player(P), not 4 = #sum {1,D : plays(P,D)}.                                                                         

#show plays/3.                                                                                                         

%%% shortcut if too many decks are used, each player can only play 4 times but at least 3 players have to play in a room (currently there is no conecpt of an empty room)
:- 3*nRooms*nDecks > nPlayers*4. 

Note that I added the last constraint, as your initial configuration was not solveable (each player has to play exactly 4 rounds and we have twenty players, this is 80 individual games. Given that at least 3 players have to be in a room, and we have 4 rooms and 7 decks this is 3 * 4 * 7 = 84, we would need to play at least 84 individual games). You could probably also compute the number of decks I think.