Total dual dyadicness and dyadic generating sets

integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of emph{dyadic generating sets for cones and subspaces}, the former being the dyadic analogue of emph{Hilbert bases}, and the latter a polynomial-time recognizable relaxation of the former. Along the way, we see some surprising turn of events when compared to total dual integrality, primarily led by the emph{density} of the dyadic rationals. Our study ultimately leads to a better understanding of total dual integrality and polyhedral integrality. We see examples from dyadic matrices,

T

-joins, cycles, and perfect matchings of a graph.

Review text

This article considers totally dyadic linear systems, which are those having integer coefficients with optimal solution vector with entries of the form \(a/2^k\). The authors consider the problem of determining when a linear program admits an optimal dyadic solution via the use of dyadic generating sets. Several interesting results are proven which provide a better insight on polyhedral internality. An extension to \(T\)-joins and perfect matchings concludes this paper. For the entire collection see [Zbl 1492.90008].

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Total dual dyadicness and dyadic generating sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164668)