# Do doubly infeasible Linear Programming problems always have doubly infeasible bases?

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 $D(\pi)\cap B(\pi)=\emptyset$ and 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 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?

• This question has been posted at the stackexchange mathematics forum four weeks ago (on Sep.1,2016). Up to now there were neither votings nor comments nor answers, so it might well be a difficult question. Sep 30, 2016 at 13:25