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

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?

• Like this, but now $a_j$ is a variable?or.stackexchange.com/questions/9893/… Feb 15 at 16:57
• @RobPratt exactly, but how does that translates to the modelling? Feb 15 at 17:22
• I think this becomes an MINLP. Feb 15 at 19:34

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

• For constraint (2); isn't it problematic for solvers to have a variable lower and upperbound in a chained inequality constrained? Feb 16 at 13:27
• You can write (2) as two separate constraints if necessary. Feb 16 at 13:40

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

• I think you want $x_j$ for the RHS of the first constraint, and I think your binary variables $z_k$ need to be double-subscripted ($z_{k,j}$).
– prubin
Feb 15 at 17:10
• Right sir, I'll correct it Feb 15 at 17:11
• @Sutanu what do you mean by: "filled upfront and also where $a_j$ can take any value from set $a$ ? Feb 15 at 17:15
• @prubin, $x_j$ may not be RHS because $x_j$ could be x,x, x having its own values but x will be same as say x if a = a = 0.4 which forms the set a={0.4,0.5,0.7}. Is my understanding correct @steven01123581321? Feb 15 at 17:21

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