# How to access neighboring extreme points to an optimal extreme point of an LP?

Suppose that I have access to an optimal non-degenerate extreme point of an LP. I need to find some $$\epsilon$$-optimal extreme points. That is, a point $$x$$ where $$c'x \le z^{*} + \epsilon$$.

One way to do this is to add this constraint to the problem, replace the problem with a different objective function, and re-optimize. Each iteration will either generate a new extreme point, or generate a solution already existed.

Is there any way to do this systematically in Cplex? That is, retrieve the optimal basis, do one or more pivoting and get to a new extreme point, and keep the solution if is satisfies $$c'x \le z^{*} + \epsilon$$. To make the search easier, neighboring extreme points that are one pivot away are fine.

Any help is appreciated. I am using C++ Concert Technology.

• look at this discussion from IBM website: ibm.com/developerworks/community/forums/html/… – Oguz Toragay Nov 5 '19 at 17:07
• and also this closely related question from SO: stackoverflow.com/q/37014143 where you can find an answer to your question – Oguz Toragay Nov 5 '19 at 17:09
• You specified "neighboring" extreme points. Do you mean this in the sense of close in objective value, or do you mean literally one pivot away? There could be near-optimal solutions that are more than one pivot away. – prubin Nov 5 '19 at 21:55
• @prubin Ideally, I'm looking for all near-optimal corner solutions. But, since such an exhaustive search might be cumbersome, near-optimal corner solutions that are one pivot away are just fine. MIP Solution pool yetanothermathprogrammingconsultant.blogspot.com/2016/01/… seems like a way to get all near-optimal corner points, but it might not have computational justifications for large problems. Is there any way to get some near-optimal corner solutions directly with Cplex routines in C++, similar to CPXpivot in C Callable Library? – Hamed Rahimian Nov 5 '19 at 22:13
• It seems to me you have answered your own question in the second paragraph (assuming you are willing to do more than one pivot at a time). Solve the LP. Add the $\epsilon$-optimality constraint. Switch to a randomly generated objective and optimize. Store the solution if new, discard if not. Repeat. Detecting repeats is a C++ question, not a CPLEX question. You could compare to all previous recorded solutions, variable by variable; or you could use a hashing function and test for repeated hash values (might be faster, could reject a solution incorrectly). – prubin Nov 6 '19 at 23:14