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.


Your Answer

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

Browse other questions tagged or ask your own question.