Re: [Help-glpk] mip formulations and reformulations

[xypron]

Hello Andrew,

thank you for the interesting article.

I solved trick.mod you appended with
glpk-4.39\w32\glpsol.exe" -m trick.mod
+  1964: mip =  8.200000000e+000 >=     tree is empty   0.0% (0; 241)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.3 secs
Memory used: 0.6 Mb (666702 bytes)

When I removed
redundant_constraint:
      sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j];

glpk-4.39\w32\glpsol.exe" -m trick.mod
+  4335: mip =  8.200000000e+000 >=     tree is empty   0.0% (0; 363)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.5 secs
Memory used: 0.7 Mb (771479 bytes)

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.

The fastest solution I could get was with the model linked below:
glpk-4.39\w32\glpsol.exe" -m trick2.mod
+  1209: mip =  8.200000000e+000 >=     tree is empty   0.0% (0; 159)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.3 Mb (292559 bytes)

http://www.nabble.com/file/p26068212/trick2.mod trick2.mod 

With --first specified the solution was even faster.
glpk-4.39\w32\glpsol.exe" -m trick2.mod --first
+  1003: mip =  8.200000000e+000 >=     tree is empty   0.0% (0; 87)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.3 Mb (284223 bytes)

While with --last specified GLPK took longer than I wanted to wait.

Best regards

Xypron


Andrew Makhorin wrote:
> 
> There had been some discussions on the list around mip's, which are
> hard for glpk due to their structure, and how one could reformulate
> the model to make it easier for solving. So I would like to mention
> the interesting educational article "Formulations and Reformulations
> in Integer Programming" by Prof. Michael Trick. The article is
> publically available at http://mat.gsia.cmu.edu/trick/formul04.pdf .
> 
> I translated one of the models described in the article from Mosel to
> MathProg (please see the attachment). In its initial formulation the
> model is absolutely intractable for solving to optimality with glpsol.
> After some reformulations suggested in the article the solution time
> was reduced signficantly. However, a most amazing effect happened
> after including in the model an additional redundant constraint (which
> is redundant even for lp relaxation) --- glpsol could solve it to
> optimality for one second.
> 
> Hope my information will be useful.
> 
> 
> Andrew Makhorin
>  
> _______________________________________________
> 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-tp26060305p26068212.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.