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

[Richard Prescott]

On Sat, 31 Jul 2004, Andrew Makhorin wrote:

> I believe that a mip presolver could not simplify your instance
> bpp25. The bin packing is a hard combinatorial optimization problem,
> and presolving could not help in this case (as a rule). Btw, the greedy
> heuristic obtained a sub-optimal solution 13, while the global bound is
> 11, i.e. the exact optimum for your instance can be only 11, 12, or 13.

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.  (That is 
true for my home problem too which is a shame.)

I might be wrong (as I said earlier, I am a optimisation newbie) but I 
feel that what is missing is kind of a "if this then that" type of 
simplification *during* MIP solving.  The type of things that we found in 
Constraint Programming and pretty much what IPP will do.

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 ?

I first though that LP relaxation will gives answers *close* to the real 
answer with a maximum offset of 1-eps (example: if LP give 4.6 answers is 
4 or 5) but my home problem shows a LP relaxation value -- for one of my 
variable which is the goal to minimize -- of exactly 4 and the real answer 
is 6. :-( That cause lpx_integer to never find an optimal solution. 
Well, that what it thinks but it was wrong.


IPP spec:

EMPTY ROW        : as LPP
EMPTY COLUMN     : as LPP
FREE ROW         : as LPP
FIXED COLUMN     : as LPP insist on integral value of integer variable
ROW SINGLETON == : enforce that fixing an integer variable to a integer
                   value otherwise infeasible
ROW SINGLETON != : enfore that fixing integer bounds to integer values
                   if bounds aren't integral, find the integral value
                   respecting the constraint and reajust row bounds in
                   consequence.
IMPLIED SLACK    : not applicable as shown by Andrew Makhorin
IMPLIED FREE     : not applicable as shown by Andrew Makhorin
FORCING ROW      : same as ROW SINGLETON !=
GENERAL ROW      : as LPP
GENERAL COLUMN   : as LPP ;-)


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)

What do you think?

Regards

Richard Prescott