Originally posted by: UserCplex

Greetings all,

I would like to revisit the question of deletion of variables/columns while doing column generation.

An earlier thread on this can be found here.

I have a large restricted master problem RMP with around 20000 constraints. In doing my tests, it is appearing that only 10% of the time is spent in the column-generation subproblem (discovering a negative reduced cost column). The remaining 90% of the time is being spent in reoptimizing the RMP once a negative reduced cost column is introduced into the RMP. I have set up the LP optimizer to be primal simplex and turned presolve ON in way of context/background.

I am looking for ways to speed up the amount of time it takes for the RMP to reoptimize.

One of the suggested ways in literature is to remove the non-basic variables from the RMP. In order to accomplish this, I have the following code where x is IloNumVarArray.

for(

int counter = 0; counter < x.getSize(); counter++)
{ 

if(cplex.getBasisStatus(x[counter]) == IloCplex::FreeOrSuperbasic)
{ x[counter].setBounds(0,0); 
} 
}

Based on the response in the thread linked to above, it appears that setting both the lower and upper bounds to 0 with presolve on is as good as removing that variable from the RMP. If the variable denoted by this column is deemed to later have a negative reduced cost, it should anyway be rediscovered by the column generation subproblem.

Is this the best way of doing it? Or is there any other way? The thing is that there are many research papers in literature that claim that reducing the size of the RMP by removing the non-basic variables from time to time helps speed up the LP solution. Is it better to turn presolve off and then set the bounds to 0?

However, in my experience on my problem, setting the lower and upper bounds to 0 did not have any effect at all in terms of the computational time.

That is, whether I reset the bounds (lower and upper) to 0 or whether I let them remain unrestricted had no effect on solution times.

Could it be that the large size of the basis (20000 x 20000) and therefore basis inversion is the bottleneck instead of the number of columns?

Thanks in advance for any insight.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Of the 90% of the time not spent in the subproblem, how much is spent adding the new column to the RMP and how much is spent pivoting?

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization