THE SETUP POLYHEDRON OF SERIES-PARALLEL POSETS

To every linear extension L of a poset P = (P, <) we associate a 0, 1- vector x = x(L) with x(e) = 1 if and only if e is preceded by a jump i n L or e is the first element in L. Let the setup polyhedron S = conv{ x(L): L is an element of (S)} be the convex hull of the incidence vect ors of all linear extensions of P. For the case of series-parallel pos ets we solve the optimization problem over S and give a linear descrip tion of S.