Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.