Originally posted by: yokito

I have an optimization problem which I reformulated as a set partitining problem. The resulting formulation has the same number of variables and constraints as the traditional formulation. However, the set partitining problem provides better values and require less nodes.

I would like to ask which analysis I should do to compare both formulations and said which is better. Maybe with LP relax of both models for small instances? Is there any method to see that since I have to demonstrated that or similar work?

Thanks in advance!

The phrase "better values" is a bit vague. Do you mean a better incumbent objective value in the same amount of time? If so, that is one of two performance comparisons I would find useful, the other being the time needed to prove optimality (or, if neither method can do that in reasonable time, the comparative tightness of their respective bounds as a function of time).

Originally posted by: yokito

You are right. Better values in terms of objective function value. I mean I have a reformulation of a model, with same number of variables and constraints. I have made a comparison of quality of the solutions in terms of objetive function value and generated nodes within same timelimit. I also made a comparison of the bounds regarding time limit. However, the reviewers said me that it is not enough to support the reformulation. I think maybe a linear relaxation of both models and compare them. What do you suggest?

Number of nodes is not a particularly good measure - model (or algorithm) A can inspect fewer nodes than model (or algorithm) B but take much longer because each node takes longer to process.

A fairly typical way to compare two models for the same problem (or two algorithms for the same model) is to run both on a set of test problems and plot the mean incumbent value and mean bound (or mean incumbent and mean gap) for each against time. I think there's a general preference for the geometric mean over the average mean in both cases. Assuming that the reformulation is valid (not going to give an incorrect solution) and not any more prone to numerical stability problems, that should be enough. If there is some concern about the new formulation eating more memory, you could address that by also plotting mean memory consumption v. time.

If the reviewers say that is not enough, then it is fair for you to ask the editor (or associate editor) to ask the reviewers just what sort of evidence they would want ... or just switch to a different journal.

Originally posted by: yokito

Thanks for you answer.

Actually all the results you suggest me to include where already  submitted in the tables. However, since they say that there are the same number of variables and constraints, they do not see a "different" formulation. I was wondering is maybe there is a paper or some kind of study regarding a relaxation that could explain why a reformulation is better than other one besides they have the same number of contraints and variables.

Does your formulation always have the same number of constraints as variables, or is that just a property of your particular set of test problems? It could be they just want you to diversify the test set.

Originally posted by: yokito

Both formulations have the same number of variables, and the same number of contraints if we compare them. On the other hand, the number of variables is not the same as the number of contraints. The difference is that with the set partitioning we use columns. I tested both formulations for making a good comparison over all the instances from the related literature. 

Well, if the performance is different, the formulations must be different. Did you do any statistical tests to establish that the difference is statistically significant (not noise)?

I suggest you post this as a question on OR-Exchange. It really does not fit with a CPLEX forum, since it has nothing to do with CPLEX itself, and you'll get a wider audience there.

Originally posted by: yokito

Are you referring to Wilcoxon test? or what do you refer with noise? Any specific test in this case?

Ok. I will post it there. Anyway, any further indication from you is very good welcome.