7
$\begingroup$

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$$

$\endgroup$
8
  • 2
    $\begingroup$ Please read: "To what extent are math questions allowed?", what is the perspective you desire that places this question within our scope? --- If you are able, would you please edit your question and use MathJax. In the future we will require you to use MathJax, instead of leaving it for us to fixup your posts. Thank you. $\endgroup$
    – Rob
    May 4, 2022 at 8:54
  • 2
    $\begingroup$ @Rob sorry I don't know about MathJax but will update the question ASAP. I am not sure if and why this question is unwelcomed here. I am taking an advanced OR course and hence I thought this to be an appropriate venue to ask my question. Thank you. $\endgroup$ May 4, 2022 at 11:17
  • 2
    $\begingroup$ @Rob I don't think your meta link on "pure" maths questions applies here as the methodology of finding extreme rays of a polyhedron is a classic OR problem. $$$$ OP (John): Please include your efforts to solve the problem, or provide more background in terms of what you have already learnt. You may find this guidance helpful (even if your question is not homework per se). $\endgroup$
    – TheSimpliFire
    May 4, 2022 at 11:18
  • $\begingroup$ Are you looking for a graphical solution (fine in 2 dimensions, maybe in 3), a solution based on applying the simplex method to an LP by hand, or solution approaches that involve solving one or more LPs with a solver? $\endgroup$
    – prubin
    May 4, 2022 at 23:59
  • 1
    $\begingroup$ UPDATE: I have rephrased my question, basically I am stuck at how this example came up with these extreme rays. $\endgroup$ May 5, 2022 at 13:06

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.