1
$\begingroup$

Traditional infeasibility cut is derived under the assumption that the feasibility problem is LP instead of ILP and relies on the dual form of the LP.

Is there a systematic way of adding valid cuts for integer feasibility problems under Benders decomposition framework?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes. Search for combinatorial Benders decomposition or logic-based Benders decomposition. In particular, Benders feasibility cuts for a binary master problem are “no-good” cuts of the form $$\sum_{j\in S_0} x_j + \sum_{j\in S_1} (1-x_j) \ge 1,$$ where $S_i$ is the set of binary variables that take value $i$ in the current solution. In some cases, depending on problem structure, you can strengthen the cut by omitting one sum or the other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.