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

[Andrew Makhorin]

>You would understand that I don't really care about bpp itself.
>(Although my home problem is close.)  But, a human resolving this problem 
>will do it faster than computer so there something wrong here.

Does "a human resolving" means that you are able to find an integer
feasible solution to any instance of bpp and prove its optimality doing
that faster than computer? If so, please publish your algorithm as soon
as possible :+) However, I believe you are only able to find an integer
feasible solution, maybe relatively fast but providing no proof that it
is optimal. The exact solver may spend much more time, because its goal
is not to find some integer feasible (sub-optimal) solution, but to find
exact optimum, i.e. to prove that no better solution exists. If you are
not interested in exact optimum, you may use a suitable heuristic,
which (as a rule) is able to find a sub-optimal solution much faster
than exact methods. I agree that glpk mip solver is not very good,
however, I tried to solve your instance bpp25 with a much more advanced
solver, Xpress-MP, available via the NEOS Server
<http://www-neos.mcs.anl.gov/neos/solvers/MILP:XPRESSMPINTEGER/>, and
it did not find the optimum for 30 minutes on a 1.5 GHz machine.

>I notice during MIP optmisation that it sometimes find a solution 
>sub-optimal and continue on.  bpp25 and my home problem have the 
>particularity of having few possibles answers (here is 11, 12, 13.)  Would 
>it be possible to lpx_integer trying to first prove that 11 is impossible 
>(or find the solution) then 12 then 13 ?

Unfortunately (or fortunately) to prove that 11 is impossible is as hard
as to solve the entire problem.

>As LPP and IPP are close in functionality, it should be a good idea to 
>merge them together? (Or provides a presolving framework but there is 
>only to kind of presolving)

I hope to tentatively implement IPP in a next release.


Andrew Makhorin