[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] [Fwd: Strip packing problem]

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] [Fwd: Strip packing problem] |

**Date**: |
Sun, 24 Jun 2012 14:27:55 +0400 |

>* Someone can point me how to model the "or" conditions? *
>* *
See the example model examples/jssp.mod included in the glpk
distribution that illustrates modeling disjunctive conditions.
Note that your 2d cutting stock problem can be modeled as mip at least
in two different ways:
i) the unknowns are x and y coordinates of each rectangle which are
continuous variables, where the disjunctive conditions are modeled with
auxiliary binary variables;
ii) the unknowns are binary variables x[i,j,k], where x[i,j,k] = 1 means
that rectangle k covers a rectangular cell (i,j) assuming that the
entire paper is divided into a set of the cells.
The model jssp.mod corresponds to the case (i). However, the case (ii)
has many advantages, in particular, it allows to reduce your problem to
the satisfiability problem (that can be efficiently solved with the
Minisat solver included in glpk).