0

I am solving a large number (probably millions a second, maybe billions) of feasibility problems:

$max\ 0$

subject to:

$Ax \ge -b,x\ge0$

So the dual is highly degenerate but is already an initial feasible solution.

$max\ -b^Ty$

subject to:

$A^Ty\le0,y\ge0$

I have simple code from previous research that solves the dual problem quite quickly. It avoids the ratio test on the values as they are zero and uses the ratio test on the slack variables. I wanted to implement the primal version. I needed both slack variables and artificial variables for the primal. I do the ratio test on the value and general columns to break ties. Do you have to use the ratio test on other columns or could you just do lexicographical comparisons of the rows? I know you could randomly choose. I find the primal problem takes a lot longer to solve in general that the dual in my application. Is this a general property in that one way or the other is better? I want to solve via the primal as there is a bunch of literature showing how to remove redundant constraints via the simplex tableau and that's something I do a lot.

On the ratio test question here is a small example. Actual problems I process are much bigger.

$max\ z=0$

St:

$x_1-x_2 \ge 1,x_1-x_3 \ge 1,-x_2+x_3 \ge 1,-x_1+x_2+x_3 \ge 0,x_1,x_2,x_3\ge0$

The tableau for the dual looks like this:

y_1 y_2 y_3 y_4 s_1 s_2 s_3  RHS
 1   1   0  -1   1   0   0 <= 0
-1   0  -1   1   0   1   0 <= 0
 0  -1   1   1   0   0   1 <= 0
-1  -1  -1   0   0   0   0    0 z

Since the RHS is always zero we could always choose the pivot rows randomly. Some books suggest doing the ratio test against $s_1$ and if equal do $s_2$ etc. Do you need to do the ratio test beyond the check of the RHS?

Neill Clift
  • 11
  • Usually you first choose the pivot column. For this pivot column you choose that row where the ratio is minimum. – callculus42 Mar 04 '22 at 16:05
  • I am talking about breaking the tie. In the dual all the b_i are zero. So the ratio is always zero. So people take the ratio of the slack variables instead of the b_i. I am wondering if the ratio is needed rather than some ordering other of the rows. – Neill Clift Mar 04 '22 at 16:10
  • A numerical example would improve your question. It seems that your question is not well understood. – callculus42 Mar 04 '22 at 16:13
  • Added an example to show a fully degenerate dual. – Neill Clift Mar 04 '22 at 17:36
  • The dual of your maximization problem should be a minimization problem. – RobPratt Mar 04 '22 at 18:51
  • Maybe. Since the objective value is zero in both the primal and dual it's just going through the motions of trying to prove it's zero or prove it's not feasible. – Neill Clift Mar 04 '22 at 21:17

0 Answers0