Divisibility constraints in integer programming

Question

In the study of a certain pure mathematical problem (related to infinite-dimensional Lie algebras) I found myself in a situation where it would be very desirable to be able to solve an integer programming problem, where one of the constraints is a divisibility assumption. Namely, for the variables $x_i\in\mathbb{Z}_{\geqslant0}$ this constraint is of the form $$ Q(x_1,\ldots,x_n)\quad \text{divides}\quad L(x_1,\ldots,x_n),$$ where $L$ is linear and $Q$ is quadratic. (for completeness: the function to minimize is simply $\sum x_i$, and other constraints are $P(x_i)>0$ for some quadratic $P$ and $(x_1,\ldots,x_n)$ is not an integer linear combination of some given integer vectors)

I don't reckon there is an out-of-the-box solution for this, so I wonder if someone has considered any other problems of this sort, say, where there is a constraint of the form "$L_1(x_i)$ divides $L_2(x_i)$" for some linear $L_1$ and $L_2$?

Answer 1

I going to assume that the ratio $L(x)/Q(x)$ is nonnegative. If it can be negative, I think there may be a workaround, but this will complicated enough without dealing with that. I'm also going to assume that $Q(x)$ and $L(x)/Q(x)$ have a priori upper and lower bounds, say $\underline{Q} \le Q(x) \le \overline{Q}$ and $L(x)/Q(x) \in \{1,\dots,N\}$.

You can create new general variables $z_1,\dots,z_N$ and binary variables $y_1,\dots,y_n$. Add the constraint $y_1 + \dots + y_N = 1$. The $y$ variables will pick the multiple to use. Add the following constraints: $$L(x)=\sum_{i=1}^N z_i$$ $$\underline{Q}y_i \le z_i \le \overline{Q}y_i \quad \forall i$$ and $$i\cdot Q(x) - M_{i1} (1-y_i) \le z_i \le i\cdot Q(x) + M_{i2} (1- y_i) \quad \forall i,$$ where $M_{i1}$ and $M_{i2}$ are sufficiently large positive constants (but not too much larger than necessary -- making them overly large impacts solver performance negatively).

Exactly one of the $y_i$ will take value $1$. For all other indices $j$, you'll have $y_j = 0 \implies z_j = 0$. For that one index $i$, you'll have $L(x) = z_i = i\cdot Q(x)$.

Answer 2

There are two ways I would interpret the divisibility requirement:

1. Functional division, i.e., $L_1(x)/L_2(x)$ is a valid polynomial division. Since we are dividing a linear function by another linear function, that result should be a constant or another linear function.
2. Integer division, i.e., $L_1(x)/L_2(x)$ produces an integral result.

Functional division

What you want is to show that after the division operation you are left with a polynomial of at most degree $1$. A way to impose this would be through a constraint like so: $L/Q = y_1x+y_2$, where $y_i$ are real auxiliary variables (usually with fairly large bounds).

In vector format, that would be:

$$\frac{L_1(x)}{L_2(x)}=\sum_{i=1}^n\left(y_{1i}x_i+y_{2i}\right).$$

If it is impossible to get a valid linear function as a result of the division, this constraint will be infeasible.

Integer division

Assuming that we want the result of the division operation to be a pure integer, we can impose this by adding the following constraint:

$L_1(x)=yL_2(x),y\in[L,U]$

where $y$ is integer and L,U are large integer bounds for this constraint. Moving $L_2(x)$ to the rhs is usually a good idea as division by zero is not a problem numerically (we can handle the zero case in a different constraint if we so desire). This formulation also allows us to handle a case where there is a remainder, like so:

$L_1(x)=yL_2(x)+r,y,r\in[L,U]^2$

where r is our remainder.

Finally, for the original case of $L(x)/Q(x)$, the constraint would be the very similar:

$L(x)=yQ(x),y\in[L,U]$

Big bounds for $y$ are quite important here because the result of the division may span several orders of magnitude. A more solver-friendly way to handle $y$ in this case would be to reformulate it as a binary sum.