1
$\begingroup$

I am trying to formulate an optimization problem where the decision variable is an index of the input array as part of the formulation.

For example, I have the following term (this is simplified):

$A[ max_t ( \alpha[t] * t ) ] $

  • A is an input 1D-array
  • $\alpha[t]$ is the integer decision variable

So my questions are:

  1. Is it correct to formulate an optimization problem where the decision variable is used to index a value in the input
  2. If the answer is yes, what solver allows such format?
  3. I tried Gekko solver, but I could not implement it, for example, a tiny code for Gekko:

x = [0, 1, 2, 3, -100, -500]

then if I try:

x[alpha[i]*(i)]

It would fails to run as the index of x must be an integer rather than a Gekko operator.

Edit:

For the original problem, I have decision variable $\alpha[t]$ and it gets assigned 0 and 1 as its an integer variable.

Then, $\forall t$ , I want to find $t'$, where $t'$ is the last time where $\alpha[t]$ is 1 such that $t'<t$, then I want to use $x[t']$ in a constraint (e.g. $x[t] - x[t'] > 0$)

$\endgroup$
11
  • $\begingroup$ Unless you know anything about $\alpha_t$ and $x_i$ as functions, this is basically just a question of finding the largest element in an array. $\endgroup$ Jul 18, 2023 at 21:20
  • $\begingroup$ I am just giving an idea of the way I am trying to do something not what I am doing to reduce the complexity. Of course I do not just want the largest element in an array, the original problem uses the decision variable as an index of the input array. I am not sure if that's correct as a mathmatical formulation, also not sure how to achieve that in code $\endgroup$
    – Kasparov92
    Jul 18, 2023 at 22:13
  • $\begingroup$ I added a hint on what I am actually trying to achieve in the original problem at the end of the question $\endgroup$
    – Kasparov92
    Jul 18, 2023 at 22:17
  • $\begingroup$ What does $a_t * t$ mean? It seems to me that you're asking how you can build a problem where there is an array x = [2, 34, 17, 5] and then want to use x[i] in various places where i is a decision variable that selects a value from x. Is that so? $\endgroup$
    – Richard
    Jul 19, 2023 at 15:38
  • 1
    $\begingroup$ @Kasparov92 I think we are all sufficient confused by what the problem is by now. You might want to rewrite the entire question, using a consistent notation (for example, what is the difference between $\alpha_t$ and $x[t]$ and why does one use a subscript and the other one index notation?). $\endgroup$ Jul 20, 2023 at 18:31

2 Answers 2

2
$\begingroup$

Can you do the following?

xc = x0*xb1 + x1*xb1 + ...
SOS1(xb)

That is, associate each value of your x array with a binary variable and put these binary variables into a Type 1 SOS collection (special ordered set). That will ensure that only one of the binary variables is true at a time, effectively selecting one element from the array.

$\endgroup$
5
  • $\begingroup$ That is similar to what I am trying to do. However, I am not trying to select item $x_i$ from array $x$, what I am trying to do is as follow: I have another binary variable $\alpha_i$, and for each $i$, I want to get the corresponding item in $x_j$, such that 1) $j<i$ and 2) $\forall k \in \{ j+1, j+2, ..., i \} $ then $\alpha_k = 0$ and lastly, 3) $\alpha_j = 1$ $\endgroup$
    – Kasparov92
    Jul 23, 2023 at 17:35
  • $\begingroup$ I am thinking of using this idea and adding some constraints to link the 2 variables together to force that to happen, I will work on it tomorrow. $\endgroup$
    – Kasparov92
    Jul 23, 2023 at 17:39
  • $\begingroup$ @Kasparov92: I'm afraid I was unable to follow your description of what you're trying to do. For instance, "item in $x_j$" confuses me. iiuc $x$ is an array and $x_j$ is an item of that array. You can't get an "item in $x_j$": it's just an element. $\endgroup$
    – Richard
    Jul 23, 2023 at 18:25
  • $\begingroup$ the word "in" is a mistake, I just want to find the item $x_j$ $\endgroup$
    – Kasparov92
    Jul 23, 2023 at 21:22
  • $\begingroup$ so in other words, I am trying to find for each $\alpha_i$ is the corresponding item $x_j$ such that $\alpha_j$ is the last $\alpha_j$ that is 1 and that precedes $\alpha_i$ $\endgroup$
    – Kasparov92
    Jul 23, 2023 at 21:25
2
$\begingroup$

I found a simple answer based on the Type1 SOS idea suggested by Richard.

The problem is that I have an integer decision variable $\alpha[t]$, for example, at some solution, the values of $\alpha[t]$:

$\alpha[t] = [0, 1, 0, 0, 0, 1, 0]$

and I do have a position input array, for example:

Positions = [10, 55, 2, -100, 3, -4.5, 9]

so, for a given index t, I need to find the last Position for which the $\alpha[t]=1$

For instance, using a 0-based indexing system, if the index is 3 then the desired position element is 55, and if the index is 6, then the position would be -4.5

Solution 1:

  1. Do an index array indices = [1, 2, 3, 4, 5, 6, 7]
  2. Multiply this array by the alpha, m = [indixes[i]*alpha[i] for i in range(7)]
  3. Build your own SOS variable to select the maximum item of m. This constitutes of (a) introducing new variables and (b) adding an objective function to maximize these SOS variables
  4. Use this SOS variable to select the corresponding position

Here is the full code in GEKKO as an example:

from gekko import GEKKO
import numpy as np


m = GEKKO()
alpha = np.array([0, 1, 0, 0, 0, 1, 0])
indices = np.array([1, 2, 3, 4, 5, 6, 7])
Positions = np.array([10, 55, 2, -100, 3, -4.5, 9])

T = 3 # Change to 6 to get the position -4.5

intb = [m.Var(0, lb=0, ub=1, integer=True) for i in range(T)]
y = m.Var()
# add equation for selecting only one option
m.Equation(sum(intb) == 1)
x = m.Intermediate(sum([alpha[i] * indices[i] * intb[i] for i in range(T)]))
m.Equation(y == x)
m.Obj(-y) # maximize the intb to select y

selected_position = m.Intermediate(sum([Positions[i] * intb[i] for i in range(T)]))

m.solve()
print(selected_position.value[0])
print([intb[i].value[0] for i in range(T)])
print(y.value[0])

In this example, the variable T controls the specific area of T to cover. The original problem is more complicated where I need to do this for each T, so I will have a list of Ts, where for each $t \in \{ 0, 1, ..., T \}$, I will need these SOS variables from 0 up to t.

Note: This solution would only work if the newly added objective functions would not be contradicting the main objective function used.

Solution 2:

The previous solution implies changing the objective function, which was not good enough for my needs, even with weighting each objective function, I still ended up getting sub-optimal solutions.

Therefore, an alternative is to design a set of constraints that represents: "the last index of $\alpha$ that has a value 1 before an index t.

There are three constraints as follow:

  1. Build an SOS variable that will select the maximum variable $\alpha[i]$. I will call this SOS variable as $\beta[i]$
  2. Constraint this SOS variable to be 1 only if $\alpha[i]$ is 1, otherwise it has to be 0. Note that by definition $\beta$ sums to 1.
  3. All $\alpha[i]$ between the index of $\beta$ that has a value of 1 and the index t must sum to 0.

This approach consumes more decision variables but prevents modifying the objective function.

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