Re[6]: [Help-glpk] LPP & MIP

[Andrew Makhorin]

>If no solver (available) can found a faster answer, does this mean that
>it is impossible to do better?  I feel a little bit screwed.

The bin packing problem as well as many other interesting combintorial
problems is np-complete. This means that there is no algorithm which is
able to find an exact optimum for any instance of such problem for a
polynomial time, i.e. for the time which is a polynomial function of the
problem size (say, n^2 or n^3, where n is the number of items to be
packed). Although it is possible to solve a particular instance for a
polynomial time (these instances as a rule are trivial and therefore
uninteresting), in worst cases *any* algorithm may require an exponential
time (say, 2^n or n!), and in this sense it is impossible to find an
exact optimimum faster.