Metraipolis › archive › dc_df39624ee23d

Face Identification via Polyhedral Relaxations for Binary Programs: A Comparison with Factor-Width Partial Facial Reduction — arXiv:2608.15676

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.15676
License (as archived)
CC0-1.0
Archived
2026-10-18T20:16:16.132Z
SHA-256 of the archived text
6fae56fc8b2029480ee8e937c6615a570baa010cdebd99a5b21504140bdc4334
Stable URL of this page
https://metraipolis.com/documento/dc_df39624ee23d

How to cite

Face Identification via Polyhedral Relaxations for Binary Programs: A Comparison with Factor-Width Partial Facial Reduction — arXiv:2608.15676 — arXiv (en), https://arxiv.org/abs/2608.15676 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_df39624ee23d (Metraipolis archive dc_df39624ee23d, sha256 6fae56fc8b2029480ee8e937c6615a570baa010cdebd99a5b21504140bdc4334)
BibTeX
@misc{dcdf39624ee23d,
  title = {Face Identification via Polyhedral Relaxations for Binary Programs: A Comparison with Factor-Width Partial Facial Reduction — arXiv:2608.15676},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.15676},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_df39624ee23d; sha256 6fae56fc8b2029480ee8e937c6615a570baa010cdebd99a5b21504140bdc4334},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15676. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Facial reduction (FR) is a preprocessing technique used to restore Slater's condition in semidefinite programming (SDP), but each step generally requires solving an auxiliary SDP. Factor-width-\(k\) partial FR restricts the class of exposing matrices. Increasing \(k\) enlarges this class, but, for \(k\geq3\), the auxiliary problem remains an SDP involving positive semidefinite blocks of order \(k\). For SDP relaxations of binary programs, we replace this auxiliary SDP by an LP-based face-identification method. We construct a polyhedron in subset-indexed moment variables that has polynomial size for fixed \(k\). The resulting face contains every feasible binary lift and is contained in every face exposed by a factor-width-\(k\) exposing matrix from the same auxiliary system. Thus, linear programming identifies a face no larger than those obtained from the factor-width-\(k\) auxiliary SDP while preserving all feasible binary points. To iterate the construction, we represent each identified face by linear equations in the original matrix variable, thereby retaining the moment-matrix indexing and the factor-width comparison at every iteration.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-18 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.15676 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T19:45:07.845Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).