Topic
  • 8 replies
  • Latest Post - ‏2013-05-02T16:40:50Z by Aaronlidebiao
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
    ChrisBr
    74 Posts

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

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

    Hello,

    Could you give us more information please?

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

    Regards,

    Chris
     

  • Aaronlidebiao
    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,

    Could you give us more information please?

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

    Regards,

    Chris
     

    Hi Chris,

    Thanks for your reply.

    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
    ChrisBr
    74 Posts

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

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

    Hi Chris,

    Thanks for your reply.

    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
    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,

    Thanks for your reply. 

    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
    Petr Vilím
    56 Posts

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

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

    Hi Chris,

    Thanks for your reply. 

    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
    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,

    Thanks for your reply.

    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
    Petr Vilím
    56 Posts

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

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

    Hi Petr,

    Thanks for your reply.

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