2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I see this similar question, but it is also lacking in good answers: or.stackexchange.com/questions/2996/… $\endgroup$
    – Brannon
    Sep 21, 2022 at 21:19
  • $\begingroup$ You say you are at an "optimal solution", meaning any recession directions either make the objective worse or keep the objective constant. Are you looking for just those that keep the objective constant? Also, I'm not sure what you mean by "extreme rays ... originating at the optimum". For any (extreme) recession direction there is a ray in that direction originating at the optimum. So are you looking for all extreme recession directions? $\endgroup$
    – prubin
    Sep 21, 2022 at 21:36
  • $\begingroup$ @prubin: yes, recession directions or constant. I'll update the question. $\endgroup$
    – Brannon
    Sep 21, 2022 at 21:37

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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