7
$\begingroup$

Is there a way to linearize is prime? in Operations Research?

is prime(n) being true if $n$ is a prime number or false otherwise.

If it is not possible, which I suspect, is there any other way in either:

  • Non linear programming
  • Constraint programming

An upper bound of $n$ is known in advance, being any positive natural number.

$\endgroup$
3
  • 1
    $\begingroup$ Is an upper bound of $n$ known beforehand? $\endgroup$ Feb 19, 2022 at 9:54
  • $\begingroup$ @worldsmithhelper, yes very good point, I added it to the question! $\endgroup$
    – JKHA
    Feb 19, 2022 at 9:59
  • 3
    $\begingroup$ Based on the answers, readers don't know whether you want 1) a variable being prime (or not prime) as a constraint in an optimization or feasibility problem (as I interpreted) or 2) an optimization problem whose solution determines whether a number is prime. $\endgroup$ Feb 19, 2022 at 22:31

4 Answers 4

7
$\begingroup$

TLDR: Enumerate (in advance) all primes $\le$ upper bound on $n$. Check to see whether a variable (declared as integer) equals one of the enumerated primes.

Details: Declare $x$ as integer.

Let $U$ be the upper bound on $x$.

Let $P$ be an $m$ by 1 vector consisting of all primes $\le U$.

Declare $b$ as an $m$ by 1 vector of binary variables.

$x$ is constrained to be prime by $$x = b^TP$$ $$\Sigma b = 1$$

Edit: I am answering the interpretation of the question that a variable being prime (or not prime) is a constraint in an optimization or feasibility problem. Some other answers interpret the question as formulating an optimization problem whose solution determines whether a number is prime.

$\endgroup$
3
  • $\begingroup$ Mhh this is more elegant than my solution using absolute values, it also uses less binary variables. Well done! $\endgroup$ Feb 19, 2022 at 13:43
  • $\begingroup$ If you have the list of all primes in the first place, then you really just need to check if $n$ belongs to that list. $\endgroup$
    – Kuifje
    Feb 19, 2022 at 14:52
  • $\begingroup$ @Kuifje Exactly, that is my point. I interpreted the question as wanting to constrain variables in an optimization or feasibility problem to be prime (or not prime). Not that we should use optimization as a way of determining prmeness. $\endgroup$ Feb 19, 2022 at 16:03
2
$\begingroup$

In Mixed-Integer Linear Programming, one could consider "prime" as a new type of variables in addition to "continuous", "binary", "integer", "semi-continuous"... Then the algorithm would branch as long a as a variable of type "prime" is not prime in the relaxation. For example if a "prime" variable $x$ has value $4$ in the relaxation, then the algorithm could branch on $x$ with one branch $x \le 3$ and the other $x \ge 5$.

It also seems possible to consider this type of variables in Constraint Programming.

But as far as I know, no MILP or CP solver supports this.

$\endgroup$
1
  • 1
    $\begingroup$ I agree that this is not supported directly in any solver that I know of. However, some solvers allow the user control over the branching process via callbacks, so it could hypothetically be implemented by the user. $\endgroup$
    – prubin
    Feb 19, 2022 at 16:44
2
$\begingroup$

Primality is difficult to check as it requires a statement like "there don't exist two natural numbers $a,b>1$ such that $n=a\cdot b$" which for flexible a $n$ require quantifiers to express. Quantified Mixed Integer (Linear) programming exists as a concept but I am not really aware of any solvers that can solve such problems.

This means we need to somehow "unroll" all possibilities such an quantifier would cover. Let $N$ be the upper bound of $n$ a naive one would be $\prod_{x \in \mathbb{P}} (n-x) = 0$ or some other polynomial. Other primality tests such as the Wilson test $(n-1)!\ \equiv\; -1 \pmod n$ can also be expressed but would result in even higher order polynomials.

Another alternative not using products of variables is to use the absolute value $\forall_{x\in\mathbb{P}\leq N} |n-x| \leq N b_p$ and $\sum_{x\in \mathbb{P}} b_p = 1$ and $b_p$ is a boolean. One could cut the number of equations almost in half by checking divisibility by 2.

There are more compact is prime checks and one could systematically search those for some fixed $N$. This would likely be possible using a two level Mixed Integer Quadratic problem where you try to find an constraint matrix $A \in \mathbb{R}^{n+2\times n+2}$ and a constraint vector $b \in \mathbb{R}^{n}$ that satisfies $$\forall m\in\mathbb{N}\leq N: A x \leq \begin{bmatrix} m \\ \text{isprime}(m) \\ b_1 \vdots \\ b_{n} \end{bmatrix}$$ where the parent tries to find a such a matrix $A$ and an assignment $x \in \mathbb{R}^a \times \mathbb{B}^{N-a}$ that satisfies this and the $N$ sub problems (each has it's own $m$) try to find counter examples $x$ such that for the $A,b$ from the parent problem $$A x \leq \begin{bmatrix} m \\ 1-\text{isprime}(m) \\ b_1 \vdots \\ b_{n} \end{bmatrix}$$ This counter example can then be used to add a new constraint to the parent problem. If the parent problem becomes unfeasible a bigger $n$ for the dimensions needs to be chosen. Note that only the parent problem is quadratic. If all subproblems are infeasible you found a constraint which encodes is prime. Depending how you chose $n$ and whether the parent problem has an appropriate objective it might also be the smallest $n$, a sparse $A$ or have other properties you want and can express in quadratic programming.

Note that Mixed Integer solvers are generally not great in finding feasible solutions a more different approach would be to pick a binary encoding of $n$ to be tested and do a similar find counter example make more constraints loop with a Pseudo boolean or a SAT solver. This will result in binary constraints which can then also be used in a MILP problem. Quantified boolean solvers also exist and there might be a way to "coax" them into finding a solution without bouncing back and forth. Another alternative on that front are Binary Decision Diagrams which are also use to reduce logic in computer chips.

Getting good results using either method with some analysis of the result would probably be worth publishing a paper about. There might be some other way to derive such a look up table however i am not aware of any.

$\endgroup$
2
$\begingroup$

Since primes only have $2$ divisors, $1$ and the number itself, you could use the following program to determine if an integer $n \in \mathbb{N}$ is prime or not : $$ \max \; x $$ \begin{align} \mbox{subject to }\quad n &= x \cdot y \tag{1} \\ x &\in \mathbb{N} \cap [0,n-1] \tag{2}\\ y &\in \mathbb{N} \cap [0,n] \tag{3} \end{align}

With constraints $(1)-(3)$, you try to decompose $n$ as a product of two integers $x$ and $y$, where $x$ cannot equal $n$. The objective function maximizes $x$. So if the largest $x$ you can find equals $1$, then $n$ is prime. Otherwise it is not.

For example, if $n:=10$, the following solution is optimal: $x=5$, $y=2$. So $n$ is not prime. If $n=11$, the following solution is optimal: $x=1$, $y=11$. So $n$ is prime.

Of course this is not linear, but you can easily linearize the product, and you will have a problem with binary and integer variables that determine if a number $n$ is prime or not.

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