# How to express coprimality as a constraint in an optimization problem over integers?

I am currently working with an optimization problem that is defined over a a set of $D$-dimensional integer vectors where each component is bounded by $M$.

Let us refer to this optimization problem as $P$ and define it as

\begin{align} \begin{split} \min_x & f(x) & \\ \text{st.} &|x_d| \leq M & \text{for } d = 1,\ldots,D \\ &x\in \mathbb{Z}^D & & \end{split} \\ \end{align}

My issue is that $P$ is that it does not have a unique solution due to the way that $f$ is defined. In particular, given that $x^*$ is the minimizing value of $P$, any scalar multiple of this solution $x' = \lambda x^*$ will also be optimal - provided that all of the elements of $x'$ are bounded within $M$.

To illustrate this, consider an example where $D=3$, $M$ = 100, and $x^* = (1,1,1)$ then there are a total of 200 total solutions to $P$ with the form $x'= \lambda(1,1,1)$ where $\lambda \in \{-100,-1,1\ldots,100\}$.

In practice, this slows down my optimization solver. Thus, I would like to obtain the solution that is the 'smallest' possible $x^*$ (i.e. $x^* = (1,1,1)$ in the example above).

I can think of two ways to achieve this:

1) Add a tiny penalty $L_1$ or $L_2$ norms in the objective of $P$.

2) Add constraints to restrict the value of $x$ to a coprime set. This requires that at least two of the components of $x*$ are coprime; that is,$\exists i \neq j \in \{1,\ldots,D\}$ such that $\gcd(x_i,x_j)=1$

I am wondering if it is possible to achieve 2) by formulating a set of smart constraints. That is, can we formulate constraints that restrict $x$ to a coprime set. Ideally, I would like to do this using as few constraints as possible.

-