Finding an interior point in the optimal face of linear programs (Q1319020): Difference between revisions

Consider the problem (P): \(\min c^ T x\) subject to \(Ax= b\), \(x\geq 0\), and its dual (D): \(\max b^ T y\) subject to \(A^ T y+ s=c\), \(s\geq 0\). It is well-known that feasible solutions \(x^*\) and \((y^*,s^*)\) are optimal for (P) and (D) respectively iff \(x^*_ j s^*_ j=0\) \((j=1,\dots,n)\). Let \(\sigma(x^*)= \{i| x^*_ i>0\}\). The pair \((x^*,s^*)\) is strictly complementary if \(\sigma(x^*)\cap \sigma(s^*)= \emptyset\) and \(\sigma(x^*)\cup \sigma(s^*)= \{1,2,\dots,n\}\). The partition \(\{\sigma^*,\bar\sigma^*\}\) of \(\{1,2,\dots,n\}\) is an optimal partition, where \(\sigma(x^*)= \sigma^*\) and \(\bar\sigma^*=\{1,2,\dots,n\}\backslash \sigma^*\) in view of the invariant character of \(\sigma(x^*)\) and \(\sigma(s^*)\) for every strictly; complementary solution \((x^*,s^*)\). The authors study the problem of finding the optimal partition and a pair of points in the interior of \(\theta_ p= \{x: Ax= b,\;x\geq 0,\;x_ j=0\) for \(j\in \bar\sigma^*\}\) and \(\theta_ d= \{(y,s): A^ T y+ s=c,\;s_ j=0\) for \(j\in \sigma^*\}\). The authors claim that the optimal partition can be identified in \(O(n^ 3 L)\) arithmetic operations where the data in (P) are rational and \(L\) is their input length. They also propose a practical and (column) scaling independent criterion for identifying the optimal partition. Finally, the authors report computational results on the problems in the NETLIB test set. For related work the reader is referred to \textit{R. M. Freund} et al. [Technical Report, Sloan W. P. No. 1674-85, MIT, Cambridge, MA (1985)] and \textit{E. Tardos} [Oper. Res. 34, 250-256 (1986; Zbl 0626.90053)].