Originally posted by: P7HD_Raca_Todosijevic

Hi all,

I would like to generate all extreme points adjacent to the optimal solution of a LP problem. Does someone know whether this is possible to do using CPLEX?

Thanks in advance.

Is there a method you can call that will do it all in a single call? Not that I know of.

Can you do it by writing code? Yes, at least with the C API. Get the optimal solution and query the variable basis statuses. Record the optimal basis, so that you can restore it easily. For each nonbasic variable, call CPXpivotin to attempt to pivot it into the basis. If successful, record the new solution as an adjacent point. If unsuccessful, record nothing. Either way, restore the optimal basis and move on to the next nonbasic variable. Note that if the optimal solution is degenerate, this may result in finding the same adjacent extreme point more than once.

I don't think the higher level APIs over a command equivalent to CPXpivotin. C++ and Java (maybe others) allow you to specify an entire set of basis statuses. The catch is that you know which variable you want to have enter the basis, but it's not obvious (to you) which one should leave. A workaround might be to set the objective coefficient of the nonbasic variable to something really attractive, limit CPLEX to a single pivot, and then reoptimize. That should bring in the target nonbasic variable. Restore the previous solution and the original objective function and repeat for the next nonbasic variable.

Paul

Originally posted by: T_O

Paul,

I just had a look at CPXpivotin and it seems that it is only applicable to pivot in slack variables (which makes sense if someone wants to delete rows and keep the basis). I think one has to call CPXpivot (which can pivot in any nonbasic variable/constraint) with CPX_NO_VARIABLE as leaving variable.

For small problems, it might be easier to use other software like Polymake.

Best regards,
Thomas

Thomas: You may be right about CPXpivot rather than CPXpivotin. I never use the C interface, so I'm not sure what goes on there.

Also agreed about Polymake (or similar) for small problems.

Originally posted by: T_O

Another thing that I am not sure about is the degenerate case (I always think about the tip of a pyramid). Might it be that one has to do all degenerate pivots and start again from there to ensure to reach all adjacent vertices? I think so, but I am not sure.

EDIT: I think this is true as one might have to inactivate several inequalities to be able to move to an adjacent vertex.

Thomas: I don't think there's a problem with the pyramid example, but I think you are correct in general. I suspect the best way to handle it may be to check for degeneracy and, if the optimal corner is degenerate, make a small perturbation to break up the degeneracy and update the solution, Then find the bases of the adjacent corners, and finally compute the unperturbed values of those corners using their bases.

I suppose another approach (without perturbation) would be to get the optimal basis, then form all possible alternative bases in which exactly one nonbasic variable becomes basic and exactly one basic variable becomes nonbasic, and ask CPLEX to switch to each of those alternative bases in turn. Some will be infeasible or invalid (singular), some may produce the same corner if they are degenerate, but it should ultimately produce all adjacent extreme points ... I think.

Originally posted by: T_O

Hmm, i think, always exchanging only one basic variable might not be sufficient.

Here is my example: Consider the 2d-unit-square with one redundant constraint:

x + y <= 2 (redundant)
x     <= 1
    y <= 1

x,y >= 0

Transform this to standard form:

x + y + s     = 2
x +       t   = 1
    y +     u = 1

x,y,s,t,u >= 0

Let for heavens sake be x,y,u an optimal basis (at vertex [1;1]).

Now obviously [0;1] is an adjacent vertex. But only the basis y,s,t belongs to this vertex. So, one has to exchange x and u by s and t.

Best regards,
Thomas

P.S.: I know that recent simplex implementations use upper and lower bounds, but for the explanation, I think this standard form is better.

Yes, you are right. I made a mistake in my previous reply (lapsed back into thinking about nondegenerate corners). I guess the correct version of what I was trying to say was that you have to look at all bases that produce the degenerate corner, and for each of those bases you then have to look at all swaps of one basic variable for one nonbasic variable. Personally, I think I would use the perturbation approach, which will be bad enough. In a high dimensional problem, there can be a lot of adjacent vertices.

Originally posted by: T_O

Paul, I think the first ansatz should be correct.

Concerning perturbation:
I'm not sure whether perturbation would not lead to the same problem. What exactly would you perturbate?

Consider my example. Make the redundant inequality a little tighter such that it looks like

___
   \
   |

Let now the lower of the 2 vertices be optimal. Then we would have the same problem.

Or are you going to perturbate something else?

Best regards,
Thomas

That's the tricky part with perturbations: a new "corner" sufficiently close to the original corner needs to be treated as identical to the original corner (different basis). The good news is that perturbation may work when you have no direct ability to manipulate the basis (and need to 'lead the solver by its nose" by tilting the objective hyperplane). The bad news is that it leaves you guessing whether a vertex very close to the perturbed original vertex is a clone of the (degenerate) original or actually a different vertex.

I guess it is cleaner to use basis manipulation if that is available. (My memory goes back to software that did not allow manual specification of pivots or bases.) Create a queue of bases to molest, initially containing the basis of the original optimal vertex. For each basis in the queue, if the basis is valid (yields a feasible vertex), try every swap of one nonbasic variable for one basic variable. If it yields a neighbor vertex, record it. If it yields the original vertex, add that basis to the queue for later processing. Repeat until the queue is empty.

Also, a key issue for the original poster: turn off the presolver before solving the model (or solve with the presolver on, store the optimal basis, reload the model, turn off the presolver and reload the basis). If the presolver eliminates any variables, all bets are off.

Paul

Originally posted by: T_O

Concerning your algorithm, one should add, that bases that were already visited should not be added to the queue. Otherwise, one would switch between different optimal bases again and again.

Concernig the presolver: I'm not sure, but shouldn't it be sufficient to disable dual reductions?

Best regards,
Thomas

First point: yes, sorry, should have pointed that out. Each basis is processed once only.

Second point: I believe you are correct. You definitely want dual reductions off, since they are based on optimality. Primal reductions, to the extent they are based on feasibility,  should just result (if anything) in projecting the original feasible region onto one in a lower dimensional space, where the algorithm still works (inflating the solution found back up to the original dimension, which CPLEX will do automatically). I don't know everything the presolver does, so I'm not 100% confident it is safe to leave primal reductions on, but I think it should be.

Cheers,

Paul