Perfect Zero-One Matrices — II
Manfred W. Padberg · Operations research proceedings · 1974
We consider combinatorial programming problems of the form (LP): max {cx|Ax ≤e, xj=0 or 1, vj}, where A is a mxn matrix of zeroes and ones, e is a column vector of m ones and c is an arbitrary (non-negative) vector of reals. Applications of this general problem include crew scheduling, political districting and others. In this paper we first summarize (without proofs) the results of a companion paper that completely characterize matrices A for Which.(IP) can be solved as an ordinary linear programming problem, i.e. where the relaxed linear program (LP): max{cx|Ax ≤e, xj≥0,vj} produces an integral solution no matter what linear form cx is maximized. (Zero-one matrices with this property are termed “perfect”). Some additional concepts and results are stated. It is shown that every totally unimodular zero-one matrix as well as every “balanced” zero-one matrix is perfect. Finally, in the concluding remarks, a reformulation of the strong perfect graph due to C. BERGE is given and some recent trends in zezo-one programming are delineated.