Model improvements

Looking at the models used in the paper http://www.ime.usp.br/~egbirgin/publications/rob.pdf I noticed that a few standard “improvements” could be introduced. Here is an example:

First equations (13) and (14) have the same RHS. Hence it makes sense to introduce a new variable for this.

Secondly, when we look at the AMPL models provided by the authors, we see:

R1 {j in 1..n}:     T[j] >=   ( S[j,m] + sum{i in 1..n} ( x[i,j] * p[i,m] ) )             - sum {i in 1..n} ( x[i,j] * d[i] ); R2 {j in 1..n}:     E[j] >= - ( S[j,m] + sum{i in 1..n} ( x[i,j] * p[i,m] ) )             + sum {i in 1..n} ( x[i,j] * d[i] );

I.e. they substituted out C[j,m]. I would probably leave that as it was formulated in the paper.

Now, do these improvements really work? As is sometimes the case: the results on a single instance can be misleading. So here were my experiments:

		old version	new version
size	rows	335	500
	cols	405	570
	nz	5635	3865
gurobi	iterations	1060935	453173
	nodes	31220	5971
	time	60	38
cbc	iterations	4589173	4790425
	nodes	36154	49851
	time	395	478

We see that my version has fewer nonzero elements at the expense of more variables and equations. But not with every solver (or with every instance) this pays off. CBC actually becomes slower. Most likely this can be explained with the simple argument that the solver follows a different path. To really assert that a formulation is better one really needs to run a large number of models and see how they behave on average.

Note: the reformulated model (and the computational results) already included the suggestion in the comment from Paul.