The Strength of Root Cuts in an Extended Abstract Branch-and-Cut Model
The branch-and-cut paradigm has led to effective solvers for a wide range of mathematical optimization problems. Despite significant theoretical work on pure branching and pure cutting, less is known about their interaction. We study an extended abstract branch-and-cut model to investigate tradeoffs between branching and cutting, including the time to generate cuts. We prove that, under symmetric branching, some minimal-time tree has all cuts at the root, before the first branching node, and that there is an asymmetric setting where some minimal-time tree has no internal cuts, i.e., cuts…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.31774
curl -X POST /api/v1/records/arxiv/2610.31774/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.31774/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'