- $BF|;~!'(B6$B7n(B13$BF|!JEZ!K(B 13:30 $B!A(B 17:00 ($B3+;O;~4V$,(B30$BJ,Aa$^$C$F$$$^$9!*(B)
1991$BG/$N(B Journal of Global Optimization $B$NAO4)0JMh!"Bg0hE*:GE,2=$N8&5f$,@9$s(B
- $BH/I=#2!'(BProf. Andr\'as Seb\"o $B!J(BIMAG, Universit\'e de Grenoble$B!K(B
- "Characterizing Noninteger Polyhedra with 0-1 Constraints"
We characterize when the intersection of a set-packing
and a set-covering polyhedron or of their corresponding
minors has a noninteger vertex. Our result is a common
generalization of Lov\'asz's characterization
of `imperfect' and Lehman's characterization of `nonideal'
systems of inequalities, furthermore, it includes new cases in
which both types of inequalities occur and interact in an essential way.
The proof specializes to a conceptually simple and
short common proof for the classical cases, moreover, a typical
corollary extracting a new case is the following : if the
intersection of a perfect and an ideal polyhedron has a noninteger vertex,
then they have minors whose intersection's coefficient matrix is the
incidence matrix of an odd circuit graph.
RAMP Home Page $B$X!%(B