function [A b] = generate_3sat(m,n)
% Generates a 3SAT problem with n variables and m expressions
logic1 = zeros(0,3);% expressions with 3 true
logic2 = zeros(0,3);% expressions with 2 true and 1 false
logic3 = zeros(0,3);% expressions with 1 true and 2 false
logic4 = zeros(0,3);% expressions all false
for i = 1:m
    x = randsample(n,3)';%select 3 variables
    neg = rand(1);
    if(neg <= 1/8)
        logic1 = [logic1; x];
    elseif(neg <= 1/2)
        logic2 = [logic2; x];
    elseif(neg <= 7/8)
        logic3 = [logic3; x];
    else
        logic4 = [logic4; x];
    end
end

% create the A and B matrices associated with this problem
A = zeros(m,n);
b = zeros(m,1);

cum_pos = 0;
for i = 1:numel(logic1)/3
    cum_pos = cum_pos + 1;
    A(cum_pos,logic1(i,:)) = [-1 -1 -1];
    b(cum_pos) = -1;
end
for i = 1:numel(logic2)/3;
    cum_pos = cum_pos + 1;
    A(cum_pos,logic2(i,:)) = [-1 -1 1];
    b(cum_pos) = 0;
end
for i = 1:numel(logic3)/3;
    cum_pos = cum_pos + 1;
    A(cum_pos,logic3(i,:)) = [-1 1 1];
    b(cum_pos) = 1;
end
for i = 1:numel(logic4)/3;
    cum_pos = cum_pos + 1;
    A(cum_pos,logic4(i,:)) = [1 1 1];
    b(cum_pos) = 2;
end

end