10
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ look at this discussion from IBM website: ibm.com/developerworks/community/forums/html/… $\endgroup$
    – Oguz Toragay
    Commented Nov 5, 2019 at 17:07
  • 1
    $\begingroup$ and also this closely related question from SO: stackoverflow.com/q/37014143 where you can find an answer to your question $\endgroup$
    – Oguz Toragay
    Commented Nov 5, 2019 at 17:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Nov 5, 2019 at 21:55
  • 1
    $\begingroup$ @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? $\endgroup$
    – Hamed Rahimian
    Commented Nov 5, 2019 at 22:13
  • 1
    $\begingroup$ 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). $\endgroup$
    – prubin ♦
    Commented Nov 6, 2019 at 23:14

1 Answer 1

Reset to default
3
$\begingroup$

There is no way to do this with CPLEX directly as far as I know, but you can use CPLEX's C++ API to code the iterative process yourself. The API allows the user to build/modify the model in C++ as well as to retrieve solutions, so you can retrieve the solution in code, add the new constraint, and resolve. You can also use the solution pool to get other vertices, but there is no guarantee that they will be close to your current optimum (I guess that depends on our definition of "neighbouring").

Improve this answer
$\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.