3
$\begingroup$

Consider the following system of inequalities:

$Ax=b$; $x\geq 0$;

A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. How this system can be solved without using linear programming?

$\endgroup$
  • $\begingroup$ please explain what mean by "solved". $\endgroup$ – Dima Pasechnik Jul 18 '12 at 17:35
  • $\begingroup$ I meant, how can the feasibility of this system be checked without using linear programming? $\endgroup$ – Star Jul 18 '12 at 17:51
  • $\begingroup$ There is no general way, but perhaps you can use one of the "theorems of the alternative" such as Farkas's Lemma, Gale's Theorem, etc. $\endgroup$ – Yoav Kallus Jul 18 '12 at 20:43
  • $\begingroup$ Why do you want to avoid linear programming? $\endgroup$ – Gilead Jul 18 '12 at 20:45
6
$\begingroup$

From http://www.faqs.org/faqs/linear-programming-faq/

Q6.4: "I just want to know whether or not a feasible solution exists."

A: From the standpoint of computational complexity, finding out if an LP model has a feasible solution is essentially as hard as actually finding the optimal LP solution, within a factor of 2 on average, in terms of effort in the Simplex Method; plug your problem into a normal LP solver with any objective function you like, such as c=0. For MIP models, it's also difficult - if there exists no feasible solution, then you must go through the entire Branch and Bound procedure (or whatever algorithm you use) to prove this. There are no shortcuts in general, unless you know something useful about your model's structure (e.g., if you are solving some form of a transportation problem, you may be able to assure feasibility by checking that the sources add up to at least as great a number as the sum of the destinations).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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