1
$\begingroup$

We have a set of constraints in an ILP of the following form :

$ \gamma (X_{11} + X_{12} + X_{13}) \leq C_1$ where $X_{ij} \in \{0,1\}$ and the value of $\gamma$ is going to depend on the actual value of $X_{ij}$ variable being set. For example, if $X_{11} = 1, X_{12} = 1, X_{13} = 1$ then $\gamma = 0.45$, while on the other hand, $X_{11} = 0, X_{12} = 0, X_{13} = 1$ then $\gamma = 0.76$ and so forth. How can such constraints be encoded in an ILP where the constant factor actually depends on the value of the variable

$\endgroup$

1 Answer 1

3
$\begingroup$

Given constant $C_1$, you want to enforce $$\left(X_{11} \land X_{12} \land X_{13}\right) \implies 0.45(1+1+1) \le C_1.$$ Equivalently, you want to enforce the contrapositive $$0.45(1+1+1) > C_1 \implies \lnot \left(X_{11} \land X_{12} \land X_{13}\right),$$ equivalently, $$\lnot \left(X_{11} \land X_{12} \land X_{13}\right) \quad \text{if $0.45(1+1+1) > C_1$},$$ which you can enforce with linear constraint $$(1-X_{11}) + (1-X_{12}) + (1-X_{13}) \ge 1 \quad \text{if $0.45(1+1+1) > C_1$},$$ which simplifies to $$X_{11} + X_{12} + X_{13} \le 2 \quad \text{if $0.45(1+1+1) > C_1$}. \tag1$$

Similarly, $$\left(\lnot X_{11} \land \lnot X_{12} \land X_{13}\right) \implies 0.76(0+0+1) \le C_1$$ yields $$X_{11} + X_{12} + (1-X_{13}) \ge 1 \quad \text{if $0.76(0+0+1) > C_1$}.\tag2$$

$\endgroup$
4
  • $\begingroup$ so in essence, we would have to include constraints such as $X_{11}+X_{12}+(1−X_{13})≥1$ if $0.76(0+0+1)>C_1$, for all 2^n combinations if I understand correctly? Also, any reference to how to express the if condition in normal ILP form? $\endgroup$
    – ephemeral
    Jul 13, 2023 at 16:14
  • $\begingroup$ Yes, $2^n$ in the worst case. But you impose the constraint only if the condition holds. Constraints (1) and (2) are already in normal ILP form. $\endgroup$
    – RobPratt
    Jul 13, 2023 at 16:33
  • $\begingroup$ Or is $C_1$ supposed to be a decision variable rather than an input parameter? $\endgroup$
    – RobPratt
    Jul 13, 2023 at 19:59
  • $\begingroup$ No, $C_1$ is an input parameter, it is in normal ILP form, thanks for the clarification. $\endgroup$
    – ephemeral
    Jul 14, 2023 at 6:28

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.