0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Goswin Sep 30 '16 at 13:24
0
$\begingroup$

The answer is Yes. A doubly infeasible problem does always have some basis that is both primal infeasible and dual infeasible.

$\endgroup$
  • $\begingroup$ In order to avoid unnecessary repetitions, I will limit my posting future information about this problem at the math overflow forum. (Question: "Do doubly infeasible Linear Programming problems always have doubly infeasible bases?") $\endgroup$ – Goswin Nov 17 '16 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.