dot-cardinality_branch_bound: Branch and bound over the moment constraints

In couplr: Optimal Pairing and Matching via Linear Assignment

Branch and bound over the moment constraints

Description

Searches the tree of inclusion decisions, bounding every node by its Lagrangian relaxation and keeping an incumbent that satisfies every stated constraint. Returns at any interruption with that incumbent and a global bound that is valid for the whole problem, never with an unproven claim of optimality.

Usage

.cardinality_branch_bound(
  problem,
  index = NULL,
  coefs = NULL,
  dual_steps = 20L,
  branch = c("unit", "pair"),
  node_limit = 500L,
  time_limit = Inf,
  should_stop = NULL,
  cost = NULL,
  tol = 1e-09
)

Arguments

problem	The network, or the pair .balance_flow_problem() returns.
index	The network's index, unless problem carries one.
coefs	Moment coefficients, one per one-sided row.
dual_steps	Multiplier updates per node.
branch	Whether to branch on left-unit inclusion or on pairs.
node_limit, time_limit	Search budget, in nodes and in seconds.
should_stop	Optional predicate of the search state; TRUE stops the search the way an interrupt would.
cost	Optional distance matrix for the audit.
tol	Numeric tolerance for certification, pruning and the row values.

Details

time_limit reaches the solver. A solve that runs out of budget stops between augmentations and comes back saying so, and the node it belonged to goes back on the frontier unopened, so the bound the search reports still covers the whole tree.

Value

A list of class cardinality_run.

couplr documentation built on Sept. 17, 2026, 1:08 a.m.