Topic
• 8 replies
• Latest Post - ‏2013-05-02T16:40:50Z by Aaronlidebiao
Aaronlidebiao
8 Posts

# Pinned topic Need help about Error "Allocating a block too large"

‏2013-04-26T03:27:54Z |

Hi,

When I ran a 400 cities TSP problem, the CPLEX ILOG report a error "allocating a block too large". There is no problem for my 80 cities problem.

Is anyone can help about it?

Thanks.

• ChrisBr
93 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-04-26T16:17:00Z

Hello,

What feature are you using? Cplex? CPOptimizer? OPL?
What version?
Could you provide us your model?

Regards,

Chris

• Aaronlidebiao
8 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-04-26T18:49:10Z
• ChrisBr
• ‏2013-04-26T16:17:00Z

Hello,

What feature are you using? Cplex? CPOptimizer? OPL?
What version?
Could you provide us your model?

Regards,

Chris

Hi Chris,

I used CPLEX ILOG Optimization studio 12.5.

I try MILP and CP, the error message showed up for my CP model. For the MIP model, it take forever to do the root relaxation.

Here is the CP model:

using CP;

range I=1..400;
range J=1..16;
range JJ=1..15;
range K=1..25;
range KK=1..24;
range L=1..30;
range M=1..1;

int dp[I][I]=...;
int dpf[I][L]=...;

dvar boolean x[I][J][K];
dvar boolean y[L][M];

minimize
(sum(k in K)  sum(i, m in I, j in JJ)  x[i][j][k]* x[m][j+1][k]*dp[i][m]
+ sum(i in I, l in L, m in M, k in K) x[i][1][k]*y[l][m]*dpf[i][l]
+ sum(i in I, l in L, m in M, t in KK) x[i][8][t]*y[l][m]*dpf[i][l]);

subject to{

forall (i in I)
sum(j in J, k in K)x[i][j][k]==1;

forall (j in J, k in K)
sum(i in I)x[i][j][k]==1;

forall(m in M)
sum(l in L)y[l][m]==1;
}

Please give me some suggestion. Thank you very much.

Regards,

Aaron

• ChrisBr
93 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-04-30T16:52:18Z

Hi Chris,

I used CPLEX ILOG Optimization studio 12.5.

I try MILP and CP, the error message showed up for my CP model. For the MIP model, it take forever to do the root relaxation.

Here is the CP model:

using CP;

range I=1..400;
range J=1..16;
range JJ=1..15;
range K=1..25;
range KK=1..24;
range L=1..30;
range M=1..1;

int dp[I][I]=...;
int dpf[I][L]=...;

dvar boolean x[I][J][K];
dvar boolean y[L][M];

minimize
(sum(k in K)  sum(i, m in I, j in JJ)  x[i][j][k]* x[m][j+1][k]*dp[i][m]
+ sum(i in I, l in L, m in M, k in K) x[i][1][k]*y[l][m]*dpf[i][l]
+ sum(i in I, l in L, m in M, t in KK) x[i][8][t]*y[l][m]*dpf[i][l]);

subject to{

forall (i in I)
sum(j in J, k in K)x[i][j][k]==1;

forall (j in J, k in K)
sum(i in I)x[i][j][k]==1;

forall(m in M)
sum(l in L)y[l][m]==1;
}

Please give me some suggestion. Thank you very much.

Regards,

Aaron

Hello Aaron,

Indeed, your model is very big.
With my machine, I get "not enough memory" in both cases (using CP or Cplex MILP).
The problem comes from the objective-expression, not from the number of variables (if we remove the objective-expression, the model is successfully extracted).

I encourage you to check your objective-expression. I don't claim that it is wrong, but it seems complicated. Are you sure you want to do these complicated embedded sums?

By the way, you are using "k" two time in this expression. Despite the fact that this is not forbidden, you might check if this is really what you wanted to write.

Regards,

Chris.

• Aaronlidebiao
8 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-04-30T20:04:15Z
• ChrisBr
• ‏2013-04-30T16:52:18Z

Hello Aaron,

Indeed, your model is very big.
With my machine, I get "not enough memory" in both cases (using CP or Cplex MILP).
The problem comes from the objective-expression, not from the number of variables (if we remove the objective-expression, the model is successfully extracted).

I encourage you to check your objective-expression. I don't claim that it is wrong, but it seems complicated. Are you sure you want to do these complicated embedded sums?

By the way, you are using "k" two time in this expression. Despite the fact that this is not forbidden, you might check if this is really what you wanted to write.

Regards,

Chris.

Hi Chris,

I think it is the expression I want. But I will double check again.

The problem is multiple travelling salesman problem plus the assignment problem. I think CPLEX should have the capability to handle this kind of problem, the complexity of this problem is very similar to the TSP with 400 cities.

Do you have any other suggestion? I appreciate your help.

Regards,

Debiao Li

• Petr Vilím
84 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-05-02T08:15:07Z

Hi Chris,

I think it is the expression I want. But I will double check again.

The problem is multiple travelling salesman problem plus the assignment problem. I think CPLEX should have the capability to handle this kind of problem, the complexity of this problem is very similar to the TSP with 400 cities.

Do you have any other suggestion? I appreciate your help.

Regards,

Debiao Li

Hello,

I agree with Chris, the objective expression is huge. That solver must convert the sums into into long chain off additions and that takes a lot of memory. There's no way around that.

The problem is modeled using boolean variables, it does not use the full power of CP Optimizer. It could be more intuitive to model the problem using interval variables or integer variables. And it would be probably also better representation for the solver.

Best, Petr

• Aaronlidebiao
8 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-05-02T14:39:26Z

Hello,

I agree with Chris, the objective expression is huge. That solver must convert the sums into into long chain off additions and that takes a lot of memory. There's no way around that.

The problem is modeled using boolean variables, it does not use the full power of CP Optimizer. It could be more intuitive to model the problem using interval variables or integer variables. And it would be probably also better representation for the solver.

Best, Petr

Hi Petr,

I was solving this model by the mathematical programming before. Because it take a long time to do the root relaxation for large jobs (400 jobs). And the best node take a long time to converge for the median problem. Then I tried to use CP to see what will happen.

I will double check my formulation and what is the efficient way to formulate for the binary variable optimization? Any suggestion?

Regards,

Aaron

• Petr Vilím
84 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-05-02T15:20:47Z

Hi Petr,

I was solving this model by the mathematical programming before. Because it take a long time to do the root relaxation for large jobs (400 jobs). And the best node take a long time to converge for the median problem. Then I tried to use CP to see what will happen.

I will double check my formulation and what is the efficient way to formulate for the binary variable optimization? Any suggestion?

Regards,

Aaron

Hello Aaron,

as I said, try to get rid of boolean variables. Of course, CP can be used to solve MIP or SAT problems. But its true power is somewhere else. CP has constraints (allDifferent for example) that are hard to expresses in MIP. Moreover CP has powerful propagation algorithms for those constraints.

If it is a TSP-like problem, you may try to model it for example using noOverlap constraint with setup times. A good introduction can be find in the documentation for example here:

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

Best, Petr

• Aaronlidebiao
8 Posts

#### Re: Need help about Error "Allocating a block too large"

‏2013-05-02T16:40:50Z

Hello Aaron,

as I said, try to get rid of boolean variables. Of course, CP can be used to solve MIP or SAT problems. But its true power is somewhere else. CP has constraints (allDifferent for example) that are hard to expresses in MIP. Moreover CP has powerful propagation algorithms for those constraints.

If it is a TSP-like problem, you may try to model it for example using noOverlap constraint with setup times. A good introduction can be find in the documentation for example here:

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

Best, Petr

Thanks Peter,

Do you mean the CP is the best option to solve this problem?

I am thinking that the CPLEX also can solve this MIQP problem, I just did something wrong or I can improve somehow.

Any other suggestion?

Regards,

Aaron