4
$\begingroup$

Given a positive integer $n$, a constant $k=2/3$, and $7$ variables $x_1, x_2, x_3, x_{12}, x_{13}, x_{23}, x_{123}$ (non-negative reals or integers) I would like to find:

$$\min \binom{x_1}2$$

subject to:

$$\binom{x_1}2 \ge \binom{x_2}2 \ge \binom{x_3}2 \tag{1}$$

$$\binom{n}2 \ge \binom{x_1}2+\binom{x_2}2+\binom{x_3}2-\binom{x_{12}}2-\binom{x_{23}}2-\binom{x_{13}}2 \ge k\binom{n-1}2 \tag{2}$$

$$\binom{x_1}2 \ge \binom{x_{12}}2+\binom{x_{13}}2 \ge k\binom{x_1-1}2 \tag{3}$$

$$\binom{x_2}2 \ge \binom{x_{12}}2+\binom{x_{23}}2 \ge k\binom{x_2-1}2 \tag{4}$$

$$\binom{x_3}2 \ge \binom{x_{13}}2+\binom{x_{23}}2 \ge k\binom{x_3-1}2 \tag{5}$$

$$x_1+x_2+x_3-x_{12}-x_{13}-x_{23}+x_{123} = n \tag{6}$$

This is a starting example, because from this I would like to solve the natural extension of the problem with $2^q-1$ variables, $q \gt 3$.

If we remove $(6)$ from the problem and we could replace $\binom{x_1-1}2, \binom{x_2-1}2, \binom{x_3-1}2$ with $\binom{x_1}2, \binom{x_2}2, \binom{x_3}2$ on the RHS of $(3), (4), (5)$ and then set $y_1=\binom{x_1}2, y_2=\binom{x_2}2, y_3=\binom{x_3}2, y_{12}=\binom{x_{12}}2, y_{13}=\binom{x_{13}}2, y_{23}=\binom{x_{23}}2, y_{123}=\binom{x_{123}}2$ we would get a linear program. Unfortunately, we can't do that, that's why we have a "nearly" linear program.

One idea that came to mind is that e.g.:

$$k\binom{x_1-1}2 = k\frac{x_1-2}{x_1}\binom{x_1}2 \ge \frac{2}{3}k\binom{x_1}2$$

when $x_1 \ge 6$, therefore we could replace the RHS for $x_1 \ge 6$ and enumerate all the possible values of $x_1$ for $x_1 \lt 6$, but we would have another $6$ linear programs to solve. If we fix $\binom{x_2-1}2$ and $\binom{x_3-1}2$ in the same way, the additional programs to solve would be $6^3 = 216$. That will be much bigger for $q \gt 3$.

Another idea is keep $(6)$, then use the identity:

$$\binom{x_1-1}2=\binom{x_1}2-x_1+1$$

however, with this one we would need a way to enforce the relation between $y_1 = \binom{x_1}2$ and $x_1$, i.e. linearize:

$$y_1 = \frac{x_1(x_1-1)}2$$

Any idea or suggestion?

$\endgroup$
4
  • 2
    $\begingroup$ I guess nearness is in the eyes of the beholder, because I wouldn't call this almost linear. $\endgroup$ Jan 9, 2023 at 0:04
  • 1
    $\begingroup$ What is the motivating problem for this formulation? $\endgroup$
    – RobPratt
    Jan 9, 2023 at 15:01
  • $\begingroup$ @RobPratt, yet another formulation related to finite union-closed families of sets. When I have some time, I will add an explanation, however it's a little long. $n$ is the number of sets of the family, $x_1$ the number of sets containing element $1$, $x_{12}$ the number of sets containing element $1$ and $2$, and so on. We are considering here the case where the universe is with max $3$ elements. $\endgroup$ Jan 9, 2023 at 15:21
  • $\begingroup$ $(2)$ enforces that at least $2/3$ of couples of (non-empty) sets have non empty intersection (see here), $(3),(4),(5)$ is the same as $(2)$ but for the subfamilies of all sets containing $1,2,3$ respectively. And finally we are searching the minimum of the maximum frequency of elements. The hope is having $\min x_1 \ge n/2$. $\endgroup$ Jan 9, 2023 at 15:21

1 Answer 1

5
$\begingroup$

Here's a linearization that you might find useful. Suppose integer variable $x\in\{0,\dots,M\}$. Then you can enforce $y = \binom{x}{2}$ by introducing binary variables $z_j$ and linear constraints: \begin{align} \sum_{j=0}^M z_j &= 1 \\ \sum_{j=0}^M j z_j &= x \\ \sum_{j=0}^M \binom{j}{2} z_j &= y \\ \end{align} More generally, you can enforce any functional relationship $y=f(x)$ by replacing $\binom{j}{2}$ with $f(j)$.

$\endgroup$

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.