# Divisibility constraints in integer programming

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$$?

• The division operation seems like it can be represented as a Mixed Integer Non Linear Programming problem. – batwing Aug 24 at 5:07

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

• I'm glad that the problem at hand can be translated into something which is solvable by the known technology, at least theoretically. Unfortunately, there is no small bound for $L(x)/Q(x)$, so it will quickly go to hundreds and thousands of variables and constraints. Anyway, the idea with the sum of binary variables helps a lot, as well as everything else in your solution, thanks! – Andrei Smolensky Aug 25 at 22:43

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.

• Frankly, I don`t see why $L/Q$ should be a polynomial (in what variables, to begin with?). The constraint I am trying to set is the divisiblity of integers that are the values of certain polynomials. – Andrei Smolensky Aug 25 at 22:46
• Ah, I assumed you were going for functional division, I'll update the answer :) – nikaza Aug 25 at 23:35