%------------------------------------------------------------------------%
% Table Talk Tuning: seating placement model
%------------------------------------------------------------------------%
%
% Authors: Martin Butler and Mikael Zayenz Lagerkvist
%
% Assigns guests to tables subject to capacities and required groupings.
% The objective first handles table slack and gender balance, then improves
% the minimum and total majority-supported conversational interest.
%------------------------------------------------------------------------%

include "globals.mzn";


%------------------------------------------------------------------------%
% Data definition
%------------------------------------------------------------------------%

enum Guests;
enum Topics;
enum Genders = {Man, Woman, NA};

type GuestInfo = record(
    string: name,
    string: surname,
    Genders: gender,
    array[Topics] of int: interest
);
array[Guests] of GuestInfo: guests;

% Sets of guests that must be at the same or different tables.
array[int] of set of Guests: same_table;
array[int] of set of Guests: different_tables;

% The number of NA guests offsets the difference between the number of
% men and women when computing the table imbalance.
int: max_gender_imbalance_per_table;

enum Tables;
array[Tables] of int: table_capacities;
set of int: unique_table_capacities = {c | c in table_capacities};

constraint assert(
    card(Guests) <= sum(table_capacities),
    "Must be room for all guests"
);


%------------------------------------------------------------------------%
% Variables
%------------------------------------------------------------------------%

% Table assignment for each guest.
array[Guests] of var Tables: table_of;

% Number of guests at each table.
array[Tables] of var 0..max(table_capacities): occupancy;

% Whether a specific guest is at a specific table.
array[Tables, Guests] of var bool: table_has_guest;

array[Tables] of var set of Guests: guests_at = [
    {guest | guest in Guests where table_has_guest[table, guest]}
  | table in Tables
];


%------------------------------------------------------------------------%
% Constraints
%------------------------------------------------------------------------%

% Channel table_has_guest with table_of.
constraint forall (table in Tables, guest in Guests) (
    table_has_guest[table, guest] <-> table_of[guest] == table
);

constraint forall (table in Tables) (
    occupancy[table] == sum (guest in Guests) (
        table_has_guest[table, guest]
    )
);

constraint forall (table in Tables) (
    occupancy[table] <= table_capacities[table]
);

constraint global_cardinality_closed(
    table_of,
    [table | table in Tables],
    occupancy
);

constraint forall (group in same_table) (
    forall (g1, g2 in group where g1 < g2) (
        table_of[g1] = table_of[g2]
    )
);

constraint forall (group in different_tables) (
    forall (g1, g2 in group where g1 < g2) (
        table_of[g1] != table_of[g2]
    )
);


%------------------------------------------------------------------------%
% Gender imbalance
%------------------------------------------------------------------------%

function var int: count_gender(
    Tables: table,
    Genders: gender_to_count
) =
    sum (guest in Guests where guests[guest].gender == gender_to_count) (
        table_has_guest[table, guest]
    );

% Imbalance is max(abs(men - women) - na, 0). The NA count can therefore
% cancel an otherwise unmatched guest in the binary balancing heuristic.
function var int: compute_imbalance(Tables: table) =
    let {
        var int: women = count_gender(table, Woman),
        var int: men = count_gender(table, Man),
        var int: na = count_gender(table, NA),
        var int: imbalance = max(abs(women - men) - na, 0);
        constraint women + men + na = occupancy[table]
    } in
    imbalance;

array[Tables] of var int: imbalances = [
    compute_imbalance(table) | table in Tables
];

constraint forall (table in Tables) (
    imbalances[table] <= max_gender_imbalance_per_table
);


%------------------------------------------------------------------------%
% Symmetry breaking
%------------------------------------------------------------------------%

constraint forall (capacity in unique_table_capacities) (
    let {
        array[int] of Tables: capacity_tables = [
            table
          | table in Tables
            where table_capacities[table] == capacity
        ]
    } in
    symmetry_breaking_constraint(
        value_precede_chain(capacity_tables, table_of)
    )
);


%------------------------------------------------------------------------%
% Optimisation goal
%------------------------------------------------------------------------%

var int: total_imbalance = sum(imbalances);
int: max_possible_imbalance =
    max_gender_imbalance_per_table * card(Tables);

array[Tables] of var opt int: slack = [
    table_capacities[table] - occupancy[table]
  | table in Tables where occupancy[table] > 0
];
var int: total_slack = sum(slack);
var int: max_slack = max(slack);
int: max_max_slack = max(table_capacities) - 1;

% For each table and topic, find the interest level supported by a strict
% majority of the guests at that table.
array[Tables, Topics] of var int: base_interest =
    array2d(Tables, Topics, [
        let {
            array[Guests] of var int: interest_at_table = [
                if table_has_guest[table, guest] then
                    guests[guest].interest[topic]
                else
                    0
                endif
              | guest in Guests
            ],
            array[int] of var int: sorted_interest =
                sort(interest_at_table),
            var int: lower_score_count = occupancy[table] div 2
        } in
        sorted_interest[card(Guests) - lower_score_count]
      | table in Tables, topic in Topics
    ]);

% Cap each supported topic by the guest's own interest, then choose their
% best topic at the assigned table.
array[Guests] of var int: best_table_interest = [
    let {
        array[Topics] of var int: table_interest = [
            min(
                base_interest[table_of[guest], topic],
                guests[guest].interest[topic]
            )
          | topic in Topics
        ]
    } in
    max(table_interest)
  | guest in Guests
];

int: max_possible_interest =
    max (topic in Topics, guest in Guests) (
        guests[guest].interest[topic]
    );
var int: min_interest = min(best_table_interest);

int: total_max_possible_interest =
    card(Guests) * max_possible_interest;
var int: total_interest = sum(best_table_interest);

% Mixed-radix weights encode the five objective levels as one MiniZinc
% objective. Each level outweighs every possible change below it.
var int: min_interest_penalty = max_possible_interest - min_interest;
var int: total_interest_penalty =
    total_max_possible_interest - total_interest;

int: total_interest_weight = 1;
int: min_interest_weight = total_max_possible_interest + 1;
int: imbalance_weight =
    (max_possible_interest + 1) * min_interest_weight;
int: max_slack_weight =
    (max_possible_imbalance + 1) * imbalance_weight;
int: total_slack_weight =
    (max_max_slack + 1) * max_slack_weight;

var int: goal =
    total_slack * total_slack_weight
  + max_slack * max_slack_weight
  + total_imbalance * imbalance_weight
  + min_interest_penalty * min_interest_weight
  + total_interest_penalty * total_interest_weight;


%------------------------------------------------------------------------%
% Search specification
%------------------------------------------------------------------------%

solve
    :: int_search(table_of, dom_w_deg, indomain_min)
minimize goal;


%------------------------------------------------------------------------%
% Output
%------------------------------------------------------------------------%

output [
    "\(table): \({guest | guest in Guests where table_has_guest[table, guest]})\timbalance: \(imbalances[table])\n"
  | table in Tables where fix(occupancy[table]) > 0
] ++ [
    "\n" ++ show2d(base_interest) ++ "\n"
] ++ [
    let {
        array[int] of string: interest_levels = [
            "\(guest): \(guests[guest].interest[topic])"
          | guest in Guests where fix(table_has_guest[table, guest])
        ]
    } in
    "\(table) \(topic): \(interest_levels)\n"
  | table in Tables where fix(occupancy[table]) > 0,
    topic in Topics
] ++ [
    "best_table_interest: \(best_table_interest)\n",
    "guests_at:           \(guests_at)\n",
    "goal:                \(goal)\n",
    "slack:               \(slack)\n",
    "1 total_slack:       \(total_slack)\n",
    "2 max_slack:         \(max_slack)\n",
    "3 imbalance:         \(total_imbalance)\n",
    "4 min_interest:      \(min_interest)\n",
    "5 total_interest:    \(total_interest)\n"
];