IBM Support

How to obtain the extreme ray when an LP is unbounded

Question & Answer


Question

How do I get the extreme or unbounded ray when an LP is unbounded?

Answer

The routines to get the unbounded ray depend on whether you are using primal or dual simplex and whether you have primal or dual unboundedness:

  1. If you are using the primal simplex optimizer and the model is primal unbounded (thus dual infeasible), you can use:
    • the routine CPXgetray in the Callable Library (C API)
    • the methods getRay of the class IloCplex in the C++ and Java APIs
    • the Cplex.Ray property in the .NET API
    • the get_ray member function of the AdvancedSolution subinterface of the cplex class in the Python API
  2. If you are using the dual simplex optimizer and the model is dual infeasible and primal unbounded, you can use:
    • the routine CPXgetray in the Callable Library (C API)
    • the methods getRay in the class IloCplex in the C++ and Java APIs
    • the Cplex.Ray property in the .NET API
    • the get_ray member function of the AdvancedSolution subinterface of the cplex class in the Python API
  3. If you are using the primal simplex optimizer and the model is primal infeasible and dual unbounded, you can obtain the extreme ray for the dual problem through:
    • the routine CPXgetpi in the Callable Library (C API)
    • the methods getDuals in the C++ , Java and .NET APIs
    • the get_dual_values member function of the SolutionInterface subinterface of the cplex class in the Python API
  4. If you are using dual simplex optimizer and the model is dual unbounded (thus primal infeasible), you can obtain the dual unbounded direction with:
    • the routine CPXdualfarkas in the Callable Library (C API)
    • the methods dualFarkas in the C++ and Java APIs
    • the DualFarkas method of the Cplex class of the .NET API
    • the dualfarkas member function of the AdvancedSolution subinterface of the cplex class in the Python API
  5. If you are using the barrier optimizer, the choice of routine depends on whether you are using primal or dual crossover. If you are using barrier method without crossover, the extreme ray is not available.

As of this writing, CPLEX's MATLAB API does not provide access to extreme rays.

Note that the dual unbounded ray in cases 3 and 4 is also a certificate of infeasibility for the primal.

Also note that all the extreme ray routines assume the existence of the basis that provided (primal or dual) unboundedness. So, if presolve detects unboundedness, these routines will not work as expected. In that case, turn presolve off and reoptimize to obtain the unbounded ray. Click here for another FAQ on unbounded status from presolve.

Finally, keep in mind that CPLEX has detected only one extreme way when it determines unboundedness in the model. For information on obtaining multiple extreme rays, click here.

[{"Product":{"code":"SSSA5P","label":"IBM ILOG CPLEX Optimization Studio"},"Business Unit":{"code":"BU053","label":"Cloud & Data Platform"},"Component":"Not Applicable","Platform":[{"code":"PF002","label":"AIX"},{"code":"PF010","label":"HP-UX"},{"code":"PF016","label":"Linux"},{"code":"PF022","label":"OS X"},{"code":"PF027","label":"Solaris"},{"code":"PF033","label":"Windows"}],"Version":"9.2;9.1.3;9.1.2;9.1;9.0;8.1;8.0;7.5;7.1;7.0;6.6;12.5;12.4;12.3;12.2;12.1;12.0;11.2.1;11.2;11.1.1;11.1;11.0.1;11.0;10.3;10.2.1;10.2;10.1.1;10.1;10.0","Edition":"","Line of Business":{"code":"LOB10","label":"Data and AI"}},{"Product":{"code":"SSSA5P","label":"IBM ILOG CPLEX Optimization Studio"},"Business Unit":{"code":"BU053","label":"Cloud & Data Platform"},"Component":"General","Platform":[{"code":"PF002","label":"AIX"},{"code":"PF010","label":"HP-UX"},{"code":"PF016","label":"Linux"},{"code":"PF017","label":"Mac OS"},{"code":"PF027","label":"Solaris"},{"code":"PF033","label":"Windows"}],"Version":"12.5;12.4;12.3;12.2","Edition":"","Line of Business":{"code":"LOB10","label":"Data and AI"}}]

Historical Number

cplex/FAQ/141

Document Information

Modified date:
16 June 2018

UID

swg21400058