# DD-Separated Facet Cuts for Fractional Architecture Search

- ID: 1543
- Canonical URL: https://synthcore.org/idea/1543/dd-separated-facet-cuts-for-fractional-architecture-search
- API JSON: https://synthcore.org/api/idea/1543.json
- API Markdown: https://synthcore.org/api/idea/1543.md
- Verification status: unverified
- Source: [arXiv:2607.28511](https://arxiv.org/abs/2607.28511)
- Category: optimization
- Solves: accuracy, scalability, speedup
- ML areas: pruning, moe-routing, fine-tuning
- Math tags: optimization, convex-analysis, combinatorics, graph-theory
- Ratings: usefulness 6/10; difficulty 7/10; novelty 8/10

## Idea description

Use the decision diagram as an exact optimizer over feasible binary gate paths to separate strong inequalities at the current fractional architecture. Add only violated cuts to the LP or MILP relaxation, rather than enumerating all gate configurations or relying on weak pairwise product constraints.

## Mathematical statement

Let MP_G be the convex hull of all valid vectors (z_v,z_e), and let omega lie in its interior. The translated polar consists of vectors u satisfying u^T(z-omega) <= 1 for every feasible vertex z. Given a fractional point bar_z, the cut-generating LP seeks a normalized vector u maximizing violation u^T(bar_z-omega), subject to u^T(z^k-omega)<=1 for every feasible binary configuration z^k. An exact DD supplies these configurations implicitly as source-to-sink paths, so the constraint family can be evaluated by dynamic programming or by the DD's flow formulation instead of explicit enumeration. If the optimum is rho>1, the resulting valid inequality u^T(z-omega)<=1 cuts off bar_z; equivalently u^T z <= 1+u^T omega. Here z contains both gate variables and monomial interaction variables, omega is a strictly interior reference point, bar_z is the current LP solution, and u is the cut coefficient vector.

## Key formulas

- $$(MP_G-\bm{\omega})^{\circ}=\{\mathbf{u}:\mathbf{u}^{\mathsf T}(\mathbf{z}-\bm{\omega})\le 1\ \ \forall\mathbf{z}\in MP_G\},$$
- $$\max_{\mathbf{u}}\ \mathbf{u}^{\mathsf T}(\bar{\mathbf{z}}-\bm{\omega})\quad\text{s.t.}\quad \mathbf{u}^{\mathsf T}(\mathbf{z}^{k}-\bm{\omega})\le 1\ \ \forall\mathbf{z}^{k}\in\mathcal{S}_G,$$
- $$\rho=\mathbf{u}^{\mathsf T}(\bar{\mathbf{z}}-\bm{\omega})>1\ \Longrightarrow\ \mathbf{u}^{\mathsf T}(\mathbf{z}-\bm{\omega})\le 1,$$
- $$\mathbf{u}^{\mathsf T}\mathbf{z}\le 1+\mathbf{u}^{\mathsf T}\bm{\omega}.$$

## Implementation notes

Integrate the method into the cut-generation loop of a MILP for binary neural architecture search, structured pruning, or constrained MoE routing. The master problem contains fractional gate variables x and interaction variables q, together with task-loss, latency, memory, and sparsity surrogates. At each root-node or selected branch-and-bound node, obtain the current fractional vector bar_z. Choose omega by solving a small LP that averages several feasible DD paths, or use the coordinate-wise average of 100 random valid configurations and verify that it is not on a known boundary. Solve the separation problem for u. For an MVP, enumerate all DD source-to-sink paths when the support has at most 20 gates; for larger DDs, use column generation: repeatedly find the path maximizing u^T(z-omega) by dynamic programming over DD states, add that path to the separation LP, and stop when no path violates the normalization constraint. Compact pseudocode is: bar_z = master.solve(); initialize path_set; repeat solve max_u u^T(bar_z-omega) subject to u^T(path-omega)<=1 for path in path_set; p = DD_longest_path(u); if u^T(p-omega)<=1+eps break; path_set.add(p); end; if rho>1+eps master.add_cut(u^T(z-omega)<=1). The DD supplies exact path maximization; the cut coefficients and separation frequency are empirical choices. Test first on a small supernet with 10-20 channel gates on CIFAR-10, comparing root gap closure and wall-clock time against McCormick-only and hand-added pairwise cuts. The expected signal is a larger root-node gap closure with fewer cuts, fewer branch-and-bound nodes, and a better accuracy/FLOP Pareto frontier at equal solver time.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.