# Help understanding LP transformation to standard form

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.

• Welcome to MSE. Questions posted here should be self-contained. Feb 5, 2023 at 9:30
• 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$?
– joni
Feb 5, 2023 at 9:34
• "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. Feb 5, 2023 at 9:35
• @joni Thank you for the tip. I have updated the question accordingly. Feb 5, 2023 at 10:11
• @JoséCarlosSantos Thanks. I have fixed that now. Feb 5, 2023 at 10:12

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.

• 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? Feb 5, 2023 at 11:47
• 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? Feb 5, 2023 at 12:56
• 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.
– joni
Feb 5, 2023 at 13:00
• 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 Feb 5, 2023 at 13:03
• 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. Feb 5, 2023 at 13:38