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.
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.
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
- 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;
Please give me some suggestion. Thank you very much.
Regards,
Aaron
- Aaronlidebiao
- 2013-04-26T18:49:10Z
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.
- 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
- Aaronlidebiao
- 2013-04-30T20:04:15Z
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
- Petr Vilím
- 2013-05-02T08:15:07Z
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
- Aaronlidebiao
- 2013-05-02T14:39:26Z
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
- Petr Vilím
- 2013-05-02T15:20:47Z
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