Dual simplex method for problems not dual feasible

I understand that MATLAB uses the HiGHS Dual Simplex algorithm tas its default solver for Linear Programming problems. What I wanted to know was how does it use the Dual Simplex problems for LP problems that are not Dual Feasible? I am teaching a subject on Linear Programming and I would like my students to have some idea of what is going on behid the scenes. I understand how to use Dual Simplex for problems that are dual feasible, but not sure what MATLAB does when the problem isn't.

Can anyone point me to any references that detail how the dual simplex method works for problems that are not dual feasible. The standard textbooks suggest the two-phase method, but that uses the Primal Simplex method, not the Dual Simplex method. In the reference by Vanderbai he suggests a method where you replace the objectivive function with a dual feasible one for Phase One but then phase 2 uses the Primal simplex method, which misses out on the advantages of the dual simplex method.

Any pointers to the actual method used woulf be much appreciated.

Thanks, Glenn

[Matt J]

If the dual problem is not feasible, the primal is unbounded or infeasible, so the solver will just bail out in that case with an empty solution and a diagnosis message (primal unbounded or primal infeasible). Are you just asking what procedure is followed, after determining dual infeasibility, to diagnose the primal? If so, I imagine that that is handled by the HiGHS software called by Matlab. I don't think Matlab itself does much of the work.

[Glenn]

"If the dual problem is not feasible, the primal is unbounded or infeasible"

This is not always true. It just means that the standard dual simplex method cannot start, but the problem is not neccessarity infeasible or unbounded. I can illustrate this with an example.

max z = -x_1 + 2x_2

s.t. 2x_1 + x_2 <= 4

x_1 - x_2 <= -1

with x_1, x_2 non-negative.

The standard dual simplex method cannot start because the dual problem is not feasible (i.e. not dual feasible). But MATLAB can find a solution z^*=8, x^* = (0,4).

I would like to understand how it finds this solution. I do understanfd that HiGHS does all the work but I am hoping someone here undestands it well enoug that they can point me to what exactly it is doing.

Thanks, Glenn

Answer 1

[Matt J]

This is not always true.

It is always true, by the Strong Duality Theorem. Once it has been determined that the dual is infeasible, neither Matlab nor HiGHS should have anything else to do but report whether the primal is unbounded or infeasible.

Regarding your example,

max z = -x_1 + 2x_2

s.t. 2x_1 + x_2 <= 4

x_1 - x_2 <= -1

x_1 >= 0, x_2 >= 0

by my math, the dual to this problem is as below, and it is not infeasible. For example y1=2, y2=0 is one feasible point.

[Glenn]

sorry, but y1=0, y2=0 is not a basic feasible solution of the dual problem. it doesnt satisfy the second constraint since 0-0 is not greater than or equal to 2. if you were to solve the dual problem using the standard simplex method you would have to use the two-phase method, introducing an artificial variable, to generate a suitable starting basis.

I also dont think the stong duality theorem is relevant to the discussion here since, my original problem does have the optimal solution x1=0, x2=4 (which satifies all constraints and has a maximum objective z=8), The optimal solution is not infeasible nor unbounded. My matlab code is here, if you wish to check.

clear;

f = [-1; 2];

A = [2 1; 1 -1];

b = [4; -1];

L = [0; 0];

[x,zn]=linprog(-f,A,b,[],[],L)

[Matt J]

sorry, but y1=0, y2=0 is not a basic feasible solution of the dual problem

Not sure why we're considering y=[0,0]. The feasible solution that I proposed is y=[2,0]. I believe that this solution is not only feasible, but also basic feasible, though that is not necessary to setlle whether the dual problem is feasible. We can also solve the dual problem with linprog to make sure that it is feasible.

f = [4; -1];
A = [2 1; 1 -1];
b = [-1; 2];
L = [0; 0];

[y,fdual,exitflag]=linprog(f,-A,-b,[],[],L)

Optimal solution found.

y = 2×1

2 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

fdual = 8

exitflag = 1

I also dont think the stong duality theorem is relevant to the discussion here since, my original problem does have the optimal solution x1=0, x2=4 (which satifies all constraints and has a maximum objective z=8)

That's why the duality theorem is relevant. Because your original problem, the primal, is feasible and has an optimal solution, the strong duality theorem assures that the dual problem must have one as well, i.e., the dual can't be infeasible.

[Glenn]

I misread your reponse, sorry, and mistook your y1=2, y2=0 for y1=0, y2=0. I think we are still not communicating well, a I blame myself for using imprecise termininology. I am not gettitng my original question answered because we are getting side-tracked. I do not care about the optimal feasible solution, which you seemed to be focussed on. (Which is why I claimed the Strong Duality theorem was not relecvent here)

I am interested in the Initial Basic Feasible solution that is used to start the Dual Simplex method, and how MATLAB (actually HiGHS) finds it. This is the first step to using the Dual Simplex method, and what I mean by it requiring that the problem be Dual Feadible is that the Intial Basic Solution of the DUal problem be Feasible, not the final optimal solution, which you correctly point out is y^* = (2,0).

[Glenn]

What I am talking about is the basic solution after you add slack variables to the dual prblem, which is s1 = 1, s2 = -2, where s1, s2, are the introduced slack variables dfor the dual problem. This is not feasible, due to the negative value, so the simplex method cannot get started, start, since it pivots fram basic feasible soluti9n to adjacent basic feasible solution. So is MATLAB/HiGHS then using a two-phase method, where it introduces an additional artifical variable? If so, then what does this look like in the primal problem, and is this what MATLAB doing?

I guess this is not strictly a MATLAB question, so I an thinking it might be better to take it to another forum, but I was just hoping someone could point me to a suitable reference that discusses how the dual simeplex method notmally works for such problems.

I've not seen any examples similar to my example, except in the Vanderbei book, page 73. But this method reverts to the primal simplex method for phase 2. I dont think that MATALB/HiGHS does this becuase it would give up some of the benefits of using the dual simplex method over the primal simplex method.

I hope this clears up what I was asking about.

[Matt J]

To my understanding:

(1) The dual simplex algorithm (both the HiGHS and legacy implementations) does not introduce slack variables into the dual problem. It still operates on the primal in standard form.

(2) Dual feasibility at a particular iteration is violated iff the reduced cost vector z has some negative entries.

(3) The dual simplex method will not necessarily choose the slack variables as the initial basis. It has ways of choosing the initial basic variables so that the starting point is always dual feasible, i.e., so that z>=0.

In your example problem, the basis x2, s1 works as an initial basis:

f= -[-1; 2];
A = [2 1; 1 -1];
b = [4; -1];

i=[2,3];  %basic variables
Q=[A,eye(2)];
B=Q(:,i);

c=[-f;0;0];

z=c.'- c(i).'*(B\Q)  %z>=0 ==> dual feasible

z = 1×4

1 0 0 2

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

How it locates the initial basis to ensure dual feasibility is murky to me... But if one cannot be found, it means that the dual LP is infeasible as a whole and therefore (by strong duality) the primal LP is not solvable.

[Glenn]

Yes, but the dual simplex is equivalent to the standard primal simplex method operating on the dual problem, even though it is uneccessary to refer directly gto the dual. So it, effectively, does introduce slack variables into the dual, just as the standard (pirmal) simplex introduces slack variables to turn the inequalities into equalityes to solve the system.

You have described the standard two-phase method used with the standard simplex method, but nit with the dual simplex method. I have tried applying this method to the dual problem to my exmaple problem, but I couldn't derive any insights about how this would apply to the dual simplex method used on the prmal problem. I can provide a PDF file of this if you are interested.

I heard back from a developer of HiGHS,

For a maximization problem, internally HiGHS negates the cost vector and minimizes.

In dual phase 1, the original bounds on variables and constraints are replaced with finite lower and upper bounds of modified problem

• [-1, 0] if there was only a finite upper bound
• [0, 1] if there was only a finite lower bound
• [0, 0] if there were finite lower and upper bounds

Hence, for any basis, the dual values are feasible for the modified problem, if the non-basic primal variables are set to their lower or upper bound according to the sign of the dual. The basis is not generally primal feasible, so HiGHS performs phase II dual simplex iterations until a primal feasible point is obtained.

However, since the dual objective value for the modified problem is the negated sum of dual infeasibilities in the original problem, if the optimal (primal) objective value of the modified problem is zero, then the dual values are feasible for the original problem. In this case, the original bounds are restored, and phase II dual simplex iterations are performed. If primal feasibility is obtained, then a primal and dual feasible (hence optimal) solution to the original problem has been found. If dual unboundedness is found, then the original problem is primal infeasible.

If the optimal (primal) objective value of the is negative, then the original problem is not dual feasible. Hence, it's either primal infeasible or unbounded, and HiGHS (by default) distinguishes this using its primal simplex solver.

He said the method was based on the paper Koberstein and Suhl Comput Optim Appl (2007) 37: 49–65.

It does not seem that HiGHS is introducing any artificial variables, like the standard two-phase method. But this paper answers the question of what MATLAB/HiGHS is doing, although I am yet to understand the paper.

Glenn

Answer 2

[Matt J]

Can anyone point me to any references that detail how the dual simplex method works for problems that are not dual feasible.

I came across this,

https://d-nb.info/978580478/34?utm_source=chatgpt.com

Section 4 seems relevant to the question of how to get a dual feasible initial basis.

So is MATLAB/HiGHS then using a two-phase method, where it introduces an additional artifical variable?

According to ChatGPT (to the extent you can trust it), both the legacy dual simplex and the HiGHS implementation will indeed resort to a two-phase method if the standard, slack-based initialization fails. However HiGHS has all kinds of preprocessing that might make it harder for that failure to occur.

The Phase I problem is set up as below with auxiiliary variables .

This auxiliary LP, which always has a trivial dual and primal feasible starting basis (x=0,a=b), is solved using dual simplex. In the course the dual simplex iterations, the reduced cost of both the auxiliary LP and the original LP are monitored. As soon as the following conditions are satisfied at a given iteration, the iterations of Phase I can stop and Phase II can begin.

(1) All a_i=0

(2) All reduced costs in the original problem are >=0

Eventually condition (1) will be reached, since that is the optimal solution for the Phase I LP. However, there is never a guarantee that condition (2) will be reached, even once Phase I converges. In that case, Phase I has failed to find a dual feasible point for the original LP.

If Phase I fails, the algorithm resorts to subsequent heuristic stops, which ChatGPT doesn't elabroate upon, but claims that this event is rare.