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:
$$x^2+(y-p|x|)^2\leq r^2,$$
where $p,r$ are parameters which can be adjusted for different shapes and sizes:
$$\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:
