0
$\begingroup$

I am facing some difficulty understanding a LP problem. The objective function and the constraints: $$ \begin{split} max. & \sum{A_{t}} \times p_{t}\\st. L_{0} & =0\\ L_{t} & =L_{t-1}+A_{t-1}; t > 0\\ -1 & \leq A_{t} \leq 1\\ 0 & \leq L_{t} \leq 3 \\ where: \\ t & = 1,...,120 \end{split} $$

The problem is to maximize the profit of a battery. The current level of the battery is $L_t$ and the action in each time period is $A_t$. The initial level of the battery is $L_t$. So, the battery can be charged $A_t=-1$ three periods in a row until $L_t$ = 3, then the only option is to discharge $A_t=1$.

$p_t$ is a time series of forecasted value so if we discharge the battery at time $t$, we earn $p_t \times A_t$, if we charge at $t$ we spend $p_t \times -A_t$ $A_t$ is a action taken at each time period $t$, $L_t$ is the maximum level

I want to formulate this as the standard problem, to be able to implement it into Python. Based on this I guess that the last two constraint would have to be transformed into the following four constraints.

  A_t + s_1 = 1
- A_t + s_2 = 1
  L_t + s_3 = 3
- L_t + s_4 = 0

But I am not sure of this. Further, I don't know how to tacle the initial constraint L_0=0 or the second constraint including the t-1 index. Any help on this would be appreciated.

$\endgroup$
7
  • $\begingroup$ Welcome to MSE. Questions posted here should be self-contained. $\endgroup$ Feb 5, 2023 at 9:30
  • $\begingroup$ Please don't post images. Instead, you can directly use LaTex here, see here for more details. In addition, you should explain your notation a bit. Is each $A_t$ and $L_t$ just a scalar variable? For instance, most people (including me) use upper letters only for matrices, not for scalars. Also, what is your objective function and what is $t0$? $\endgroup$
    – joni
    Feb 5, 2023 at 9:34
  • $\begingroup$ "I don't know how to tacle the initial constraint L_0=0 or the second constraint including the t-1 index" I would say that $t$ is defined for natural numbers, without 0. $\endgroup$ Feb 5, 2023 at 9:35
  • $\begingroup$ @joni Thank you for the tip. I have updated the question accordingly. $\endgroup$ Feb 5, 2023 at 10:11
  • $\begingroup$ @JoséCarlosSantos Thanks. I have fixed that now. $\endgroup$ Feb 5, 2023 at 10:12

1 Answer 1

0
$\begingroup$

A LP in standard form looks like this:

$$ \min c^\top x \quad \text{s.t.} \quad Hx = d, \quad l \leq x \leq u. $$

You only need to to two things:

  1. Pack all your variables into one vector, i.e. you can set $x = (L_0, A_0, L_1, A_1, \ldots, L_{120}, A_{120}) \in \mathbb{R}^{242}$.

  2. Set the objective vector $c$. With the choice of $x$ you have

$$ c = (0, p_0, 0, p_1, 0, p_2, 0, p_3, \ldots, 0, p_{120})^\top $$

  1. Write your constraints as matrix-vector product.

This isn't hard, as you have

$$ - L_{t-1} - A_{t-1} + L_t = 0 $$

for $t \geq 1$ and $L_0 = 0$. I think it helps to explicitly write these constraints:

$$ \begin{align*} - L_0 - A_0 + L_1 &= 0, \\ - L_1 - A_1 + L_2 &= 0, \\ - L_2 - A_2 + L_3 &= 0, \\ &\vdots \\ - L_{119} - A_{119} + L_{120} &= 0 \end{align*} $$

Therefore, we have

$$ \underbrace{% \begin{pmatrix} -1 & -1 & 1 & 0 & 0 & 0 & \ldots & 0 \\ 0 & -1 & -1 & 1 & 0 & 0 & \ldots & 0 \\ 0 & 0 & -1 & -1 & 1 & 0 & \ldots & 0 \\ & & & \vdots & & & \\ 0 & 0 & 0 & 0 & 0 & \ldots & -1 & -1 & 1 \end{pmatrix} }_{=H} \cdot \underbrace{% \begin{pmatrix} L_0 \\ A_0 \\ L_1 \\ A_1 \\ \vdots \\ L_{120} \\ A_{120} \end{pmatrix} }_{=x} = \underbrace{% \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ 0 \end{pmatrix} }_{=d}. $$

Here, $H \in \mathbb{R}^{120 \times 242}$ is a matrix with 120 rows and 242 columns. Your variable bounds are then given by

$$ \begin{align*} l &= (0, -1, 0, -1, 0, -1, \ldots, 0, -1)^\top, \\ u &= (0, 1, 3, 1, 3, 1, 3, 1 \ldots, 3, 1)^\top. \end{align*} $$

Note that the upper and lower bound for $L_0$ is 0 due to the equation $L_0=0$. Alternatively, you could incorporate this equation into the matrix $H$ instead. It would be just another row with a 1 in the first column and zeros for the other ones.

$\endgroup$
9
  • $\begingroup$ Thank you a lot for this. In the vector x. What are the values of $L_0$, $A_0$ etc. supposed to be when I create the vector in Python to later pass it to the solver? $\endgroup$ Feb 5, 2023 at 11:47
  • $\begingroup$ I suppose that I might not need to do this. But what about the requirement that the c vector should have the same size as the number of columns in H. Now c=240 and H=242? $\endgroup$ Feb 5, 2023 at 12:56
  • $\begingroup$ Sorry, I don't understand your first question. You just solve the LP. Then, the solver gives you the solution $x$ and you can split the solution back into $L_0, A_0$ etc using the the above definition afterwards. Regarding your second comment: The vector c already has 242 entries. Otherwise, the scalar product $c^\top x$ wouldn't be defined. $\endgroup$
    – joni
    Feb 5, 2023 at 13:00
  • $\begingroup$ Hm, okay. When I read it I understand it as the vector $c$ should contain $0, p_0, 0, p_1$ etc. But this only gives 240 values since there are 120 $p_i$s $\endgroup$ Feb 5, 2023 at 13:03
  • $\begingroup$ Well. I feel a bit stupid. If there are only 120 $p_i$ I guess the list should only go to $p_{119}$ if it starts at $p_0$ and therefore $H$ should have only 240 columns too. I struggle with implementing $H$ though since the -1, -1, 1 sequence stop at column 121, while in your example the last three columns are also non-zero. $\endgroup$ Feb 5, 2023 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .