Ways to impact values of returned extreme ray of an unbounded LP

Answered

Lene Grübler

October 04, 2023 12:21

• 
• 
• 

Hi all, 

I have implemented a Benders decomposition using Gurobi's Python package and it does solve my problem correctly. I observe that the algorithm spends most of the time solving the master problem which is not surprising in the first place as the master is a MIP problem.

Going through the log file, I realized that, after a few iterations, the master problem becomes numerically instable with a matrix range of [3e-13, 2e+06].

Before adding any Benders cuts, the range has been [1e+00, 5e+05].

Based on the LP file of the master problem including the Benders cuts, I can tell that the small coefficients occur only in the feasibility cuts.

While the model can still be solved correctly with the Numeric Focus parameter of the master problem set to 3, I assume it slows down the solving process of the master problem even more.

To build the feasibility cuts I query the Unbounded Ray attribute of the dual sub problem. While I know that the extreme ray of the dual represents a direction along which the objective function value continuously increases I am wondering if I can somehow impact the values returned by the Unbounded Ray attribute in order to not unnecessarily decrease the numerical stability of my master problem by adding cuts.

As I am still a bit new to the theory of optimization I have the following questions: 

1. Is the unbounded ray returned from the dual of a linear problem always unique?
2. If not, is there any way to have Gurobi return a collection of multiple extreme rays of which I could choose one that allows me to construct numerically stable cuts?
3. Is there any way I can impact the values returned by the extreme ray attribute by adjusting model parameters and/or model definition?

 

Thanks in advance.

Related to

• Bender's
• Unbounded

0

• 

  Marika Karbstein

  • Gurobi Staff

  October 05, 2023 14:17

  Hi Lene,

  The unbounded ray does not need to be unique. However, you cannot access multiple extreme rays at once. I also see no way to "positively influence" the extreme ray information.

  But you could try to scale the values. For example, Python's fractions could help to identify rational approximations to a given floating-point number and then you can choose a scale value among the denominators.

  You could also try to get rid of very small coefficients and slightly relax your cuts.

  Hope this helps,
  Marika

  0

Please sign in to leave a comment.