6
$\begingroup$

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?

$\endgroup$
3

3 Answers 3

9
$\begingroup$

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

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

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$

$\endgroup$
4
  • $\begingroup$ 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}$). $\endgroup$
    – prubin
    Feb 15, 2023 at 17:10
  • $\begingroup$ Right sir, I'll correct it $\endgroup$ Feb 15, 2023 at 17:11
  • $\begingroup$ @Sutanu what do you mean by: "filled upfront and also where $a_j$ can take any value from set $a$ ? $\endgroup$ Feb 15, 2023 at 17:15
  • $\begingroup$ @prubin, $x_j$ may not be RHS because $x_j$ could be x[1],x[2], x[3] having its own values but x[1] will be same as say x[7] if a[1] = a[7] = 0.4 which forms the set a={0.4,0.5,0.7}. Is my understanding correct @steven01123581321? $\endgroup$ Feb 15, 2023 at 17:21
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.