Re: [Help-glpk] mip formulations and reformulations

[Andrew Makhorin]

> When I removed
> redundant_constraint:
>       sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];
> [...]
> Is it this 40 % saving you are refering to?
> Interestingly when MIR cuts are enabled AND the redundant constraint is
> removed
> GLPK gets really slow.
> [...]
> With --first specified the solution was even faster.

It is difficult to say how this or that heuristic used to choose
branching variable affects the solution process. I only would like to
draw an attention that reformulation of mip may essentially reduce the
solution time (though this is well known).

If you try to solve the initial formulation, you can see that the
model is very hard for glpk. Cuts and different branching heuristics
do not help. I also tried pseudo-cost branching, it also does not help.

Just another example. Look at the article "Rapid Mathematical
Programming or How to Solve Sudoku Puzzles in a few Seconds" by
Thorsten Koch at www.zib.de/Publications/Reports/ZR-05-51.pdf .
There are two formulations of the Sudoku puzzle: the first one (p. 5)
uses integer variables and all-different constraints; it cannot be
solved with cplex for more than six hours and one million branching
nodes; the second one (p. 6) uses binary variables and is similar to
sudoku.mod in glpk examples; glpsol can solve it either on the
preprocessing stage or, in hard cases, after performing 3-5 branches.