Originally posted by: waldstein

Hi all,

if the subproblem in the benders decomposition is a integer problem, classical way (solve a LP and obtain the dual) can not be used. Can CPLEX give any support on this case?

Thx.

Originally posted by: T_O

First of all, you can add all Benders cuts as if your problem were continous. In general, this does not suffice. If your master problem is binary, you can use additional integer optimality / feasibility cuts. If your master problem is integer but not binary, you can binarize it. If your master problem contains continous variables, i have no idea.

Best regards,
Thomas

Originally posted by: waldstein

Thomas,

thanks.

I think I do not understand your comment clearly. 

(1) My master problme is formulated as following:

min x + sigma

s.t.      Ax > b

x is binary and sigma > 0

Is above formulation binary as your said (Node it contains a continuous artifical vvariable "sigma")

(2)  Could you please explain further of "If your master problem is binary, you can use additional integer optimality / feasibility cuts"?

I have no idea how to generate this kind of integer cuts......and where I gonna put these cuts to. Am I going to put these cuts to the subproblem?

Thank you

Originally posted by: T_O

Your Problem seems appropriate for the integer cuts. Maybe it helps to have a look at section 4.2 of this paper.

Best regards,
Thomas

If the portion of the master problem solution passed to the subproblem consists entirely of values of binary variables, and if the subproblem is then infeasible, you can add a "no good" cut to the master (saying that at least one of the binary master variables must change value). Also, if we assume we are minimizing cost, you know that the subproblem cost must be less than the total cost of the incumbent solution minus the portion of the current master problem objective value that does not come from the subproblem. By adding that constraint to the subproblem (just for this one iteration), you may get a "no good" cut if the subproblem is feasible but incapable of improving on the incumbent. I don't know any way to get more general optimality cuts that are necessarily useful. You can still get the usual dual-based optimality cuts from the LP relaxation of the subproblem, but they may be rather loose.

Paul

Originally posted by: waldstein

Hi Paul,

thanks for the response.

I am sorry that I do not understand your comment clearly.

By "Also, if we assume we are minimizing cost, you know that the subproblem cost must be less than the total cost of the incumbent solution minus the portion of the current master problem objective value that does not come from the subproblem"

What do you mean by this sentence? Besides, why is this adding this constraint to the subproblem helpful for the integer feature of the subproblem?

thank you....

It's too messy to explain here, so I put it into a blog post. Hopefully that will be a bit clearer.

Paul