[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;



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

Powered by Outblaze

reply via email to

[Prev in Thread] Current Thread [Next in Thread]