Exercise 1.8 (Road lighting)

Question

Consider a road divided into $n$ segments that is illuminated by $m$ lamps. Let $p_{j}$ be the power of the $j$ th lamp. The illumination $I_{i}$ of the $i$ th segment is assumed to be $\sum_{j=1}^{m} a_{i j} p_{j}$, where $a_{i j}$ are known coefficients. Let $I_{i}^{*}$ be the desired illumination of road $i$.\par 

We are interested in choosing the lamp powers $p_{j}$ so that the illuminations $I_{i}$ are close to the desired illuminations $I_{i}^{*}$. Provide a reasonable linear programming formulation of this problem. Note that the wording of the problem is loose and there is more than one possible formulation.

Elu Thingol · Accepted Answer

Our goal is to minimize the difference between the desired illumination $[I_{1}^{*}, \ldots, I_{n}^{*}]$ and the actual illumination $[I_{1}, \ldots, I_{n}]$. We could choose any kind of \href{https://en.wikipedia.org/wiki/Metric_(mathematics)}{metric} to do so, but the one suitable for the linear optimization is the sum of absolute errors (cf. residual minimization from Section 1.3):

$$d\left(\mathbf{I}^*,\mathbf{I}ight) = \sum_{i=1}^{n} \left|I_{i}^{*} - I_{i}ight|.$$

Considering the fact that the powers of the lamps cannot be negative, we formulate the above optimization problem as

\begin{equation*}
\begin{array}{ll}
	ext{minimize} \quad & \sum_{i=1}^{n} \left|I_{i}^{*} - \sum_{j=1}^{m} a_{ij}p_jight|\
	ext{subject to} \quad &p_j \geq 0,\quad j=1,\ldots,m
\end{array}.
\end{equation*}

We use the procedure from the Section 1.3 (Problems involving absolute values) to get rid of the absolute values:

\begin{equation*}
\begin{array}{lll}
	ext{minimize} \quad & \sum_{i=1}^{n} z_i\
	ext{subject to} \quad &z_i \geq I_{i}^{*} - \sum_{j=1}^{m} a_{ij}p_j &i=1,\ldots,n\
&z_i \geq -\left(I_{i}^{*} - \sum_{j=1}^{m} a_{ij}p_jight) &i=1,\ldots,n\
&p_j \geq 0 &j=1,\ldots,m
\end{array}
\end{equation*}

and to reformulate the above as a linear optimization problem:
\begin{equation*}
\begin{array}{lll}
	ext{minimize} \quad & \sum_{i=1}^{n} z_i\
	ext{subject to} \quad &z_i + \sum_{j=1}^{m} a_{ij}p_j\geq I_{i}^{*} &i=1,\ldots,n\
&z_i - \sum_{j=1}^{m} a_{ij}p_j\geq -I_{i}^{*}  &i=1,\ldots,n\
&p_j \geq 0 &j=1,\ldots,m
\end{array}.
\end{equation*}

Exercise 1.8 (Road lighting)

Answers

Comments

Exercise 1.8 (Road lighting)

Answers

Comments

Add answer