Given a set of logical sentences together with probabilities that these sentences are true, the probabilistic satisfiability (PSAT) problem consists, in its decision version, in finding whether these probabilities are consistent, and in its optimization version in determining best possible lower and upper bounds on the probability that an additional sentence be true. Van der Gaag recently proposed a partially quantified belief network model which may be viewed as a decomposition-oriented version of PSAT. Both models give the same bounds, which implies that PSAT implicitly takes into account some independence relations. A column-generation algorithm is proposed for the decomposition form of PSAT and shown to have several advantages over a similar algorithm for the usual form, mainly in the exploitation of the sparsity of the matrix of coefficients.