% In a house with 5 people, specify how much each person has spent
% on communal stuff, and get a minimal list of transaction to get
% all debts balanced.
names = {'Amelia', 'Bill', 'Clemens', 'Dean', 'Eric'};
paid = [30 45 10 35 5]';
balance = paid - mean(paid);
% Transactions are from people who owe money to those who don't
n_transactions = sum(balance > 0) * sum(balance < 0);
% Create a table showing which people each transaction refers to.
transaction_dirs = zeros(n_transactions,2);
% Create the constraint matrix
A = zeros(length(balance),n_transactions);
t = 1;
for src = find(balance'<0)
    for dest = find(balance'>0)
        transaction_dirs(t,:) = [src, dest];
        A(src,t) = 1;
        A(dest,t) = 1;
        t = t+1;
    end
end

b = abs(balance);
lb = zeros(n_transactions, 1);
first_guess = mean(b)/2 * ones(n_transactions,1);

% Maximise the sum of squares. Can you prove that this minimises the number
% of transactions?
objective = @(x)(-x'*x);

p = createOptimProblem('fmincon', 'Aineq', A, 'bineq', b,...
                       'lb', lb, 'objective', objective,...
                       'x0', first_guess);
gs = GlobalSearch('MaxTime',5,'Display','off',...
                  'TolX', 5e-3,'TolFun',1e-4,...
                  'NumTrialPoints',300,'NumStageOnePoints',80,...
                  'StartPointsToRun','all');

[x,fval,ex] = run(gs, p);

for ind = 1:n_transactions
    if round(x(ind)*100)/100 ~= 0
        fprintf('%s pays %s %0.2f\n', names{transaction_dirs(ind,1)},...
                                      names{transaction_dirs(ind,2)},...
                                      x(ind));
    end
end
