0
$\begingroup$

I am confronted with the problem of writing conditional constraints in a binary integer programming problem. Let us consider a typical knapsack problem. The constraint is that if items $1$ and $2$ are chosen then item $3$ must also be chosen. Let $x_1,x_2,x_3$ be the corresponding binary decision variables. Can I write $x_1+x_2-x_3<2$ for this constraint? Am I doing it correctly?

There is another constraint as well which says that if items $4$ and $5$ are chosen then items $6$ and $7$ must not be chosen. I feel myself unable to write this constraint. Please help me as to how to proceed.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You can derive the desired linear constraints somewhat automatically via conjunctive normal form.

The first one is $$ (x_1 \land x_2) \implies x_3 \\ \lnot (x_1 \land x_2) \lor x_3 \\ \lnot x_1 \lor \lnot x_2 \lor x_3 \\ (1 - x_1) + (1 - x_2) + x_3 \ge 1 \\ x_1 + x_2 - x_3 \le 1 $$ Similarly, $$ (x_4 \land x_5) \implies (\lnot x_6 \land \lnot x_7) \\ \lnot (x_4 \land x_5) \lor (\lnot x_6 \land \lnot x_7) \\ (\lnot x_4 \lor \lnot x_5) \lor (\lnot x_6 \land \lnot x_7) \\ (\lnot x_4 \lor \lnot x_5 \lor \lnot x_6) \land (\lnot x_4 \lor \lnot x_5 \lor \lnot x_7) \\ (1 - x_4) + (1 - x_5) + (1 - x_6) \ge 1 \land (1 - x_4) + (1 - x_5) + (1 - x_7) \ge 1\\ x_4 + x_5 + x_6 \le 2 \land x_4 + x_5 + x_7 \le 2 $$

$\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.