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

[xypron]

Hello Nigel!

The search space is infinite with x, y in [-inf, +inf] with infinitely many
global optimum solutions hence solution time for branch and bound will be
infinite too.

The optimum is the smallest multiple of 
the largest common divisor of a and b 
>= the right hand side of st1.

Obviously the objective function will always be integer. Hence it would make
sense to let the branch and bound add an extra cut limiting the objective
function to the best found solution minus one.

Together with a cut providing a correct lower limit this would let the
search stop at the first optimum solution.

Best regards

Xypron

Nigel Galloway wrote:
> 
> 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
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
> 
> 
Quoted from: 
http://www.nabble.com/For-complexity-size-isn%27t-the-issue.-tp15483910p15483910.html

-- 
View this message in context: 
http://www.nabble.com/For-complexity-size-isn%27t-the-issue.-tp15483910p18205499.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.