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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .