[Help-glpk] For complexity size isn't the issue.

[Nigel Galloway]

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