Originally posted by: TonyWangyanchun

Hi,

I have been struggling with this problem weeks, but no progress, could someone tell me where the problem is and how I can solve it. Any response will be appreciated.

When I solve my model, it will take a long time to get the optimal solution, sometimes it will take several hours, so terrible.

The information appears on the screen again and again, with memory usage and solutions number increasing.

  10535  8034       98.4944   105       98.3980       98.4984   147607    0.10%

  11029  8462       98.4954   110       98.3980       98.4984   151046    0.10%

Elapsed time = 131.27 sec. (98465.66 ticks, tree = 58.53 MB, solutions = 7) ---here, time can be a couple of hours with more than 30 solutions, at last it will be out of memory or reach the time limit specified

  11504  8872       98.4954   100       98.3980       98.4984   154063    0.10%

As for the model and the constraints, please see attached for reference.

Thank you very much!

Tony

First, you're within one tenth of one percent of optimal (which means you may very well have the optimal solution, but need to tighten the bound a bit further to prove optimality). You should seriously consider declaring victory and moving on.

If you really must prove optimality, then you need to clarify: are you saying that the solver actually spent a couple of hours and gobbled large amounts of memory between node 11029 and node 11504 (which would suggest something pathological about the node LPs at that point), or are you saying that in other runs it can get stuck? If the latter, be advised that taking two or more hours to solve a MIP is quite common. Taking two or more days is not uncommon (athough it's perhaps uncommon for anyone to let one run that long).

You can help RAM consumption by making sure that CPLEX is set to write portions of the node log to disk as it gets big. If you want to try for better speed, write a difficult problem to a SAV file and try the tuning tool in the interactive optimizer on it. The tuning tool is documented in the user manual.

Originally posted by: TonyWangyanchun

Hi PaulRubin,

Thank you so much for your help.

The log above is only an example, I means it can get stuck in other runs. and I need the optimal solution as well.

I have tried to write portions of the node log to disk, and the problem of out of memory can be avoided.  But I didn't try the tuning tool and I will do that if necessary.

I'm also wondering whether there are some problems to optimise in my model.

There are much more variables than constraints in my model. Now when I build my model, I just create the variables, and add the constraints one by one to my model as the model file attached described, and I didn't use matrix or something like this. I don't know how to reformulate to let it run more efficiently and effectively.

Is there any special algorithm or data structure to use to get a better performance for this kind of model? 

Thanks.

Tony

Originally posted by: TonyWangyanchun

Today I got the result below when running my program, anyone can tell me if this is normal?

Thanks.

What you are seeing is not unexpected. Proving optimality can take a very long time and may require a very large search tree (after all, these are NP hard problems we are solving here).

I have tried here the model you attached to the first post and it solves at the root node with CPLEX 12.6.0.1. What version of CPLEX do you use? Was that model one for which CPLEX struggles or was it just an example to illustrate the structure of your model? Also, the constraints you posted seem to be unrelated to each other? The first three constraints only involve variables X while the last constraint does not use any X variables. The last constraint is a 'strictly less'. Is that intended or should it be "less than or equal"?

When you look at the log file of a very long run, can you tell whether the problem is finding the optimal solution or raising the dual bound to actually prove optimality? Do you see new solutions being found near the end of the search?

Originally posted by: TonyWangyanchun

The version of CPLEX I use is 12.6.0 (academic license). The model I attached above is not very clear, and here I give an example, hope this can make it clearer.

The problem is like this: There are N(I use 5 by default) catalogue of items, each catalogue has R items and each item have D (use 6 by default) attributes(<attr0, ..., attrD>, all are double type). There are M user requirements which is described with a vector that also have D dimensions (<req1, ..., reqD>), For M end-users, there are M*N*R 0-1 variables Xk,i,j (k=1, …, M, i=1, …, N, j=1, …, R and Dk,i,j={0, 1}), Xk,i,j being 1 if the jth item in the ith catalogue is selected  for end-user k, 0 otherwise.

the model should comply the following constraints as well:

1) Must select one (only one) item from each catalogue for each user;

2) Each item can only be selected by at most one user;

3) Must select M items from each catalogue to satisfy M user (there are more than M items in each catalogue, that means some items will not be selected for any user, so I think there's something wrong in the model in the first post, it should be sum(Xk,i,j) <=1, where k=1, ..., M)

4) The sum of attribute values for each dimension of item selected, should be less than that dimension of user's requirements values. for example, for user0, item0 is selected from catalogue0, ..., item4 is selected from catalogue4(this means X0,0,0=1, X0,1,1=1, X0,2,2=1, X0,3,3=1, X0,4,4=1, all other Xk,i,j = 0), and then item0[0] + item1[0] + item2[0] + item3[0] + item4[0] <= user0's requirement[0];

5) The objective is minimise the sum of 0th attribute of all items selected.

I attached a model file with N=5, M=10, and R=100, and the log file generated when running the model. I didn't get the final solution before I stopped it. And I attached a solution example file to show what it looks like. 

I don't know how to check whether the problem is finding the optimal solution or raising the dual bound to actually prove optimality, I'm not familiar with Cplex and no much background knowledge in optimisation, this is why I was struggling with this problem for weeks.