Originally posted by: arains

Dear all,

I’m running a LP problem in cplex and the solution I obtain is optimal but it is not an extreme point. I use the function “cplex.setParam(IloCplex::RootAlg,1);” to use the Simplex algorithm, but still I obtain the same. Is there a parameter that I can use so I only obtain extreme points or is it a problem of my program?? Because I’m not only interest in the optimal, but I want it to be an extreme point too.

Thank you!!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Something must be wrong. The simplex algorithm should always yield an extreme point. What makes you think that your solution is not a vertex of the LP polyhedron? Did you take a look at the optimal basis?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: arains

How can I check the optimal basis?

I checked that my solution is not an extreme point by deleting one of the active variables and obtaining another feasible solution.

e.g. sol=1 1 0 1 1 --> sol'=0 1 0 1 1; Cplex returns sol whilst sol' is also a feasible solution with the same objetive value.

Thank you in advance.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You can query the basis in the C API with CPXgetbase(). For other APIs, please consult the manual.

Are you sure that your first variable is not bounded (explicitly or implicitly) above by 1?

But even if not, I don't see why your argument proves that the solution is not extreme. If your model is degenerate, then there can be multiple solutions of the same objective value.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: arains

Thank you very much for your rapid response.

Firstly, this variable is not bounded above by one since both solutions are feasible. In the other hand, for sure this problem is highly degenerated, this could be a problem?

thank you again
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The fact that the problem is degenerate means that it is no surprise that you have different solution vectors of the same objective value.

Both solutions can be vertices of the polyhedron. The fact that the first variable is not at a bound does not mean anything. It could be a constraint that is blocking its movement.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: arains

Hi everyone!

After several tests and validations I was not able to find where the problem is. In addition, the same framework was applied but with other optimization solver obtaining, in this case, a extreme point. Could be a bug in Cplex? I know this claim sounds risky but I don't know what to do anymore.

Thank you again.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I still do not understand the issue. Could you please do the following:

1. Attach a problem instance (for example an .lp file) where you see the behavior.
2. Post the solution vector that CPLEX provides.
3. Explain exactly why you think that this is not a vertex of the polyhedron defined by the constraints and bounds.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Is this because your objective function is parallel to some of your constraint set?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> jimzhang wrote:
> Is this because your objective function is parallel to some of your constraint set?

That would account for the existence of multiple optima, but the solutions reported by CPLEX must be extreme points (because the simplex algorithm only considers extreme points).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: arains

Thank you very much for all your responses. However, I have not solve the problem. I still keep trying so when I have any further comment I will post here.

Than you all!

Jon
#CPLEXOptimizers
#DecisionOptimization