sci.op-research

On Mar 2, 12:36 am, "Skybuck Flying" wrote:
> Simplex algorithm works for floating-point numbers (=broken numbers like 2/3
> or 0.66)

What is a "broken number"? If you mean that the simplex method can
deliver non-integer solutions, then your statement is correct.

>
> Branch and Bound uses the simplex algorithm to try and round down broken
> numbers on tree nodes. Therefore branch and bound is a wacky integer solver
> (=whole numbers like 1 or 2 or 3 or 4).

What is a 'wacky' solver? If you mean that the method is somewhat
naive and/or lacks theoretical depth, you may be right. On the other
hand we don't know any better way to deal with general instances of
IP, despite almost 50 years of work by highly talented and intelligent
people.

For 0.66 it would try 0 and 1 and
> see which one is best.

No, it would not, although it might start off that way. It could end
up going from x = 0.66 in the continuous solution to x = 7 in the
optimal integer solution.

>
> So branch and bound complements the simplex algorithm. It sort of extends it
> a little bit.
>
> It's not a very good algorithm though, it's best effort, there are no
> garantuees that it will find optimal solutions... it can take very long.

No. Theoretically it IS guaranteed to find an optimal integer solution
or to prove that the integer problem is infeasible (even if the
continuous problem is feasible). However, there are no guarantees on
how much work it will need to do or how long it will take. Of course,
these are theoretical guarantees on ideal computers in the absence of
computational roundoff errors and with unlimited memory and unlimited
CPU time. Perhaps you meant to say that the method might not always
work on a real, finite wordlength computer with finite memory in
companies with finite solution deadlines and finite computing budgets.
If so, that is sometimes true.

R.G. Vickson


>
> Bye,
> Skybuck.
>
> "saneman" wrote in message
>
> news:fqbapa$rs2$1@news.net.uni-c.dk...
>
> > What is the difference between simplex and branch and bound? As I
> > understand they can both be used to solve linear programs.