function P = defimaxcut(W)
% Given a square matrix W the instruction
%
%   P = DEFIMAXCUT(W)
%
% returns a structure P in Gloptipoly's format corresponding to the
% 0-1 quadratic Max-Cut problem with adjacency matrix W

% Author: Didier Henrion, December 21, 2001
% Last modified by Didier Henrion, January 3, 2002
  
n = size(W,1);
if size(W,2) ~= n,
 error('Input matrix must be square');
end;
e = ones(1,n); Q = (diag(e*W)-W)/4;
P.s = 3*e; P.c = sparse(3^n,1);
for row = 1:n, for col = row:n,
  ind = num2cell(1+(1:n==row)+(1:n==col));
  P.c(sub2ind(P.s,ind{:})) = (1+(row~=col))*Q(row,col);
end; end;
P.t = 'max'; P.v = -e;