Design a heart with DJC

In connection with the approaching Christmas, we are receiving many support questions about the use of mixed-integer conic optimization in the design of the traditional Danish "braided heart" Christmas tree decorations:

Let us demonstrate how this can be done with MOSEK. First, we need to define the heart. A suitable model is given by

$$x^2+(y-p|x|)^2\leq r^2,$$

where $p,r$ are parameters which can be adjusted for different shapes and sizes:

This is not a convex shape, but it can still be modelled in conic form if we employ a mixed-integer model of $|x|$. This can be done using a classical big-M approach or, in MOSEK 10, using a disjunctive constraint (DJC):

$$\begin{array}{l}(x\geq 0 \ \mathrm{AND}\ z=x)\ \mathrm{OR}\ (x\leq 0 \ \mathrm{AND}\ z=-x) \\  x^2+(y-pz)^2\leq r^2\end{array},$$

combining a DJC with a quadratic cone constraint in affine conic (ACC) form.

Having defined the domain, it is time to draw some lines with slope $\pm 45^\circ$ to determine the braided pattern. To do this, we will choose, one at a time, line segments with integer endpoints, say $x=(x_1,x_2)$, $y=(y_1,y_2)$, inside the heart. Such a line segment has the correct slope if

$$x_1-x_2=y_1-y_2\ \mathrm{OR}\ x_1+x_2=y_1+y_2,$$

which, again, is a disjunctive constraint. We will only choose sufficiently long line segments, for example by requiring

$$|x_1-y_1|\geq c$$

for some constant $c$. Here the absolute value can again be modelled in the same mixed-integer fashion as before. We set no objective, so this becomes a feasibility problem, but one could also decide, for instance, to maximize the length of the segment or optimize some other measure of beauty for the design.

Having found one segment, we will construct a new one by adding additional constraints to guarantee that the new segments do not interfere too much with the previous ones. For the sake of simplicity, we will demand that new endpoints do not belong to any line of slope $\pm 45^\circ$ containing the previous endpoints, but one could consider other elimination conditions as well. This iterative procedure is similar to solving the travelling salesman problem by cycle elimination, and it terminates once there is no more place for new segments under all the constraints. The implementation requires us to be able to write the "not equals" condition $x\neq a$, which, assuming we work with integers, can again be cast as a DJC:

$$x\leq a-1 \ \mathrm{OR}\ x\geq a+1.$$

The iterative procedure will construct more and more segments:

To obtain different designs, we can vary the parameters $p,r$. Still, there is enough freedom in the choice of segments that even just varying the random seed ("mioSeed") for the mixed-integer optimizer produces different final solutions for the same choice of $p,r$:

And on this note, we leave you with the Fusion API code below and wish you all the best. (You can also read our last Christmas special from way back in 2018).

MOSEK Team