[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: xypron
Subject: Re: [Help-glpk] For complexity size isn't the issue.
Date: Mon, 30 Jun 2008 15:12:32 -0700 (PDT)

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


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
> Powered by Outblaze
> _______________________________________________
> Help-glpk mailing list
> address@hidden
Quoted from:

View this message in context:
Sent from the Gnu - GLPK - Help mailing list archive at

reply via email to

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