15
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Andrei Smolensky Aug 25 at 22:43
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andrei Smolensky Aug 25 at 22:46
  • $\begingroup$ Ah, I assumed you were going for functional division, I'll update the answer :) $\endgroup$ – nikaza Aug 25 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.