Skip to content

Toggle Branch-Price Sparse Dual Formulation

Claim/Theorem

For any finite row support R\subseteq L_P, the coordinate-0 toggle instance has an exact sparse dual obstruction test.

For a row-weight vector w:R\to\mathbb R and a label \beta, define

\[ m_\beta(w)=\min_{H_\beta}\sum_{U\in R}w_U\mathbf 1[U\in H_\beta], \]

where the minimum ranges over all boundary-compatible upsets H_\beta of L_P, with h_\beta(\varnothing)=0, h_\beta(P)=1, and h_\beta(A_j)=\beta_j for all seven generators.

Every feasible toggle decomposition would imply

\[ \sum_{U\in R}w_U|U|\ge \sum_\beta m_\beta(w). \]

Therefore a strict reverse inequality is a finite sparse Farkas/Hall-type obstruction to the full 2,849,631-row problem.

The pricing problem defining each m_\beta(w) is an exact min-weight closure problem on the selected row projection: binary variables record the value of h_\beta on rows in R, order constraints impose monotonicity, and fixed constraints impose the generator boundary. This is the sparse row-supported version of the full column-generation pricing oracle.

The current implementation used R consisting of 750 rank-<=3 and coordinate-interface rows. The restricted master:

  • started from boundary-compatible forced-generator, repaired-principal, and threshold seed columns;
  • added 43, 31, 3, and 1 unseen columns across four pricing rounds;
  • ended with 138 columns;
  • still had restricted slack objective about 1962;
  • did not certify infeasibility because final pricing was not closed (pricing_timeout_or_error).

The explicit sparse dual families tested in this run did not obstruct f_3:

  • coordinate-0 singleton weight: zero gap;
  • coordinate-0 minus each other generator: zero gap;
  • rank-<=4 parity-signed support: negative gap;
  • small random rank-<=4 supports: no positive gap in the configured trials.

Dependencies

  • [[coordinate-zero-toggle-is-not-single-interface-transport.md]]
  • [[monotone-count-decomposition-is-column-generation-not-single-flow.md]]
  • [[route-d-full-rank-order-frontier-is-monotone-count-decomposition.md]]

Conflicts/Gaps

  • The branch-and-price run is a restricted row-support computation, not a solved full decomposition or full infeasibility certificate.
  • A positive restricted-master slack value is not by itself a certificate until pricing over unseen columns closes for that row support.
  • The next exact finite bottleneck is either a closed positive sparse-dual gap or a larger row support whose pricing loop can be certified.

Sources

  • local computation: docs/project_QEM-QEC/tmp/certificates/toggle_branch_price_report.json
  • local script: docs/project_QEM-QEC/tmp/scripts/route_d_toggle_branch_price.py
  • local computation: docs/project_QEM-QEC/tmp/certificates/monotone_count_decomposition_report.json