Face Identification via Polyhedral Relaxations for Binary Programs: A Comparison with Factor-Width Partial Facial Reduction
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.15676
curl -X POST /api/v1/records/arxiv/2608.15676/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.15676/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'