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
  • $\begingroup$ Like this, but now $a_j$ is a variable?or.stackexchange.com/questions/9893/… $\endgroup$
    – RobPratt
    Commented Feb 15, 2023 at 16:57
  • $\begingroup$ @RobPratt exactly, but how does that translates to the modelling? $\endgroup$ Commented Feb 15, 2023 at 17:22
  • $\begingroup$ I think this becomes an MINLP. $\endgroup$ Commented Feb 15, 2023 at 19:34

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$ Commented Feb 16, 2023 at 13:27
  • 1
    $\begingroup$ You can write (2) as two separate constraints if necessary. $\endgroup$
    – RobPratt
    Commented 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
    Commented Feb 15, 2023 at 17:10
  • $\begingroup$ Right sir, I'll correct it $\endgroup$ Commented 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$ Commented 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$ Commented 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.