function X = BR_linprog(KB)
%

m = length(KB);
vars = BR_vars(KB,[]);
n = length(vars);

num_vars = m + 2*n;
num_eqns = 0;
for c = 1:m
    clause = KB(c).clauses;
    num_eqns = num_eqns + length(clause);
end
num_eqns = num_eqns + m;
A = zeros(num_eqns,num_vars);
eqn = 0;

for c = 1:m
    clause = KB(c).clauses;
    atoms = abs(clause);
    signs = sign(clause);
    num_atoms = length(atoms);
    eqn = eqn + 1;
    A(eqn,c) = 1;
    for a = 1:num_atoms
        if signs(a)<0
            A(eqn,(atoms(a)-1)*2+m+1) = -1;
        else
            A(eqn,(atoms(a)-1)*2++m+2) = -1;
        end
    end
    for a = 1:num_atoms
        eqn = eqn + 1;
        A(eqn,c) = -1;
        if signs(a)<0
            A(eqn,m+(atoms(a)-1)*2+1) = 1;
        else
            A(eqn,m+(atoms(a)-1)*2+2) = 1;
        end
    end
end
[num_rows,num_cols] = size(A);
b = zeros(num_rows,1);

Aeq = zeros(m+n,num_vars);
for a = 1:n
    index = m + (a-1)*2 + 1;
    Aeq(a,index:index+1) = 1;
end
beq = ones(m+n,1);
for c = 1:m
    Aeq(n+c,c) = 1;
    beq(n+c) = KB(c).prob;
end
lb = zeros(num_vars,1);
ub = ones(num_vars,1);

X = linprog([],A,b,Aeq,beq,lb,ub);
