# How to solve a "nearly" linear program

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?

• I guess nearness is in the eyes of the beholder, because I wouldn't call this almost linear. Jan 9 at 0:04
• What is the motivating problem for this formulation? Jan 9 at 15:01
• @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. Jan 9 at 15:21
• $(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$. Jan 9 at 15:21

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