Christmas lights

In this year's Christmas blogpost, we explain how to properly hang the Christmas lights on the Christmas tree 🎄.

Let us fix some notation. The 🎄 in dimension $D\geq 2$ is (surprise!) a reflected and rescaled quadratic cone:

$$(x_1,\ldots,x_D) \in \unicode{x1F384} \subseteq\mathbb{R}^D\quad  \iff\quad W(1-x_D/T)\geq \|x_{1:D-1}\|_2,\ x_D\geq 0$$

where $T$ is the coordinate of the top and $W$ is a width rescaling parameter. The tree comes decorated with $P$ ornaments located at $c_1,\ldots,c_P\in\unicode{x1F384}$. Here is an example in dimension $D=2$.

The Christmas lights chain consists of $N$ bulbs evenly spaced in distance $L$ along the wire. Their  locations $x_1,\ldots,x_N\in \unicode{x1F384}$ are to be determined.  If, like us, you have been collecting and repairing your lights for almost 25 years then it is possible that each of the lightbulbs shines with different power $I_1,\ldots,I_N$.

The main requirement we have is that each of the ornaments is nicely illuminated, more precisely we wish to maximize the total amount of light received by the worst-illuminated ornament. Let $\mathrm{il}_j(d)$ be the amount of light that a point in distance $d$ from the light source receives from the $j$-th lightbulb. Obviously $\mathrm{il}_j(d)$ is a decreasing function of the distance $d$ to the bulb. That leads us to the optimization problem:

$$\begin{array}{llrr}\mathrm{maximize} & \mathrm{il}_{MIN}  & &\\ \mathrm{s.t.} & \mathrm{il}_{MIN}\leq \sum_{j=1}^N \mathrm{il}_j(d_{ij}) & i=1,\ldots,P & (2.1) \\ & d_{ij}\geq \|x_j-c_i\|_2 & i=1,\ldots,P,\ j=1,\ldots,N &(2.2) \\ & \|x_j-x_{j+1}\|_2\leq L & j=1,\ldots,N-1 & (2.3) \\ & x_j \in \unicode{x1F384} & j=1,\ldots,N &(2.4) \\ & x_1 = (W,0,\ldots) & &(2.5)\end{array}$$

In principle we should let the brightness of the $j$-th bulb decay as $\mathrm{il}_j(d)=I_j/d^{D-1}$, but that does not lead to a convex constraint in (2.1). Instead, let us use a piecewise-linear approximation $\widetilde{\mathrm{il}_j}(d)=\mathrm{max}(I_i-d,0)$. This function is not concave either, so it cannot be used directly in (2.1) in a continuous fashion, but when written as

$$(d\in[0,I_j]\ \mathrm{and}\ \widetilde{\mathrm{il}_j}(d) = I_j-d)\ \mathrm{or}\ (d\geq I_j\ \mathrm{and}\ \widetilde{\mathrm{il}_j}(d) = 0)$$

it becomes evidently definable via a disjunctive constraint. Here is a rough comparison between $\mathrm{il}_j(d)$ and $\widetilde{\mathrm{il}_j}(d)$:

Let us quickly recap problem (2): constraint (2.1) (with $\widetilde{\mathrm{il}_j}$ in place of $\mathrm{il}_j$) computes the approximate amount of light received by each ornament as a function of the distance $d_{ij}$ from the $i$-th ornament to the $j$-th bulb; that distance is computed in (2.2). Two consecutive lightbulbs cannot be spaced by more than the wire length between them, as in (2.3), while (2.5) ensures that the chain starts at the fixed bottom point of the tree, where the electric socket is. The complete MOSEK Fusion model can be found on GitHub; it is a mixed-integer (due to the disjunctive constraints) second-order cone optimization problem.

We end with some examples. The ornaments have been given intensity according to the amount of light received. The disk sizes correspond to the brightness of lightbulbs.

It remains to wish all readers a very well-lit 🎄 and Happy New year 2024!

The MOSEK team