[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] mip formulations and reformulations

From: Andrew Makhorin
Subject: Re: [Help-glpk] mip formulations and reformulations
Date: Tue, 27 Oct 2009 01:22:07 +0300

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]