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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.