Topic
• 5 replies
• Latest Post - ‏2013-05-20T07:33:36Z by Petr Vilím
glebB
3 Posts

Pinned topic 2D packing++ and which software

‏2013-05-02T03:29:40Z |

Hi,

I am trying to solve a loading/unloading problem which looks like 2D rectangular packing with additional constraints, e.g. of scheduling type. Moreover, the packed objects have variable size in one dimension (which is time).

What software is recommended, ILOG CP 1.6 or CP Optimizer? I started looking at ILOG CP. It has classes named as Ilo... and Ilc... and I see no documentation about their difference and what is the concept to use them. Just isolated examples in the manuals. I can only understand that Ilc... allow some managing...

What would be a sensible way to model non-overlapping constraints for rectangles (whose size in the 1st dimension is variable)? I mean how to do it efficiently, e.g., is there any version of diff2 available?

Would be great to have help,
Gleb

Updated on 2013-05-03T01:37:41Z at 2013-05-03T01:37:41Z by glebB
• Petr Vilím
29 Posts
ACCEPTED ANSWER

Re: 2D packing++ and which software

‏2013-05-17T08:48:37Z
• glebB
• ‏2013-05-17T01:17:32Z

Dear Petr,

thanks a lot, this finally clarifies the difference about Ilo... and Ilc... I wish the documentation was that readable!

In packing problems, the cumulative constraints are redundant, however very helpful to accelerate the search. But they are not enough; we still need the non-overlapping constraint such as this (with tasks1, tasks2 similar to sched_cumul):

// NON-OVERLAPPING: non-disjunctive
for (int i=0;i<m-1;++i)
for (int j=i+1;j<m;++j) {
if (w[i]+w[j] <= W and h[i]+h[j] <= H) {
model.add(IloEndOf(tasks1[i]) <= IloStartOf(tasks1[j])
or IloEndOf(tasks1[j]) <= IloStartOf(tasks1[i])
or IloEndOf(tasks2[i]) <= IloStartOf(tasks2[j])
or IloEndOf(tasks2[j]) <= IloStartOf(tasks2[i])
);
} else
if (w[i]+w[j] > W) { // this is our "resource"
model.add(IloEndOf(tasks1[i]) <= IloStartOf(tasks1[j])
or IloEndOf(tasks1[j]) <= IloStartOf(tasks1[i])
);
} else
if (h[i]+h[j] > H) { // this is our "time"
model.add(IloEndOf(tasks2[i]) <= IloStartOf(tasks2[j])
or IloEndOf(tasks2[j]) <= IloStartOf(tasks2[i])
);
} else
assert(0);
}

Is this an efficient way to model non-overlapping in CP Optimizer?

I cannot use OPL because calling the solver from a C++ application.

Gleb

Hello Gleb,

I see that you really need 2D packing and not only cumulative resources. Unfortunatelly, the first "or" constraint over 4 different cases cannot be improved. The other two "or" constraints seems to me to be redundant, cumulative functions for "resource" and "time" should propagate that better than the "or". Is it the case? If it is, the propagation may be a bit faster without them.

There is one more example that may be interesting for you: sched_square.cpp. In this example the problem is to place small squares into a big square such that they do not overlap. The model is very similar to yours. There is one more improvement though: usage of search phases. In this example, it helps to first decide all x-axis coordinates only then decide y-axis:

IloSearchPhaseArray phases(env);
phases.add(IloSearchPhase(env, x));
phases.add(IloSearchPhase(env, y));

if (cp.solve(phases)) {

Maybe it can help in your case too? First decide all times and only then resources or vice versa.

You can also try to increase inference level for cumulative functions to invest more time into propagation of cumulative constraints:

```    cp.setParameter(IloCP::CumulFunctionInferenceLevel, IloCP::Extended);
```

With this setting, cumulative functions can propagate more. However whether it helps the search depends on the problem.

Otherwise I don't see anything else what can be improved.

Best, Petr

Updated on 2013-05-17T08:59:07Z at 2013-05-17T08:59:07Z by Petr Vilím
• Petr Vilím
29 Posts

Re: 2D packing++ and which software

‏2013-05-06T13:26:57Z

Hello Gleb,

Definitely choose CP Optimizer over ILOG CP that is much older (new versions of ILOG CP only fix bugs).

From what I understand, cumulative functions in CP Optimizer may be what you need. Cumulative function is an abstraction of a resource such as limited capacity storage. The function maintains used capacity over time, and it is possible to constraint minimum/maximum capacity usage during different time periods. Is that what you need?

Cumulative function is illustrated e.g. by example sched_cumul that is delivered together with CP Optimizer. There are two versions of this example: in C++ and in OPL. A good starting point that describe the concept in mathematical terms may be the following page in the CP Optimizer documentation:

IDE and OPL > OPL Interfaces > C++ interface reference manual > Concepts > Introduction to Scheduling Concepts in CP Optimizer

Regarding difference between Ilo and Ilc, it stays the same for ILOG CP and CP Optimizer. Classes starting with Ilo are Concert classes that are used to model the problem. The solving engine doesn't use Concert classes during the solve though. It first "extracts" the model from Ilo into Ilc classes. Most of the time, Ilo classes are enough. Ilc classes are necessary only for development of custom constraints or custom search. Note also that you don't have to use even Ilo classes and instead model the problem using OPL modeling language and use full power of OPL Optimization Studio.

Best, Petr

• glebB
3 Posts

Re: 2D packing++ and which software

‏2013-05-17T01:17:32Z

Hello Gleb,

Definitely choose CP Optimizer over ILOG CP that is much older (new versions of ILOG CP only fix bugs).

From what I understand, cumulative functions in CP Optimizer may be what you need. Cumulative function is an abstraction of a resource such as limited capacity storage. The function maintains used capacity over time, and it is possible to constraint minimum/maximum capacity usage during different time periods. Is that what you need?

Cumulative function is illustrated e.g. by example sched_cumul that is delivered together with CP Optimizer. There are two versions of this example: in C++ and in OPL. A good starting point that describe the concept in mathematical terms may be the following page in the CP Optimizer documentation:

IDE and OPL > OPL Interfaces > C++ interface reference manual > Concepts > Introduction to Scheduling Concepts in CP Optimizer

Regarding difference between Ilo and Ilc, it stays the same for ILOG CP and CP Optimizer. Classes starting with Ilo are Concert classes that are used to model the problem. The solving engine doesn't use Concert classes during the solve though. It first "extracts" the model from Ilo into Ilc classes. Most of the time, Ilo classes are enough. Ilc classes are necessary only for development of custom constraints or custom search. Note also that you don't have to use even Ilo classes and instead model the problem using OPL modeling language and use full power of OPL Optimization Studio.

Best, Petr

Dear Petr,

thanks a lot, this finally clarifies the difference about Ilo... and Ilc... I wish the documentation was that readable!

In packing problems, the cumulative constraints are redundant, however very helpful to accelerate the search. But they are not enough; we still need the non-overlapping constraint such as this (with tasks1, tasks2 similar to sched_cumul):

// NON-OVERLAPPING: non-disjunctive
for (int i=0;i<m-1;++i)
for (int j=i+1;j<m;++j) {
if (w[i]+w[j] <= W and h[i]+h[j] <= H) {
model.add(IloEndOf(tasks1[i]) <= IloStartOf(tasks1[j])
or IloEndOf(tasks1[j]) <= IloStartOf(tasks1[i])
or IloEndOf(tasks2[i]) <= IloStartOf(tasks2[j])
or IloEndOf(tasks2[j]) <= IloStartOf(tasks2[i])
);
} else
if (w[i]+w[j] > W) { // this is our "resource"
model.add(IloEndOf(tasks1[i]) <= IloStartOf(tasks1[j])
or IloEndOf(tasks1[j]) <= IloStartOf(tasks1[i])
);
} else
if (h[i]+h[j] > H) { // this is our "time"
model.add(IloEndOf(tasks2[i]) <= IloStartOf(tasks2[j])
or IloEndOf(tasks2[j]) <= IloStartOf(tasks2[i])
);
} else
assert(0);
}

Is this an efficient way to model non-overlapping in CP Optimizer?

I cannot use OPL because calling the solver from a C++ application.

Gleb

Updated on 2013-05-17T01:41:55Z at 2013-05-17T01:41:55Z by glebB
• Petr Vilím
29 Posts

Re: 2D packing++ and which software

‏2013-05-17T08:48:37Z
• glebB
• ‏2013-05-17T01:17:32Z

Dear Petr,

thanks a lot, this finally clarifies the difference about Ilo... and Ilc... I wish the documentation was that readable!

In packing problems, the cumulative constraints are redundant, however very helpful to accelerate the search. But they are not enough; we still need the non-overlapping constraint such as this (with tasks1, tasks2 similar to sched_cumul):

// NON-OVERLAPPING: non-disjunctive
for (int i=0;i<m-1;++i)
for (int j=i+1;j<m;++j) {
if (w[i]+w[j] <= W and h[i]+h[j] <= H) {
model.add(IloEndOf(tasks1[i]) <= IloStartOf(tasks1[j])
or IloEndOf(tasks1[j]) <= IloStartOf(tasks1[i])
or IloEndOf(tasks2[i]) <= IloStartOf(tasks2[j])
or IloEndOf(tasks2[j]) <= IloStartOf(tasks2[i])
);
} else
if (w[i]+w[j] > W) { // this is our "resource"
model.add(IloEndOf(tasks1[i]) <= IloStartOf(tasks1[j])
or IloEndOf(tasks1[j]) <= IloStartOf(tasks1[i])
);
} else
if (h[i]+h[j] > H) { // this is our "time"
model.add(IloEndOf(tasks2[i]) <= IloStartOf(tasks2[j])
or IloEndOf(tasks2[j]) <= IloStartOf(tasks2[i])
);
} else
assert(0);
}

Is this an efficient way to model non-overlapping in CP Optimizer?

I cannot use OPL because calling the solver from a C++ application.

Gleb

Hello Gleb,

I see that you really need 2D packing and not only cumulative resources. Unfortunatelly, the first "or" constraint over 4 different cases cannot be improved. The other two "or" constraints seems to me to be redundant, cumulative functions for "resource" and "time" should propagate that better than the "or". Is it the case? If it is, the propagation may be a bit faster without them.

There is one more example that may be interesting for you: sched_square.cpp. In this example the problem is to place small squares into a big square such that they do not overlap. The model is very similar to yours. There is one more improvement though: usage of search phases. In this example, it helps to first decide all x-axis coordinates only then decide y-axis:

IloSearchPhaseArray phases(env);
phases.add(IloSearchPhase(env, x));
phases.add(IloSearchPhase(env, y));

if (cp.solve(phases)) {

Maybe it can help in your case too? First decide all times and only then resources or vice versa.

You can also try to increase inference level for cumulative functions to invest more time into propagation of cumulative constraints:

```    cp.setParameter(IloCP::CumulFunctionInferenceLevel, IloCP::Extended);
```

With this setting, cumulative functions can propagate more. However whether it helps the search depends on the problem.

Otherwise I don't see anything else what can be improved.

Best, Petr

Updated on 2013-05-17T08:59:07Z at 2013-05-17T08:59:07Z by Petr Vilím
• glebB
3 Posts

Re: 2D packing++ and which software

‏2013-05-20T05:39:46Z

Hello Gleb,

I see that you really need 2D packing and not only cumulative resources. Unfortunatelly, the first "or" constraint over 4 different cases cannot be improved. The other two "or" constraints seems to me to be redundant, cumulative functions for "resource" and "time" should propagate that better than the "or". Is it the case? If it is, the propagation may be a bit faster without them.

There is one more example that may be interesting for you: sched_square.cpp. In this example the problem is to place small squares into a big square such that they do not overlap. The model is very similar to yours. There is one more improvement though: usage of search phases. In this example, it helps to first decide all x-axis coordinates only then decide y-axis:

IloSearchPhaseArray phases(env);
phases.add(IloSearchPhase(env, x));
phases.add(IloSearchPhase(env, y));

if (cp.solve(phases)) {

Maybe it can help in your case too? First decide all times and only then resources or vice versa.

You can also try to increase inference level for cumulative functions to invest more time into propagation of cumulative constraints:

<pre dir="ltr"> cp.setParameter(IloCP::CumulFunctionInferenceLevel, IloCP::Extended); </pre>

With this setting, cumulative functions can propagate more. However whether it helps the search depends on the problem.

Otherwise I don't see anything else what can be improved.

Best, Petr

Dear Petr,

thank you for the hints. The example sched_square would have been very helpful in the beginning if the documentation had pointed out its existence. Here are the results: for "mutually exclusive" items the cumulative constraint is indeed sufficient. But the removal of the "or" did not change anything in the results.

Search strategy is indeed important. For difficult instances, in addition to separation of dimensions you spoke of, it is efficient to sort items by decreasing size/area or measure the failure rate:

IloSearchPhaseArray phaseArray(env);
IloVarSelectorArray varSelArray(env);
varSelArray.add(IloSelectSmallest(// 3,       // mult selection is bad
IloVarSuccessRate(env)));
// varSelArray.add(IloSelectSmallest(3, IloDomainSize(env)));
// varSelArray.add(IloSelectSmallest(IloDomainMin(env)));
IloSearchPhase xPhase(env, X, // separation of dimensions is important!
varSelArray,
// IloSelectSmallest(IloVarSuccessRate(env)),
// IloDomainSize(env)), // X23 !
// IloVarIndex(env, X)),
IloSelectSmallest(IloValue(env))
);
phaseArray.add(xPhase);
IloSearchPhase yPhase(env, Y, varSelArray,
// IloSelectSmallest(IloVarSuccessRate(env)),
// IloDomainSize(env)), // X23: good
// IloVarIndex(env, Y)),
IloSelectSmallest(IloValue(env))
);
phaseArray.add(yPhase);

However, this more complicated search strategy seems to require pure integer variables which I had to produce like this:

IloIntVarArray X(env, m), Y(env, m);
for (int i=0;i<m;++i) {
X[i] = IloIntVar(env, 0, H-h[i]);
model.add(X[i] == IloStartOf(tasks1[i]));
Y[i] = IloIntVar(env, 0, W-w[i]);
model.add(Y[i] == IloStartOf(tasks2[i]));
}

Adding (IloCP::CumulFunctionInferenceLevel, IloCP::Extended) halved the number of branches in a difficult instance.

Best,
Gleb

• Petr Vilím
29 Posts

Re: 2D packing++ and which software

‏2013-05-20T07:33:36Z
• glebB
• ‏2013-05-20T05:39:46Z

Dear Petr,

thank you for the hints. The example sched_square would have been very helpful in the beginning if the documentation had pointed out its existence. Here are the results: for "mutually exclusive" items the cumulative constraint is indeed sufficient. But the removal of the "or" did not change anything in the results.

Search strategy is indeed important. For difficult instances, in addition to separation of dimensions you spoke of, it is efficient to sort items by decreasing size/area or measure the failure rate:

IloSearchPhaseArray phaseArray(env);
IloVarSelectorArray varSelArray(env);
varSelArray.add(IloSelectSmallest(// 3,       // mult selection is bad
IloVarSuccessRate(env)));
// varSelArray.add(IloSelectSmallest(3, IloDomainSize(env)));
// varSelArray.add(IloSelectSmallest(IloDomainMin(env)));
IloSearchPhase xPhase(env, X, // separation of dimensions is important!
varSelArray,
// IloSelectSmallest(IloVarSuccessRate(env)),
// IloDomainSize(env)), // X23 !
// IloVarIndex(env, X)),
IloSelectSmallest(IloValue(env))
);
phaseArray.add(xPhase);
IloSearchPhase yPhase(env, Y, varSelArray,
// IloSelectSmallest(IloVarSuccessRate(env)),
// IloDomainSize(env)), // X23: good
// IloVarIndex(env, Y)),
IloSelectSmallest(IloValue(env))
);
phaseArray.add(yPhase);

However, this more complicated search strategy seems to require pure integer variables which I had to produce like this:

IloIntVarArray X(env, m), Y(env, m);
for (int i=0;i<m;++i) {
X[i] = IloIntVar(env, 0, H-h[i]);
model.add(X[i] == IloStartOf(tasks1[i]));
Y[i] = IloIntVar(env, 0, W-w[i]);
model.add(Y[i] == IloStartOf(tasks2[i]));
}

Adding (IloCP::CumulFunctionInferenceLevel, IloCP::Extended) halved the number of branches in a difficult instance.

Best,
Gleb

Hello Gleb,

I'm sorry that I didn't mention example sched_square sooner. I think that at this point you have the best possible model.

Note that CP Optimizer has two different built-in search procedures: for integer variables and for interval variables. As you noticed, the search for integer variables can be configured in more detail. The way you construct the integer variables is the right one. Note that switching from interval variables to integer variables not only allows to better configure the search, but it also switches to a different search proccedure.

By default, search for integer variables is making decision based on impacts. It is highly effective strategy. You may try to also use integer variables but ommit selection criteria. That's the last hint that comes to my mind.

Best, Petr