mip formulations and reformulations

[Andrew Makhorin]

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
Help-glpk@...
http://lists.gnu.org/mailman/listinfo/help-glpk

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

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
[e-mail]
http://lists.gnu.org/mailman/listinfo/help-glpk

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



_______________________________________________
Help-glpk mailing list
Help-glpk@...
http://lists.gnu.org/mailman/listinfo/help-glpk

[Andrew Makhorin]

> I only would like to
> draw an attention that reformulation of mip may essentially reduce the
> solution time (though this is well known).

Not only the reformulations that tighten the feasible region
(like cutting planes), but even redundant constraints may significantly
affect the solution process, as shown by Prof. Trick.



_______________________________________________
Help-glpk mailing list
Help-glpk@...
http://lists.gnu.org/mailman/listinfo/help-glpk

[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:
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
[e-mail]
http://lists.gnu.org/mailman/listinfo/help-glpk

[Meketon, Marc-2]

Kipp Martin wrote several papers on reformulations of linear/integer
programs to obtain tighter bounds and faster optimization times.  I have
used some of tricks successfully in the past couple of years.

When this email from Andrew first came out, I asked Kipp if there was
anything available on the web that contained his work that could be
distributed to this group.

He graciously created a link for us that contains Chapter 16 of a book
he wrote on large-scale linear and integer optimization.  This chapter
discusses reformulations of the problem to get tighter bounds.  I
believe many people in this group would find it helpful:

http://kipp.chicagobooth.edu/chapter16.pdf

Thank you Kipp!

-Marc


-----Original Message-----
From: help-glpk-bounces+marc.meketon=oliverwyman.com@...
[mailto:help-glpk-bounces+marc.meketon=oliverwyman.com@...] On
Behalf Of Andrew Makhorin
Sent: Monday, October 26, 2009 9:58 AM
To: help-glpk@...
Subject: [Help-glpk] mip formulations and reformulations

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
----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged.  If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein.  Please inform us of the erroneous delivery by return e-mail.

Thank you for your cooperation.
----------------------------------------------------------------------------



_______________________________________________
Help-glpk mailing list
Help-glpk@...
http://lists.gnu.org/mailman/listinfo/help-glpk

[Ali Baharev]

This thread is getting more and more exciting :)

The Zimpl User Guide gives examples of reformulations that made the
solution process much faster:

Section 5 - Modeling examples
http://zimpl.zib.de/download/zimpl.pdf

It appeared earlier on this mailing list before:

AIMMS Modeling Guide - Integer Programming Tricks
http://www.aimms.com/aimms/download/manuals/AIMMS3OM_IntegerProgrammingTricks.pdf

Although it is not MILP, someone may find this one also useful:

AIMMS Modeling Guide - Linear Programming Tricks
http://www.aimms.com/aimms/download/manuals/AIMMS3OM_LinearProgrammingTricks.pdf

Ali


_______________________________________________
Help-glpk mailing list
Help-glpk@...
http://lists.gnu.org/mailman/listinfo/help-glpk

[Andrew Makhorin]

Please see an example model attached. It demonstrates a technique
to reduce coefficients for 0-1 knapsack inequality.

Original 0-1 knapsack inequality:
65 x1 + 64 x2 + 41 x3 + 22 x4 + 13 x5 + 12 x6 + 8 x7 + 2 x8 <= 80

Minimized equivalent inequality:
4 x1 + 4 x2 + 2 x3 + 2 x4 + 1 x5 + 1 x6 + 1 x7 + 0 x8 <= 5


_______________________________________________
Help-glpk mailing list
Help-glpk@...
http://lists.gnu.org/mailman/listinfo/help-glpk