Originally posted by: waldstein

Hi all,

given a LP with simple upper bounding variables, one choice is transform the upper bounding to a constraint like xi < ui so all the variables are xi > 0 without upper bounding.

Another choice is use simplex algorithm with bounding variable. The latter has less number of constraint that the former one.

But some first-step experiments show that when the the num. of variables is less than 100 (all of them have upper bounding). Two algorithms have the same iterations and cost almost the same time. The latter even needs more computation.

I am going to test some larger examples. But before that, would you please tell me when simplex with bounded variables can be more effective?

In CPLEX solver, there are lower bound and upper bound of variables for parameter. Does CPLEX use simplex algorithm with bounding?

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Some days ago, Tobias wrote that the presolver will transform upper bound constraints into upper bounds of the variables.

If presolving is off, simplex should be faster with bounded variables for different reasons, e.g.:

• If all variables are bounded, the dual simplex algorithm does not need any phase 1 algorithm.
• The basis becomes larger if you add the bounds to the constraints. (Remember that the basis size equals the number of rows.)

Best regards,
Thomas

P.S.: Of course, there may be examples where the variant where the bounds are encoded as constraints may be faster (e.g. due to better DSE-pricing), but I would not expect that in general.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Thomas,

thanks!

Yes, I would not expect that either :)

Plus, if I obtain the final tabula of the model by simplex with bounded, how can I get the dual solution? From my initial testing result, I find it may be not the same with the final tabula of classical simplex method.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

The "missing" duals are the reduced costs. Just obtain the reduced cost vector.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Thomas,

thanks!

I have already got that and come here to update my question :)

The dual is can be found in the last row of the final tabula, the reduced cost.

Question is : some literature say their should be duals for the upper bound which is not infinite. But this part can not be found in the tabula. I compare dual optimum with primal optimum. This part is trivial for the duals of this upper boundings are approximately zero (but sometimes they are not zero). But I still want to know more about this...
Would you please help me on that?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

I have to admit that I am not an expert for the tableau method because I consider it obsolete.

Is there a version of the tableau method with upper bounds? Or do you have to add the upper bounds to the constraints to be able to use the tableau method.

Maybe somebody of the old school who still learned tableau method should help you.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Yes, tabula may be old. But I found it faster than matrix formulation of simplex. Maybe because there is not so many matrix operation. Plus, only one matrix is needed in the memory. Of course, there may be some advanced matrix formulation which I do not know.

Upper bounding do not have to transformed to constraint if using tabula.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

You might think that the tableau method is faster, but in practise it is not. Check your literature about the revised simplex method. It has something to do with the fact that you only need the basis colums in most of the simplex steps. Also remember that there are fast update procedures for LU-decompositions of the basis matrices (e.g. Forrest/Tomlin or Suhl/Suhl).

Unfortunately, I cannot help you with your problem.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Thomas,

thanks!

Yes, I did not implement revised simplex, which is my next step.

I searched that revised simplex could also handle bounding variable. Let me try to explore this.

Your reply helps me a lot. Thanks you all the same :)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Details on a revised dual simplex algorithm which can handle bounds of variables can be found here:
http://digital.ub.uni-paderborn.de/hs/download/pdf/3885?originalFilename=true

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Thomas,

thanks! it is very helpful!
#CPLEXOptimizers
#DecisionOptimization