Uniform saturation in linear inequality systems (Q2568606)

Let \(T\) be a set, and consider \(a:T\rightarrow\mathbb{R}^n\), \(b:T\rightarrow \mathbb{R}\), denoting by \(a_t\) and \(b_t\) their values at \(t\in T\). The authors consider a system \(\sigma=\{a_t'\geq b_t,\;t\in T\}\), where \(a_t'\) denotes the transpose, and \(a_t\neq0_n\) for every \(t\). Let \(F\subset\mathbb{R}^n\) be the solution set, and for each \(s\in T\) put \[ F_s=\{x\in\mathbb{R}^n:\;a_t'x\geq b_t,\;t\in T\setminus\{s\}\}. \] The index \(s\) is called \textit{redundant} if \(F_s=F\). Let \(P(c)\) and \(P_s(c)\) be the linear programs of minimizing \(c'x\) subject to \(x\in F\) and \(x\in F_s\) respectively, and let \(F^*(c), F_s^*(c)\) be the corresponding optimal sets. Let also \(H_s=\{x:\;a_s'=b_s\}\). The constraint \(s\) is said to be \textit{uniformly saturated} in \(\sigma\), if \(F^*(c)\cap H_s\neq\emptyset\) for all \(c\in\mathbb{R}^n\setminus\{0\}\); \textit{uniformly strongly saturated} in \(\sigma\), if \(F^*(c)\subset H_s\neq\emptyset\) for all \(c\in\mathbb{R}^n\setminus\{0\}\) such that \(F^*(c)\neq\emptyset\); \textit{weakly uniformly saturated} in \(\sigma\) if it is uniformly saturated but not uniformly strongly saturated. The authors characterize those inequalities in \(\sigma\) belonging to each of the three classes.