How to find extreme rays

Question

I am applying Benders decomposition and the dual is unbounded. I need to find the extreme rays to proceed, but I am not sure how to do that. Following is an example problem, can someone explain how the extreme rays (3,2) (1,3) were found in this example (graphically or simplex method)? I know how to find the extreme points, but don't know how to find the extreme rays.

Problem

$$U=\{u\in\mathbb{R}_+^2 : 4u_1+2u_2\geq2, -2u_1+3u_2\geq-3, 3u_1-u_2\geq1\}$$ has extreme points $(\frac25,\frac15)^T,(\frac12,0)^T,(\frac32,0)^T$ and extreme rays $(3,2)^T,(1,3)^T$ giving the extended formulation :

$$U=\{u\in\mathbb{R}^2 :u=\begin{pmatrix}\frac25 \\\frac15 \\\end{pmatrix}\lambda_1+\begin{pmatrix}\frac12 \\0 \\\end{pmatrix}\lambda_2+\begin{pmatrix}\frac32 \\0 \\\end{pmatrix}\lambda_3+\begin{pmatrix}3\\2\\\end{pmatrix}\mu_1+\begin{pmatrix}1\\3\\\end{pmatrix}\mu_2, \\ \ \\ \lambda_1+\lambda_2+\lambda_3=1, (\lambda,\mu)\in\mathbb{R}_+^3\times\mathbb{R}_+^2\} \qquad\qquad\qquad\Box$$

Answer 1

Plot the region in two dimensions, as shown here, where $(x,y)$ corresponds to $(u_1,u_2)$.

The second and third constraints have boundary lines with slopes $2/3$ and $3/1$, yielding the extreme rays $(3,2)$ and $(1,3)$, respectively.

Answer 2

Add an objective function to the constraints so that you have an LP. Warning: There may be a significant amount of trial-and-error involved. First, you are looking for an objective for which the LP is unbounded. If you maximize $a^\prime u$ and the problem is bounded, you can try minimizing $a^\prime u$. Also, what follows once you have an unbounded LP gets you the direction vector for one of the extreme rays. You have to keep trying direction vectors (which might find the same ray(s) over and over) until you convince yourself you have all the rays. This is related to the problem of finding all optimal extreme point solutions to an LP, which as I recall is NP-hard (not that NP-anything is a huge worry when you have two variables and five constraints counting nonnegativity).

Let's say you got lucky with your objective and the problem is unbounded. In the primal simplex method, reduced costs tell you which variable is entering the basis (pivot column), and the variable leaving the basis is in the first row whose right hand side value hits zero on the way to turning negative as you increase the value of the variable in the pivot column. With an unbounded problem, you find the pivot column but no row qualifies (no RHS decreases as you increase the pivot variable). So if $v$ is the vector of entries in the pivot column, you can add any positive multiple of $v$ to the current basic feasible solution $\hat{u}$ without losing feasibility. That makes $v$ one of your rays.