Convert implication to linear constraint

Question

I have the next constraint in logic (simplified):

$$\forall r \in R, t \in T: x_{rt} = 1 \implies t_a < r_p < t_b$$

I need to linearize this. What I've come up with is: \begin{align} x_{rt}t_a &< r_p \\ x_{rt}r_p &< t_b \end{align} But this looks kind of hacky. Although I think it should work, is there a better way to convert my constraint?

I need to assign reservations to tables. $R$ is the list of reservations. $T$ is the list of tables. Obviously the amount of people in the reservation needs to be less than the maximum amount of seats on a table and more than the minimum amount of seats. $x_{rt}$ is the boolean that says that reservation $r$ is assigned to table $t$. $t_a$ is the minimum seats at the table, $t_b$ is the maximum and $r_p$ is the amount of people in the reservation. $t_a$, $t_b$ and $r_p$ can be assumed constant. $x_{rt}$ is a variable (and needs to be optimized).

Other than x (which presumably you intend to be binary), what are your optimization variables? If A or B are optimization variables, then what you came up with is not a linearization. If neither A nor B are optimization variables, then $A \lt B$ is meaningless. What are the other bound constraints on the optimization variables? — Mark L. Stone, Dec 24 '17 at 19:09
I have [edit]ed your question so that it's written in MathJax. — GNUSupporter 8964民主女神地下教會, Dec 27 '17 at 02:14
@MarkL.Stone I've changed the question. So $t_a$ and $r_p$ are fixed, but the equation $x_{rt}t_a < r_p$ just needs to be valid. ($x_{rt}$ can change) — TheChosenOne, Dec 27 '17 at 12:23

score 1 · Answer 1 · answered Dec 27 '17 at 14:33

I will reformulate the problem to what I think you want, which is not what you stated in the formulation. For simplicity, I will dispense with all subscripts other than on the t's.

First of all, $r$ needs to be a decision (i.e., optimization) variable in your optimization formulation; it can not be considered constant, or your whole formulation is meaningless. Second of all, all of your inequalities should be non-strict, i.e., $\le$ rather than $\lt$.

Even when these changes are made, your proposed formulation is incorrect. If $x = 0$, your constraints become $0 \le r$ and $0 \le t_b$. There is nothing which forces $r$ to equal $0$ in this case, which is one of your requirements.

Here is a correct formulation: Add the constraints $xt_a \le r$ and $r \le xt_b $, and x is binary.

If $x = 1$, this becomes $t_a \le r \le t_b$.

If $x = 0$, this becomes $0 \le r \le 0$. In other words, $r = 0$, as required.

@TheChosenOne Does this answer your question? I think it does. — Mark L. Stone, Dec 28 '17 at 12:23

Convert implication to linear constraint

1 Answers1