scientific article; zbMATH DE number 125490
[For the entire collection see Zbl 0748.00023.] Let \(A\) be a rational \(m\times n\)-matrix, and let \(b\) be a rational vector of length \(m\). Several polyhedra occurring in combinatorics are described by linear systems of inequalities \(Ax\leq b\) which have the integer rounding property. S. Baum and L. E. Trotter defined a linear system \(Ax\leq b\) to have the integer rounding property if: \[ \min\{yb:yA=w,\;y\geq 0,\;y\text{ integral}\}=[\min\{yb:yA=w,\;y\geq 0\}] \] for each integral vector \(w\) for which \(\min\{yb:yA=w,\;y\geq 0\}\) is finite. (If \(q\) is a rational number, then \([q]\) is the least integer greater than or equal to \(q.)\) This property can be considered as a generalization of the total dual integrality. The system of inequalities \(Ax\leq b\) is called totally dual integral if the minimum in the linear programming dually equation \[ \max\{wx:Ax\leq b\}=\min\{yb:yA=w,\;y\geq 0\} \] has an integral optimal solution for each integral vector \(w\) for which the optima exist. In general the total dual integrality is also defined for nonintegral matrices \(A\), but only integral matrices are considered here. Operations that preserve the total dual integrality of linear systems of inequalities \(Ax\leq b\) have been investigated by Cook and Schrijver. A generalization of this problem consists in considering linear systems with the integer rouding property and the behaviour of this property under operations. This problem is studied in the present note.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027192)