Re: [Help-glpk] mip formulations and reformulations

[xypron]

Hello Andrew,

> 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).

My understanding is, to solve this problem fast:
1) Symmetries should be removed.
2) The usage of trucks should be modeled as binaries.
3) Branching should be on trucks first.
4) Redundant constraints may help.

I have added symmetry removal and result output to the following
file:
http://www.nabble.com/file/p26070245/trick3.mod trick3.mod 

I guess the problem is interesting enough to be added to the GLPK
examples.

Best regards

Xypron


Andrew Makhorin wrote:
> 
>> 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.
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
> 
> 

-- 
View this message in context: 
http://www.nabble.com/mip-formulations-and-reformulations-tp26060305p26070245.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.