My solution is based on an augmenting chain search in a bipartite graph between variables $$$l$$$ and value assignments $$$r$$$ with somewhat arbitrary constraints of how many of certain $$$l \leftarrow r$$$ are taken. With some simple constraints it's a bipartite matching algorithm generalized to vertex capacities higher than 1, identical to Kuhn's algorithm. Unfortunately, for complicated constraints a simple augmenting chain may not exist although a more general reassignment is possible, and even if such a chain exists, it can be blocked by visiting an intermediate state with an incorrect recursive path. To find a link in a chain it is necessary to intersect the sets of assigned variables over all constraints that are saturated and prevent assigning $$$l \leftarrow r$$$. I'll start with the described constraint satisfaction version and later extend it with an optimization objective for the OXC adjustment cost.

For a long time I've tried to apply this algorithm to more or less the complete problem for $$$max\underline{{ }}conflict=1$$$. Turns out it's really bad at it, since with many constraints the set intersection for each potential assignment often becomes empty, and adding some shuffling algorithms didn't help enough.

Then I reluctantly switched to hierarchical or sequential assignment — for example, start with assigning demands only their planes somehow uniformly, then solve for the other variables keeping the plane assignment fixed. If the plane assignment made the problem unsatisfiable, too bad. But actually, with correct constraints each stage can be guaranteed satisfiable except for certain input parameters.

The final sequence I've used is planes $$$\rightarrow$$$ spines $$$\rightarrow$$$ OXCs $$$\rightarrow$$$ SO links.

1. Plane assignment must satisfy that each leaf-plane combination is used at most $$$S/P$$$ times, with the guarantee that each leaf degree in the leaf-leaf multigraph is at most $$$S$$$. For even $$$S/P$$$ such an assignment can always be constructed using Euler circuit and bipartite perfect matching, for odd it may not exist, for example when $$$S=P$$$ and demands create a triangle between leaves. This is why testcase 5 query 1 is impossible to solve with $$$max\underline{{ }}conflict=1$$$. For the AC algorithm this stage limits each demand-plane assignment with two constraints, and at least two links always exist from each unsatisfied demand.

2. Spine assignment must satisfy separately for each plane that each leaf-spine combination is used at most once, with the guarantee that each leaf degree in the leaf-leaf multigraph is at most $$$S/P$$$. It is trivial to solve by processing demands sequentially and assigning them any available spine at each demand endpoint, but since we'll need to optimize OXC adjustment cost and provide certain guarantees for the next stage, I've used the AC algorithm again. Considering even $$$S/P$$$, it is desirable for this stage to create a bipartite graph between spines, for example by forcing different parity of the spines at the two ends of each demand, or even forcing the spine indices to always differ exactly in the lowest bit. Such an assignment always exists by the same argument and the problem structure for the AC algorithm choosing a pair of spines to assign is also the same.

3. OXC assigment must satisfy separately for each plane that each spine-OXC combination is used at most $$$K$$$ times, with the guarantee that each spine degree in the spine-spine multigraph is at most $$$L$$$. Again it's the same problem. For even $$$K$$$ a solution always exists. For odd $$$K$$$ a solution may not exist, but if $$$S/P$$$ is even, the previous stage guaranteed the existence of a solution by enforcing bipartiteness. The only case left is covered by tests only in the first test case, for which this stage can certainly manage colouring two parallel edges in two colours.

4. SO link assignment is trivial to solve by processing demands sequentially, and even trivial to solve optimally for the OXC adjustment cost by selecting only no-adjustment assignments in the first pass and the rest in the second.

To incorporate the OXC adjustment cost into the algorithm, for each stage I defined an objective. The first stage minimizes the sum of absolute differences between the number of plane-group-group assignments in this query and the previous one. The second and the third do the same for plane-group-spine-group-spine and plane-OXC-group-spine-group-spine respectively. Then the AC algorithm can track the change of objective with each assignment/unassignment. The fastest modification is to order the immediate assignments $$$l \leftarrow r$$$ and reassignments $$$l' \not\leftarrow r, l \leftarrow r$$$ by the objective change. The slowest modification is to replace the recursive Kuhn-like implementation with an iterative Dijkstra-like implementation with negative edges without any visited masks, potentially allowing each $$$l$$$ to be revisited with lower and lower path cost again and again, even several times in a single chain, with exponential complexity worst case. I've used the latter everywhere, it turns out to be fast enough in practice.

That's it for the general $$$max\underline{{ }}conflict=1$$$ solution. If $$$S=P$$$ and plane assignment fails, I've used the same stages, but modified the objective of the first to also minimize the number of 2-demand buckets group-group-plane assignments can be merged into (to minimize the number of un-paired demands for $$$max\underline{{ }}conflict=2$$$), merged pairs of demands into one, skipped the spine stage, expanded pairs after the SO stage. This reduces the number of used OXC connections close to twice.

The remaining part of the solution handles the $$$max\underline{{ }}conflict=\frac{LP}{MK}+1$$$ case. In pretests $$$max\underline{{ }}conflict=\frac{LP}{MK} \gt 1$$$ was impossible, so I've focused on using less OXC connections and reusing the old ones with fixed $$$max\underline{{ }}conflict=\frac{LP}{MK}+1$$$. This part is also split into two stages.

1. Allocate the OXC connections minimizing the adjustment cost but providing sufficient group-group bandwidth. All the possible connections are partitioned into group-group cliques for each plane, OXC, spine, SO link index tuple. Each clique can provide a perfect matching. The point of this partition is to limit how badly a new connection can break the old ones. Then the group pairs are ordered by demand/bandwidth ratio in priority queues. Pairs allowing a connection reuse are biased to be selected earlier than pairs with somewhat higher ratio. As long as any pair has insufficient bandwidth and can reuse a connection, connection reuse is forced. If a group has sufficient bandwidth and can not reuse a connection, it is ignored. If the only way to satisfy a pair with insufficient bandwidth is to ignore the clique partitioning, it is done as a last resort. Sometimes the reuse prioritization is too aggressive and doesn't let some bandwidth requirements to be satisfied, for these rare cases there is a fallback with a less aggressive prioritization. I've tried to replace this stage with the AC algorithm as well, but didn't have enough time to develop it to comparable performance.

2. Assign demands the allocated group-group connections while satisfying the $$$max\underline{{ }}conflict$$$ constraint using the AC algorithm with no objective. There are 3 constraints limiting a demand-connection assignment, but 2 of them are pretty weak since leaf-spine connections are sparse, so it mostly achieves perfect saturation of the group-group connections.

# 1: OK [2703ms, 0MB]: 1 50      1 0       1 0       1 0       1 0       points 6350.0
# 2: OK [3656ms, 0MB]: 1 50      1 75      1 0       1 0       1 50      points 5975.0
# 3: OK [4140ms, 0MB]: 1 46.875  1 34.375  1 37.5    1 0       1 18.75   points 6087.5
# 4: OK [4796ms, 4MB]: 1 50      1 85.4557 1 32.6302 1 36.4193 1 29.7266 points 5797.3046875
# 5: OK [4828ms, 4MB]: 2 26.2817 1 56.2744 1 41.0278 1 30.1392 1 38.1104 points 5424.4995117188
# 6: OK [4812ms, 4MB]: 1 49.9878 1 78.418  1 21.7773 1 26.5625 1 19.7876 points 5910.400390625
# 7: OK [4828ms, 4MB]: 1 50      1 77.6302 1 18.2682 1 20.625  1 37.0312 points 5889.3359375
# 8: OK [4859ms, 3MB]: 1 50      1 66.4714 1 47.0182 1 27.1224 1 32.3307 points 5831.171875
# 9: OK [4921ms, 3MB]: 1 50      1 81.1279 1 36.7798 1 33.7524 1 39.8071 points 5775.5981445312
#10: OK [4890ms, 5MB]: 1 49.9878 1 76.9653 1 26.1719 1 31.5063 1 20.0928 points 5885.8276367188
#11: OK [4875ms, 3MB]: 1 50      1 71.1589 1 12.7734 1 47.0573 1 21.1328 points 5893.6328125
#12: OK [4921ms, 2MB]: 4 37.5977 4 32.3242 4 15.6006 4 12.915  4 8.17871 points 4930.1513671875
#13: OK [4921ms, 1MB]: 4 38.0859 4 43.335  4 10.2783 4 38.6719 4 7.44629 points 4836.5478515625
#14: OK [4843ms, 2MB]: 4 38.0859 4 35.9863 4 9.32617 4 16.8213 4 17.6514 points 4896.38671875
#15: OK [4890ms, 1MB]: 4 37.5977 4 36.6699 4 10.083  4 3.49121 4 13.501  points 4945.9716796875
#16: OK [4937ms, 2MB]: 4 38.0859 4 40.0391 4 15.2832 4 18.2861 4 15.4053 points 4868.701171875
#17: OK [4921ms, 2MB]: 4 37.5977 4 9.8877  4 37.1338 4 11.3281 4 10.0586 points 4931.982421875
#18: OK [4906ms, 2MB]: 4 37.5977 4 32.3242 4 9.10645 4 3.49121 4 7.78809 points 4979.0771484375
#19: OK [4921ms, 2MB]: 4 38.0859 4 32.959  4 24.0723 4 26.5381 4 22.4609 points 4817.6513671875
#20: OK [4859ms, 2MB]: 8 43.75   8 34.375  8 25.5371 8 23.1445 8 13.1836 points 5455.029296875
#21: OK [4890ms, 2MB]: 8 46.875  8 58.252  8 32.4219 8 28.0273 8 16.9922 points 5327.294921875
#22: OK [4890ms, 2MB]: 8 43.75   8 40.4785 8 24.4629 8 15.4297 8 14.0625 points 5460.44921875
#23: OK [4937ms, 2MB]: 8 46.875  8 58.3496 8 10.5469 8 10.2539 8 43.5547 points 5366.259765625

The idea will be to create $$$S/2$$$ pairs of spines ($$$s$$$, $$$s+1$$$) belonging to the same plane. For each flow between two leaves, we will create a connection from the spine $$$s$$$ to the spine $$$s+1$$$.

To do so, we first use the fact that each leaf appears in at most $$$S$$$ flows. Let's denote by $$$G$$$ the unoriented graph of flows between leaves. Each node of this graph is at most degree $$$S$$$. So it's possible to orient the edges of this graph in order to obtain a graph $$$G'$$$ with $$$\text{in_deg}(v) \leq S/2$$$ and $$$\text{out_deg}(v) \leq S/2$$$ for every vertex $$$v$$$ of $$$G'$$$. To do so one can add a new vertex $$$v_{odd}$$$ to $$$G$$$, then connect all vertices of $$$G$$$ whose degree is odd to $$$v_{odd}$$$, and then compute an eulerian cycle inside this new graph. The cycle can then be oriented, and we use this orientation for the construction of $$$G'$$$.

Now that we have an oriented graph of flows $$$G'$$$ with $$$\text{in_deg}(v) \leq S/2$$$ and $$$\text{out_deg}(v) \leq S/2$$$ for every vertex. We can now create a bipartite graph $$$B = X \cup Y$$$ where each side $$$X$$$ and $$$Y$$$ contains $$$N \cdot L$$$ vertices. One vertex $$$x_{g,l}$$$ in $$$X$$$ ($$$y_{g,l}$$$ in $$$Y$$$) for each leaf $$$(g,l)$$$. For each oriented flow $$$(g_A, l_A) \rightarrow (g_B, l_B)$$$ of $$$G'$$$ we add an edge between $$$x_{g_A, l_A}$$$ and $$$y_{g_B, l_B}$$$. Thus $$$deg(x_{g,l}) = \text{out_deg}((g,l)) \leq S/2$$$ and $$$deg(y_{g,l}) = \text{in_deg}((g,l)) \leq S/2$$$. Such a bipartite graph can be partitioned in $$$S/2$$$ maximum matching.

Each of the $$$S/2$$$ maximum matchings $$$M$$$ corresponds to a collection of oriented flows assigned to a pair of spines ($$$s$$$, $$$s+1$$$). In fact, as $$$M$$$ is a mathching of $$$B$$$, each leaf appears at most one time as the origin of a flow and at most one time as the destination of flow. So each leaf will be connected at most one time to the spine $$$s$$$ and at most one time to the spine $$$s+1$$$.

Now we only need to create the connections inside the OXCs of the plane. To do so, we create a new bipartite graph $$$B' = U \cup V$$$ where each side $$$U$$$ and $$$V$$$ contains $$$N$$$ vertices, one for each group. Vertices are named $$$u_g$$$ and $$$v_g$$$ for each group $$$g \leq N$$$. For each oriented flow $$$(g_A, l_A) \rightarrow (g_B, l_B)$$$ in $$$M$$$, we add an edge between $$$u_{g_A}$$$ and $$$v_{g_B}$$$. It can be verified that $$$deg(u_g) \leq L$$$ and $$$deg(v_g) \leq L$$$ for each group $$$g$$$. This is because each group has $$$L$$$ leaves and each leaf appears at most one time. Then $$$B'$$$ can be partitioned in $$$L$$$ maximum matchings. Each matching $$$M'$$$ computed corresponds to a set of oriented flows assigned to one of the M/P OXCs of the plane using one of the K indices of links spine-OXC. This works because when $$$CR=1$$$, we have $$$L = (M/P)*K$$$. The corresponding OXC and link index are $$$m_{M'}$$$ and $$$k_{M'}$$$.

Finally, we map each oriented flow $$$(g_A, l_A) \rightarrow (g_B, l_B)$$$ in $$$M$$$ to one of the edges $$$(u_{g_A})-(v_{g_B})$$$. This last edge belongs to a matching $$$M'$$$ such that we can connect the two leaves of this flow using the OXC $$$m_{M'}$$$ between the ports $$$(g_A, s, k_{M'})$$$ and $$$(g_B, s+1, k_{M'})$$$. As $$$M'$$$ is a matching of $$$B'$$$ we now have a solution with $$$MFC=1$$$ as each port is used at most one time.

In that case, each flow is assigned to one spine.

To do so, we use the fact the graph of flows $$$G$$$ is bipartite. Each node of $$$G$$$ has degree at most $$$S$$$, so we can partition $$$G$$$ in $$$S$$$ maximum matchings. Each maximum matching $$$M$$$ corresponds to a set of flows that can be assigned to a single spine $$$s$$$ as each leaf appears at most one time.

For each matching $$$M$$$, we now need to setup the connection of the OXCs belonging the plane of $$$s$$$. We will make connections between ports with link index $$$k=0$$$ and $$$k=1$$$. For this, we create a new graph $$$G'$$$ with $$$N$$$ vertices. One vertex $$$v_g$$$ for each group. For each flow $$$(g_A, l_A) - (g_B, l_B)$$$ in $$$M$$$, we add an edge $$$v_{g_A} - v_{g_B}$$$ in $$$G'$$$. As each group has $$$L$$$ leaves and each leaf appears at most one time in $$$M$$$, $$$deg(v) \leq L$$$ for each vertex $$$v$$$ in $$$G'$$$. We can then orient the edges of $$$G'$$$ in order to obtain a new graph $$$H$$$ with $$$\text{in_deg}(v) \leq L/2$$$ and $$$\text{out_deg}(v) \leq L/2$$$ for each vertex $$$v$$$ in $$$H$$$.

We now create a bipartite graph $$$B = X \cup Y$$$ where each side $$$X$$$ and $$$Y$$$ contains $$$N$$$ vertices, one for each group. For each oriented arc $$$g_A \rightarrow g_B$$$ in $$$H$$$, we add an edge $$$x_{g_A} - y_{g_B}$$$ in $$$B$$$. Vertices of $$$B$$$ have at most degree $$$L/2$$$, so $$$B$$$ can be partitioned in $$$L/2$$$ maximum matchings. As $$$CR=1$$$, we have $$$L = (M/P)*K$$$, and since $$$K=2$$$, we have $$$M/P=L/2$$$. Thus each mathching $$$M'$$$ in $$$B$$$ can be assigned to $$$m_{M'}$$$, one of the OXC of the plane.

Finally, we map each oriented flow $$$(g_A,l_A)-(g_B,l_B)$$$ in M to one of the edges $$$x_{g_A} - y_{g_B}$$$. This last edge belongs to a matching M′ such that we can connect the two leaves of this flow using the OXC $$$m_{M'}$$$ between the ports $$$(g_A,s,0)$$$ and $$$(g_B,s,1)$$$. As M′ is a matching of B we now have a solution with MFC=1 as each port is used at most one time.