simplex method with bounded variables tool

Question

Is there any reliable tool or source code (preferably C++) for solving LPs with bounded variables by simplex method? In my problem all variables are bounded to 1.

I actually found some tools in StackOverflow posts: SoPlex, CLP and lpsolve.

Among them, SoPlex is more extensive I suppose. In the documentation, it is said that SoPlex considers variable bounds. Then it says:

"If all primal variables are within their bounds, the Simplex basis is said to be primal feasible. Analogously, if all dual variables are within their bounds, its is called dual feasible. If a basis is both, primal and dual feasible, the optimal solution has been found."

My impression is that it does not FORCE the basis to be within variable bounds, instead it checks if the variables of the solution are within the bounds. If so, it considers the solution optimal.

Are there any tools out there to find a feasible solution considering variable bounds?

That's what Linear Programming is for. Bounded variables are just natural (instead of free ones). Work through the basics of LP! — sascha
There is an implicit way to cap variables by the boundary. I want a tool that handles that. I already know the boundaries can be treated as new constraints but that's costly. — Masoud
Sure, but the question is: how long will a standard optimized LP-solver take for your problems (will you gain something through this)? And is simplex the correct tool (compared to Interior-point solvers)? — sascha
Most solvers will not handle bounds as constraints. They handle bounds implicitly. In some sense one could say bounds are free (they have no computational cost). — Erwin Kalvelagen

mattmilten mattmilten · Accepted Answer · 2016-10-29T09:58:32

LPs with bounded or boxed variables are completely normal and very common. Just like problems with ranged constraints, i.e. constraints with both a left and a right hand side.

SoPlex is capable of running both the primal and the dual simplex. It starts from a slack basis - all variables are on one bound - and shifts the bounds accordingly to make this basis primal or dual feasible for the respective simplex type.

Another possibility to get a feasible basis is to use the so-called phase 1. This solves a modified LP and switches then back to the original.

simplex method with bounded variables tool

1 Answers