1
$\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 $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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Goswin
    Sep 30, 2016 at 13:25

1 Answer 1

1
$\begingroup$

The answer is Yes. A Linear Programming problem that is both primal and dual infeasible does always have a (not necessarily unique) basis that is both primal and dual infeasible.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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