0

Can I say that "If a problem is formulated as a linear problem (LP), then there must be a solution to the problem (theoretically)"?

Dave
  • 576
  • It's unclear what you mean by "solved definitively". Is that different than just "solved"? (Do you mean "solved globally"?) Some LPs are too large to be solved with current computers. You might instead say something like "efficient algorithms are available for solving LPs" or something like that. – littleO Dec 27 '16 at 07:39
  • It depends. If your readers know what "solved definitively" means, then I guess so. But I don't know what that means, so it might be good to explain what you mean by that phrase. – 5xum Dec 27 '16 at 07:40
  • @littleO, I mean "there must be a solution to the problem (theoretically)" – Dave Dec 27 '16 at 07:46
  • There exist LPs whose feasible sets are empty, and hence cannot be solved. – Sean Roberson Dec 27 '16 at 07:58
  • 1
    $\min x$, $x\in\Bbb R$ is an LP, but there is no solution (unbounded objective function in the set). – A.Γ. Dec 27 '16 at 09:37

1 Answers1

2

Consider the following two LPs:

Problem 1:

$$\max x$$ $$\text{s.t.}~ x \geq 1$$ $$ x \leq 0$$

This problem is infeasible because there is no number that is $\geq 1$ and $\leq 0$ at the same time. Thus, there is no optimal solution.

Problem 2:

$$\max x$$ $$\text{s.t.}~ x \in \mathbb{R}$$

This problem is unbounded and, hence, has no optimal solution.

Thus, not all LPs need to have a solution.

YukiJ
  • 2,529