Skip to main content

extreme rays are all 0

Awaiting user input

Comments

3 comments

  • Iason Liagkas
    Gurobi-versary
    Detective
    Thought Leader

    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 Gurobi Staff

    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
    Gurobi-versary
    Thought Leader

    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.