A branch-and-filter method for mixed-integer linear programming
Abstract
We develop a new tree-search framework for mixed-integer linear programming problems, which incorporates a filter mechanism as a node-acceptance device. The introduced branch-and-filter algorithm combines proper branching actions with a filter on integrality violation and an incumbent-dependent objective coordinate. Inspired by classical filter methods in nonconvex constrained optimization, the proposed method moves to a restoration phase whenever sufficient progress cannot be provided by the filter and funnel mechanisms, the latter of which is anchored at global relaxation lower bounds. Under mild assumptions, the introduced method either certifies infeasibility in finitely many iterations, or converges to global optimality. Moreover, we establish a total outer iteration complexity bound of order 𝒪(ε−1) to certification of an ε-optimal mixed-integer solution through fixed-integer linear programming recovery. We finally perform several numerical experiments to study the performance of branch-and-filter against benchmark solvers, under a branch-and-bound, a branch-and-cut, and a novel cell-deletion realization of the proposed restoration oracle.
Related
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework
- Non-convex integer programming: a deterministic solution method of the large block sale problem
- Autoregressive Differentiable Method for Integer Programming
- Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
BibTeX
@misc{dimou2026branchandfilter,
title = {{A branch-and-filter method for mixed-integer linear programming}},
author = {Nikos Dimou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32165},
eprint = {2610.32165},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32165},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A branch-and-filter method for mixed-integer linear programming
AU - Nikos Dimou
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32165
UR - https://arxiv.org/abs/2610.32165
AB - We develop a new tree-search framework for mixed-integer linear programming problems, which incorporates a filter mechanism as a node-acceptance device. The introduced branch-and-filter algorithm combines proper branching actions with a filter on integrality violation and an incumbent-dependent objective coordinate. Inspired by classical filter methods in nonconvex constrained optimization, the proposed method moves to a restoration phase whenever sufficient progress cannot be provided by the filter and funnel mechanisms, the latter of which is anchored at global relaxation lower bounds. Under mild assumptions, the introduced method either certifies infeasibility in finitely many iterations, or converges to global optimality. Moreover, we establish a total outer iteration complexity bound of order 𝒪(ε^−1) to certification of an ε-optimal mixed-integer solution through fixed-integer linear programming recovery. We finally perform several numerical experiments to study the performance of branch-and-filter against benchmark solvers, under a branch-and-bound, a branch-and-cut, and a novel cell-deletion realization of the proposed restoration oracle.
ER -