Given a graph G = (V,E) with nonnegative weights x(e) for each edge e, a pa
rtition inequality is of the form x(delta(S-1,...,S-P)) greater than or equ
al to ap+b. Here delta(S-1,...,S-P) denotes the multicut defined by a parti
tion S-1,...,S-P of V. Partition inequalities arise as valid inequalities f
or optimization problems related to k-connectivity. We give a polynomial al
gorithm for the associated separation problem. This is based on an algorith
m for finding the minimum of x(delta(S-1,...,S-P))-p that reduces to minimi
zing a symmetric submodular function. This is handled with the recent algor
ithm of Queyranne. We also survey some applications of partition inequaliti
es.