Skip to main content

About Farkas Dual in Benders Decomposition

Answered
Fan YANG
Edited
  • Gurobi-versary
  • Conversationalist
  • First Question

Dear,
I am working on a Benders Decomposition, and I would like to add feasiblity cuts to master problem by Farkas dual. I have several problems as:

1.  The value returned by the call of farkas dual isn't the extreme ray of the dual problem of the sub-problem?

2. The primal sub-problem is minimziation. The right hand of the sub-problem is "(B - Dy)" . I added " 0 >= r * (B-Dy)" to the master probelm, where "r" is obtained by fakas dual. But I cannot get the right solution. When I added " 0 >= (-1) * r * (B-Dy)", then the solution is right. Do you konw the reason for this?

3. Sometimes the result of r * (B-Dy) is negative, sometimes it's positive? what's the reason for this?

 

Many thanks,

Related to

0

Comments

7 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Thomas Opfer
    • Gurobi-versary
    • Thought Leader

    1. The returned vector is the Farkas Dual of the problem where it is returned from. (Obviously.)

    2./3. Do you have variables with non-trivial bounds? If yes, please read this (including the comments) in order to find out the differences between Farkas Dual and the dual ray.

    0
  • Fan YANG
    • Gurobi-versary
    • Conversationalist
    • First Question

    Hi Thomas, 

    Thanks for your reply, I am trying read and learn that page.

    Best.

    0
  • Simin Chai
    • Gurobi-versary
    • First Comment

    Hi Thomas, 

    The link you provided above does not work, and I can not access the line/website.

    Could you please provide the new reference?

    0
  • Riley Clement
    • Gurobi Staff Gurobi Staff

    Hi all,

    For what its worth I can access the link that Thomas posted.  Simin, perhaps your internet traffic is being restricted and a VPN would help?

    - Riley

    0
  • Simin Chai
    • Gurobi-versary
    • First Comment

    Hi Riley,

    Thanks for your reply.

    It is my internet problem. The link is valid.

    Best

    0
  • Tobias Adamoski
    • Gurobi-versary
    • First Comment

    Hi Fan,

    though you posted your problem some time ago, I experienced the same as you did. I am using an inequality of the form (b - By)^T * r <= 0 to generate feasibility cuts for the MP, where b is the vector of constraint RHS values of the original problem and B is the parameter matrix associated with the discrete decision variables y.

    I follow the canonical form of the MILP, therefore the primal SP is a minimization problem as is in your case. Negating the farkas dual DV vector seemed to resolve the issue for me as well, though it is not fully consistent with the formal definition of the MP model anymore...

    0

Post is closed for comments.

Didn't find what you were looking for?

New post