# Bases of doubly infeasible Linear Programming problems

Consider a Linear Programming problem in dictionary form,

$$\max\Big\{f^\pi+\!\!\!\sum_{j\in D(\pi)}\!\! d^\pi_jx_j~\Big|~\forall~i\!\in\!B(\pi)~~~ b^\pi_i+\!\!\!\sum_{j\in D(\pi)}\!\! G^\pi_{ij}x_j\ge0,~~~ \forall~j\!\in\!D(\pi)~~ x_j\ge0\Big\},$$

where indices $\pi$ uniquely define the coefficients of each basic inequality system.

Now assume that the problem is both primal and dual infeasible. Primal infeasibility implies that there always exists a "primal-infeasible" basis $\alpha$ with some $r\!\in \!B(\alpha)$ having $~b^\alpha_r<0$ and $\forall~j\!\in\!D(\alpha)~~ G^\alpha_{rj}\le0$, while dual infeasibility implies that there exists a (possibly different) "dual-infeasible" basis $\beta$ with some $s\!\in\!D(\beta)$ having $~d^\beta_s>0$ and $\forall~i\!\in\!B(\beta)~~ G^\beta_{is}\ge0$.

It is easy to construct doubly infeasible problems where both of the above properties appear together at some of its bases, that is, where $\alpha=\beta$.   But is that true for all doubly infeasible problems? By a case by case analysis, I was able to prove that a counterexample to the existence of such doubly infeasible bases would have at least $|D(\pi)|\ge3$ and $|B(\pi)|\ge3$.

Does a doubly infeasible problem always have bases that are simultaneously primal-infeasible and dual-infeasible? Alternatively, is there a doubly infeasible problem such that the above two properties do only appear at different bases?

• Since this question received no voting, comment, or answer during the last four weeks, it might be a rather difficult question, so I decided to post it also at the mathoverflow forum. – Goswin Sep 30 '16 at 13:24