how to use simplex method for LP in matlab

Hello,

i want to use the simplex-algorithm in matlab to solve my optimization problem. After reading the threads i underestand that the simplex-algorithm is not used for

linprog, instead the dual-simplex is the default solution which essentially performs a simplex algorithm on the dual problem. How can i use the simplex-algorithm to solve my linear problem? The most relevant thread that i found is: https://uk.mathworks.com/matlabcentral/fileexchange/61086-simplex-solver

any suggestions?

Thanks!

[Matt J]

The most relevant thread that i found is:

Doesn't that solve the issue? What is wrong with the solver that you found there?

Answer 1

[Matt J]

I do find it a bit strange that the primal simplex algorithm is not an option in linprog...

However, the dual of the dual is the primal, so a simple work around might be to input the dual problem to linprog instead. That way, when linprog applies the "dual simplex algorithm", it will really be applying the simplex algorithm to the primal. The Lagrange multipliers (lambda) that it returns

[x,fval,exitflag,output,lambda] = linprog(___)

should then give you the primal solution, as found by the primal simplex algorithm.

[Pavlos]

Hello,

thanks for your prompt reply.

What i am trying to do is aply the benders decomposition method for a MILP. So spliting a complicated problem into master and slave problem.

I construct the dual-slave problem and get its solution to set the optimality and feasibility cuts for the master.

However when the dual-slave is unbounded (i.e., primal-slave infeasible) i need to extract the extreme ray to add to the feasibility cuts of the master problem.

I found that you can get the rays from the simplex algorithm, that is why i made the question.

So the question is how can you get the ray of a dual unbounded problem (withouth using CPLEX)

any suggestions?

Thanks again.

[Matt J]

OK, but what is wrong with my solution as stated so far? If you know that you need to implement the (primal?) simplex algorithm to get the extreme ray, then I've already told you how to do it.

[Pavlos]

Hello,

In my case i have formulated both the primal and the dual problem, so i can use linprog to both.

If i use linporg on the dual problem, that means that it will use the simplex-algorithm in the original primal problem, and get an unbounded solution, and some values for the lagrange multipliers.

So this lambda value, should be the ray that should be for the master feasibility cut?

[Matt J]

No, if the primal is unbounded, the Lagrange multipliers mean nothing.

[Pavlos]

The unbounded solution is for the dual. The primal actually is infeasible in this case.

So i sovle the dual e.g.,

[dualVars, dualVal, dualFlag, dualOutput, dualLamba] = linprog(g, -A_dual, -b_dual, [], [], lb_dual, ub_dual);

thanks for your time!

[Matt J]

If the primal is infeasible (and so has no solution) why was your original goal to run the primal simplex algorithm?