No label defined (Q4027192)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 125490
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 125490 |
Statements
21 February 1993
0 references
linear systems of inequalities
0 references
integer rounding property
0 references
total dual integrality
0 references
linear programming
0 references
integral matrices
0 references
0.7606567144393921
0 references
[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.
0 references