[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] For complexity size isn't the issue.
From: |
Nigel Galloway |
Subject: |
[Help-glpk] For complexity size isn't the issue. |
Date: |
Thu, 14 Feb 2008 17:35:33 +0100 |
Consider the following mathprog:
param a ,integer;
param b ,integer;
var x integer;
var y integer;
st1: a*x + b*y >= 1;
minimize m: a*x + b*y;
solve;
end;
This has only 2 unknowns, Euclid demonstrated that there is always feasible set
for any combination of a and b. When the feasible set includes 1 the solution
is found. Does anyone know of a simplex algorithm that can find the minimum
value when the feasible set does not include 1?
I would conclude that in the general case there is no possiblity to determine
the effect of small changes to variables on the time taken for glpk to solve a
problem. Probably not even if glpk had a Polynomial-Time Simplex Algorithm.
--
_______________________________________________
Surf the Web in a faster, safer and easier way:
Download Opera 9 at http://www.opera.com
Powered by Outblaze
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Help-glpk] For complexity size isn't the issue.,
Nigel Galloway <=