general approach to iterating extreme rays of solution cone

Question

Suppose I'm at an optimal solution of an LP relaxation in a MILP branch-and-bound descent. I want to add an additional cut of my own devices. To compute this cut I need the extreme rays of the cone originating in the LP optimum. The rays will be recessionary (aka, leading away from the optimum); I have no intention of traveling them. This data should be available in the LP tableau (assuming a simplex algorithm), right? Can you explain to me the general process for reading extreme (or all) recession rays from the tableau extending from the current optimum?

A few points of my confusion on this: Some constraints should be tight at the LP optimum, and I can find those. However, I want rays, not planes. I want intersections of those constraints -- like what we walk in the simplex algorithm. Hence, it doesn't seem like a row of the tableau. It seems like it should be a column of the tableau, like the rays should be all the columns not in the optimal basis. However, the rays should have a component corresponding to each variable, and the number of rows in the tableau is not representative of the number of variables.

A third point of confusion comes from looking at SCIP. SCIP has a nice interface for adding custom "separators". It allows me to iterate through the rows and columns of the tableau, but it's not the full tableau. It seems to be missing the slack columns, but it gives me methods for getting the LHS and RHS slack values. Whatever those are, I'm not sure how I would align them between rows. Maybe this has to do with the way the "revised simplex algorithm" stores values, which thing I don't fully understand.

I'm also interested in how to iterate these rays in SCIP.

Answer 1

The cone you are describing is often referred to as a basis cone (for instance, in Sec 2.3 of this paper, where the concept is used to derive cuts too). Note that you have such a cone for every feasible basis, not just the optimal one.

Formally, consider a polyhedron $$ P = \{x \in \mathbb{R}^{n} \mid Ax \geq b \}, $$ where $A \in \mathbb{R}^{m \times n}$ and a basis consisting of $n$ linearly independent inequalities (i.e., rows of $A$). The corresponding basis cone is defined by these $n$ inequalities, whose slack variables are all non-basic (the slacks are zero because the inequalities are tight at $\bar{x}$).

Each of the $n$ rays of the basis cone corresponds to the edge that a simplex pivot would traverse if one of these non-basic slack variables were to enter the basis. Therefore, to find the extreme rays, all you have to do is write down what a simplex pivot would look like if each of the $n$ slack were to enter the basis. Of course, in general, a simplex pivot may only take a finite step, because another inequality eventually becomes tight (and the corresponding slack leaves the basis).

Bottom-line: write down the equation describing each non-basic slack entering the basis, and you'll get the $n$ extreme rays.