extreme rays are all 0

Awaiting user input

Iason Liagkas

• March 18, 2024 11:35

Hello guys, 
I have a problem that all its extreme rays are 0. Do you have any idea of what could be the case? Can we check if there are numerical issues with a problem solution that produce this result?

Kind regards
Iason

Related to

• Bender's

0

• 

  Iason Liagkas

  • March 18, 2024 11:58

  

  

  

  I want to add some context. I am applying the Benders Decomposition algorithm. And I have a Master problem and a Subproblem. It happens depending on my starting point (initial feasible solution) in the algorithm I reach to a point where the extreme rays of the problem are all 0. This is when the subproblem is infeasible. Then from theory, we know that subproblem dual could be either infeasible or unbounded. If it is unbounded then the extreme rays give us the directions that its objective function would indefinatelly improve. If the extreme rays were indeed 0 then this would mean that the subproblem dual is infeasible as well. This would imply that the initial problem would be infeasible. But I have my problem coded and I know it is feasible. So what could be an explanation that all extreme rays are 0? The first thing that comes to my mind is that I have a bug somewhere in my code. But I am wondering if there is a way that I can find out if I have no bug but this happens because of the parameter values I have, or another numerical complication.    

  0
• 

  Jaromił Najman

  Gurobi Staff

  • March 19, 2024 08:13

  Hi Iason,

  I would recommend to first investigate the cause of infeasibility. This may already answer all your questions.

  Please refer to How do I determine why my model is infeasible? for additional information.

  If this does not give any clues, then we will need to think about something else.

  Best regards, 
  Jaromił

  0
• 

  Thomas Opfer

  • March 19, 2024 18:01
  • Edited

  

  

  A typical mistake in Benders Decomposition is that some variables have non-trivial bounds (different from 0 or infinity) and not taking the reduced cost vector into account when calculating the dual ray. (See also my comment here: https://support.gurobi.com/hc/en-us/community/posts/360054671612-About-Farkas-Dual-in-Benders-Decomposition .)

  Best regards,
  Thomas

  0

Please sign in to leave a comment.