BASE POLYTOPES OF SERIES-PARALLEL POSETS - LINEAR DESCRIPTION AND OPTIMIZATION

We define the base polytope B(P, g) of partially ordered set P and a s upermodular function g on the ideals of P as the convex hull of the in cidence vectors of all linear extensions of P. This new class of polyt opes contains, among others, the base polytopes of supermodular system s and permutahedra as special cases. After introducing the notion of c ompatibility for g, we give a complete linear description of B(P, g) f or series-parallel posets and compatible functions g. In addition, we describe a greedy-type procedure which exhibits Sidney's job sequencin g algorithm to minimize the total weighted completion time as a natura l extension of the matroidal greedy algorithm from sets to posets. (C) 1998 The Mathematical Programing Society, Inc. Published by Elsevier Science B.V.