How do we formulate a problem where the decision variable has an index that is also a decision variable?

Question

I want to maximize the sum of a nonlinear function $f(.)$ w.r.t. $x$ that is convex in $x$: $$\max \sum_{i=1}^N f(x_i), $$where $x_i$ is a continuous variable and $0 \le x_i < 1$ for $i = 1, 2, \dots , N$.

But in this problem, $x_i$ is restricted to be an element of the set $a = \lbrace a_1, a_2, a_3 \rbrace$, where $a_j$ is also a continuous variable and $0 \le a_j < 1$ for $j = 1, 2, 3$.

The problem is thus to maximize the objective function in w.r.t. of $x_i$ for $i= 1, 2, \dots , N$, where $x_i$ has to belong to the set $a$ and $a_j$ also is unknown and thus a decision variable.

There is one more constraint:

$$\beta = \frac{\sum_{i=1}^N D_i x_i }{\sum_{i=1}^N D_i},$$

where $D_i$ is a known constant for each $i$ and $\beta$ is again a constant with $0 \le \beta < 1$. $D_i$ and $\beta$ are thus outside of the model.

Is there a way to formulate this as an NLP problem?

Answer 1

Let binary decision variable $y_{ij}$ indicate whether $x_i = a_j$, and impose linear constraints \begin{align} \sum_j y_{ij} &= 1 &&\text{for all $i$} \tag1\label1 \\ -(1 - y_{ij}) \le x_i - a_j &\le 1 - y_{ij} &&\text{for all $i$ and $j$} \tag2\label2 \end{align} Constraint \eqref{1} selects exactly one $j$ for each $i$, and (big-M) constraint \eqref{2} enforces the logical implication $y_{ij} = 1 \implies x_i = a_j$.

Answer 2

Assuming set $a=\{a_1,a_2,a_3\}$ is filled with variable $a_k$ and also where $a_j$ can take any value from set $a$, lets try:

$ \sum_{j=1}^3 a_j\cdot z_{j,i} = a_i \ \ \forall i$
$ \sum_j z_{j,i} = 1 \ \ \forall i$

The above 2 will turn $ z_j = 1$ when $a_j = a_i$ for an index $i$

Then $\sum_j z_{j,i}\cdot x_{j} \ \ \forall i$ which can be linearized by
$ \epsilon z_{j,i} \le x_{j} \le Mz_{j,i} \ \ \forall j \ \ \forall i$ where M and $\epsilon$ can be the upper & lower bound for $x$

Answer 3

If $x_i \ge x_{i+1}$ (which was the case in my situation), I found the following that works as well. Create two continuous variables $x_i$ and $a_i$, $0 \le x_i, a_i < 1$ for $i= 1, 2, \dots, N$ and one binary variable $\delta_i$. Then impose the following constraints:

$$x_i = x_{i-1} - (\delta_ia_i)\tag{1},$$ $$\delta_1 = 0\tag{2},$$ $$\sum_i \delta_i = 2\tag{3},$$ $$\beta = \frac{\sum_i d_ix_i}{\sum_i d_i}\tag{4}.$$