Notes

Intervals

Although an interval is usually represented using two variables, such as \(I = (a, b]\), in reality, four variables are required to define an interval, namely representing the left endpoint, the right endpoint, the left openness/closedness, and the right openness/closedness.

That is, an interval is represented by a four tuple

\[(a, b, l, r) \in \mathbb{R} \times \mathbb{R} \times \mathbb{Z_{2}} \times \mathbb{Z_{2}}\]

where \(a \leq b\).

For our purposes, we shall represent \(I_{\sigma}\) and \(J_{\xi}\) as

\[\begin{split}I_{\sigma} & := (\delta_{\sigma, 0}, \delta_{\sigma, 1}, \varphi_{\sigma, 0}, \varphi_{\sigma, 1}) \\ J_{\xi} & := (\zeta_{\xi, 0}, \zeta_{\xi, 1}, \psi_{\xi, 0}, \psi_{\xi, 1}).\end{split}\]

Here, the third and the fourth coordinates represent whether the endpoints are included or not. For example,

\[I = (a, b, 0, 1)\]

will represent a half open interval \(I = (a, b]\) in the usual notation.

For convenience, we will be mixing different notations going forward, but there should be no confusion as to which type of notation is being used as the number of arguments are different.

Indicator function

Given set \(A \subseteq \mathbb{R}\), we have

\[\begin{split}\chi_{A}(x) := \begin{cases} 1 & \text{if } x \in A \\ 0 & \text{otherwise} \end{cases}.\end{split}\]

Note that the relation between \(x\) and \(e\) is not linear. So we somehow need to convert this into a set of linear relations. For now, let’s consider the cases \(A = \mathbb{R}^{+}\) and \(A = I = [a, b]\).

If \(A = \mathbb{R}^{+}\), then we have

\[\begin{split}e = \begin{cases} 1 & \text{if } x > 0 \\ 0 & \text{otherwise} \end{cases}.\end{split}\]

Assuming that \(e\) is binary, this assignment can be achieved by giving the constraints

\[\begin{split}x & \leq N e \\ e & \leq N x.\end{split}\]

This gives

\[e = 0 \implies x = 0 \mathrm{\quad and \quad} x = 0 \implies e = 0.\]

Also note that if \(N\) is sufficiently large, there is effectively no upper bound for \(x\) when \(e = 1\).

Note that when \(e = 1\), the latter constraint becomes

\[1 \leq N x \Longleftrightarrow \frac{1}{N} \leq x.\]

Although this is not technically the same as \(0 < x\), if \(N\) is sufficiently large, it is practically the same.

Note

Suppose \(0 < x < \frac{1}{N}\). Then we have

\[0 < x < N e \implies e = 1\]

as \(e = 0\) gets ruled out. This in turn implies

\[e = 1 \leq N x \implies \frac{1}{N} \leq x\]

which is contradictory to our assumption that \(x < \frac{1}{N}\). Hence the range \((0, \frac{1}{N})\) is effectively ruled out for the possible values of \(x\).

However, it may be sometimes desirable to use a separate variable \(\varepsilon\) instead of \(\frac{1}{N}\). Then we can use the following set of constraints instead

\[\begin{split}x & \leq N e \\ \varepsilon & \leq x + N (1 - e).\end{split}\]

Now, if \(A = I = [a, b]\), then this translates to

\[\begin{split}e = \begin{cases} 1 & \text{if } a \leq x \text{ and } x \leq b \\ 0 & \text{otherwise} \end{cases}.\end{split}\]

Now consider the constraints

\[\begin{split}x & \leq b + N (1 - e) \\ a & \leq x + N (1 - e)\end{split}\]

which implies

\[e = 1 \implies a \leq x \text{ and } x \leq b.\]

As for

\[e = 0 \implies x < a \text{ or } x > b,\]

we use the constraints

\[\begin{split}x & \leq a - \varepsilon + N e + N e^{*} \\ b + \varepsilon & \leq x + N e + N (1 - e^{*})\end{split}\]

where \(e^{*}\) is another independent binary variable.

Note

Let \(e = 0\). Then the constraints above become

\[\begin{split}x & \leq a - \varepsilon + N e^{*} \\ b + \varepsilon & \leq x + N (1 - e^{*}).\end{split}\]

Depending on the value of \(e^{*}\), only one of the two is effectively enforced.

Hence the full list of constraints becomes

\[\begin{split}a & \leq x + N (1 - e) \\ x & \leq b + N (1 - e) \\ x & \leq a - \varepsilon + N e + N e^{*} \\ b + \varepsilon & \leq x + N e + N (1 - e^{*}).\end{split}\]

As for bounded open intervals, or even half-open intervals, the list of constraints can be derived in a similar manner. For example, if we had \(A = I = (a, b)\), we would have obtained instead

\[\begin{split}a + \varepsilon & \leq x + N (1 - e) \\ x & \leq b - \varepsilon + N (1 - e) \\ x & \leq a + N e + N e^{*} \\ b & \leq x + N e + N (1 - e^{*}).\end{split}\]

Combining the two, let \(A = I = (a, b, c, d)\). Then the full list of constraints covering all cases becomes

\[\begin{split}a & \leq x + N (1 - e) + N (1 - c) \\ x & \leq b + N (1 - e) + N (1 - d) \\ x & \leq a - \varepsilon + N e + N e^{*} + N (1 - c) \\ b + \varepsilon & \leq x + N e + N (1 - e^{*}) + N (1 - d) \\ a + \varepsilon & \leq x + N (1 - e) + N c \\ x & \leq b - \varepsilon + N (1 - e) + N d \\ x & \leq a + N e + N e^{*} + N c \\ b & \leq x + N e + N (1 - e^{*}) + N d.\end{split}\]

However, by pairing open and closed cases, such as

\[\begin{split}a & \leq x + N (1 - e) + N (1 - c) \\ a + \varepsilon & \leq x + N (1 - e) + N c\end{split}\]

we see that this can be reduced to a single constraint

\[a + \varepsilon (1 - c) \leq x + N (1 - e).\]

Performing similar reductions on all other pairs, we get

\[\begin{split}a + \varepsilon (1 - c) & \leq x + N (1 - e) \\ x & \leq b - \varepsilon (1 - d) + N (1 - e) \\ x & \leq a - \varepsilon c + N e + N e^{*} \\ b + \varepsilon d & \leq x + N e + N (1 - e^{*}).\end{split}\]

Redacted Header

Content redacted.

Redacted Header

Content redacted.

Variable separation

Continuing on with a previous subsection, we want to define \(x_{1}, \dots, x_{n}\) where

\[x = \sum_{k} x_{k}\]

with

\[\forall k, e_{k} = 1 \implies x_{k} = x.\]

Now, together with the constraints that were constructed in the previous subsection

\[\begin{split}\begin{align} & & x & \leq N \sum_{k} e_{k} \\ & & \sum_{k} e_{k} & \leq 1 \\ & \forall k, & \delta_{k, 0} + \varepsilon (1 - \varphi_{k, 0}) & \leq x + N (1 - e_{k}) \\ & \forall k, & x & \leq \delta_{k, 1} - \varepsilon (1 - \varphi_{k, 1}) + N (1 - e_{k}) \end{align}\end{split}\]

consider the following additional constraints

\[\begin{split}\begin{align} & & x & = \sum_{k} x_{k} \\ & \forall k, & x_{k} & \leq N e_{k}. \end{align}\end{split}\]

The first one is obvious. As at most one of \(e_{k}\)’s can be nonzero, the second one enforces that also at most one of \(x_{k}\)’s is nonzero.

Note that we have

\[\begin{split}\begin{align} e_{k} = 1 & \implies e_{l} = 0 & & \textrm{for } l \neq k \\ & \implies x_{l} = 0 & & \textrm{for } l \neq k \\ & \implies x_{k} = x & & \end{align}\end{split}\]

since \(\sum_{l} x_{l} = x\).

Nearest Integer Function

Let \(x \in \mathbb{R}\) and \([\cdot]\) be a nearest integer function. We want to express

\[n := [x],\]

where \(n \in \mathbb{N},\) in terms of constraints. To do this, we introduce an intermediary variable \(m \in \mathbb{N}\) and require

\[\begin{split}m & \leq x \\ x & \leq m + 1 - \varepsilon.\end{split}\]

Then we effectively have

\[m = \lfloor x \rfloor.\]

Now \(n\) can be redefined as

\[\begin{split}n := \begin{cases} m + 1 & \text{if} & 0.5 \leq x - m \\ m & \text{otherwise}. & \end{cases}\end{split}\]

For this, we introduce a yet another conditional binary variable \(e\) where

\[\begin{split}0.5 & \leq x - m + N(1 - e) \\ x - m & \leq 0.5 - \varepsilon + N e.\end{split}\]

We can now simply define \(n\) as

\[n := m + e.\]

In simple terms, we round up \(x\) if \(e = 1\) and round down if \(e = 0\). Putting everything together, we have

\[\begin{split}n & = m + e \\ m & \leq x \\ x & \leq m + 1 - \varepsilon \\ 0.5 & \leq x - m + N(1 - e) \\ x - m & \leq 0.5 - \varepsilon + N e.\end{split}\]

Simpler Nearest Integer Function

Note that, from

\[n = [x] \Longleftrightarrow n = \lfloor x + 0.5 \rfloor\]

we can use

\[\begin{split}n & \leq x + 0.5 \\ x + 0.5 & \leq n + 1 - \varepsilon\end{split}\]

as our constraints to eliminate the necessity of an additional variable.