An Abstract Linear Duality Model

We investigate an abstract linear duality model which has as special instances several duality systems of interest in combinatorial optimization: subspace orthogonality, cone polarity, lattice duality, blocking polyhedra and antiblocking polyhedra. The descriptive duality present in the model is that of specifying a set in terms of linear constraints or viewing a set as being generated by certain types of linear combinations. We define properties of Weyl, Farkas and Minkowski for the general model by analogy with classical results in cone polarity and we investigate relationships among these properties and further properties of Lehman and Fulkerson, defined by analogy with results on dual pairs of polyhedra of the blocking or antiblocking type. In particular, we show that, for any given duality system, the Weyl property is equivalent to the combined properties of Farkas and Minkowski (or Lehman), that the Farkas property implies the Fulkerson property and that the Minkowski property is equivalent to the combined properties of Lehman and Fulkerson. We also adapt results of Dixon (Dixon, J. D. 1981. On duality theorems. Linear Algebra Appl.39 223–228.) in order to obtain general sufficient conditions for validity of the Weyl property.

In the second part of the paper, specific instances of the model are examined in more detail. The instances studied here are “integral duality” and “nonnegative integral duality,” which are related to the problem of finding integral solutions and nonnegative integral solutions, respectively, for linear systems. For each instance, the validity of the Weyl, Minkowski, Farkas, Lehman and Fulkerson properties is examined. We also characterize the constrained sets under each duality.