The computational complexity of an LP problem is approximately proportional to (rows2 (squared) x columns). If the number of rows in the dual (transposed problem) is lower than the number of rows in the primal, the solution may be easier to solve with the dual.
Dear Prof Pete Bettinger ,
In LP, the number of rows is equal to the number of constraints, and the number of columns is equal to the number of variables. The dual problem converses the numbers compared with the primal.
So, can I make the following conclusion:
when the constraints is more than variables in a LP problem, the dual simplex method can solve it more efficiently.
As this is RG - spell it out, please - "R" stands for "research": we should rather talk about postgraduate stuff than the incoming criterion in the simplex method or similar basic stuff. Yes?
I haven't paid attention, I guess, but are the questions posed here becoming too trivial to deal with?
One cannot tell in advance which variant will be the fastest for a problem - and besides primal and dual simplex there are interior point methods, too, which in some cases are best suited.
The practical approach of e.g. CPLEX when solving the root node LP for MILPs on modern multicore computers is: run the three in parallel and the first finishing wins. The work of two methods is wated, but the total solution time is least.
So no need to decide beforehand.
- Badges
- Science topic
- Similar topics
- Psychology
- Emotion