PaperlayerView exact revision on arXiv

Source-linked AI summary

A branch-and-filter method for mixed-integer linear programming

Nikos Dimou

arXiv:2610.32165v1math.OCcs.NAmath.NA

TL;DR

Existing MILP tree-search strategies use feasibility and objective information, but their node-selection criteria do not ensure progress toward integrality. The paper introduces branch-and-filter, combining integrality and objective filtering with a lower-bound-anchored funnel and restoration; it establishes convergence and an O(ε^-1) outer-iteration route to ε-optimality under stated assumptions.

  • Problem

    Existing tree-search selection rules use feasibility and objective information, but their criteria are not based on conditions sufficient for progress toward integrality.

    Source: §1 · p. 2

  • Method

    Branch-and-filter combines branching with a node-acceptance filter on integrality violation and an incumbent-dependent objective coordinate, a lower-bound-anchored funnel, and restoration when needed.

    Source: §1 · p. 2

  • Results

    Under mild assumptions, branch-and-filter finitely certifies infeasibility or converges to global optimality; with a bounded filter metric, it reaches ε-optimality within O(ε^-1) outer iterations, and BB/BC beat Gurobi on the selected batch.

    Source: §1 · p. 2, §7 · p. 29

  • Takeaways & Limitations

    The experiments indicate that restoration is a central target for improvement, while selected-batch results motivate further development of an efficient restoration oracle for generic MILPs.

    Source: §7 · p. 30

    Cell-deletion restoration can be costly when auxiliary disjunctive subproblems are expensive, prompting a hybrid with a branch-and-bound fallback.

    Source: §6.3 · p. 25, §7 · p. 29

Abstract

from arXiv · show

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 $\mathcal{O}(\varepsilon^{-1})$ to certification of an $\varepsilon$-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.

1 Introduction

Existing MILP tree-search strategies use feasibility- and objective-related information, but their selection criteria do not ensure progress toward integrality. The paper introduces branch-and-filter, which combines a filter, funnel, and restoration phase and establishes convergence and iteration-complexity guarantees.

Motivation

  • Existing best-bound, depth-first, best-projection, best-estimate, and hybrid node-selection rules use feasibility or objective information, but their selection criteria do not ensure progress toward integrality.This motivates controlling progress through the node-acceptance mechanism itself.Source: §1 · pp. 1–2

Contribution

  • Branch-and-filter uses integrality violation and an incumbent-dependent objective coordinate to admit nodes, while a funnel tracks promising nodes and restoration is called when the search cannot select a parent.The restoration oracle can modify branch-and-bound or branch-and-cut methods; with bounded integer variables, the paper also introduces a cell-deletion implementation.Source: §1 · p. 2

Theoretical results

  • Under standard assumptions, the algorithm either finitely certifies infeasibility or optimality, or generates iterates whose objective values converge to the optimum.When a convergent subsequence exists, it converges to a global optimum; under a boundedness assumption on the filter objective metric, an ε-optimal solution is obtained within O(ε^-1) outer iterations.Source: §1 · p. 2

Related work

  • Earlier MILP uses of “filter” have different purposes, while the related nonlinear-programming approaches use filters to balance objective improvement and constraint violation.The paper distinguishes its node-acceptance mechanism from binary-solution screening, graph-coloring and satisfiability filtering, and filters used in nonlinear or mixed-variable methods,,,.Source: §1 · p. 2

2 Algorithm overview

The overview presents branch-and-filter as a tree search that combines branching and incumbent updates with filter-based node acceptance, a lower-bound-anchored funnel, and restoration when no acceptable candidate is found.

2.2 Branching and incumbent update

  • Branching solves the relaxed LPs of child nodes, fathoms nodes using infeasibility, lower bounds, or incumbent-based tests, and updates the incumbent by optimizing continuous variables for a verified integer vector.The fixed-integer update solves over the original constraints, so its feasible solution need not belong to the node that supplied the integer vector.Source: §2.2 · pp. 3–4

2.3 The filter mechanism

  • The filter compares integrality violation with an incumbent-dependent objective gap, admitting fractional points that meet its acceptance criterion and deleting dominated filter pairs.Before an incumbent exists, the gap measures shortfall below a reference level; afterward, it measures the difference from the incumbent.Source: §2.3 · pp. 4–5
  • The filter’s slanting-envelope acceptance rule prevents accepted points from accumulating near earlier points, enforcing integrality violation to vanish along the accepted sequence.The objective-gap coordinate can admit a point with a stronger relaxation bound even when its objective value and integrality violation rise, unlike the corresponding objective-value filter.Source: §2.3 · pp. 5–6

2.4 The funnel mechanism

  • The funnel restricts the search to candidates whose objective values remain sufficiently close to the global relaxation lower bounds, and the algorithm seeks filter-admissible points within it.The paper identifies this combined filter-and-funnel search as the mechanism for asymptotic feasibility and optimality.Source: §2.4 · p. 7

2.5 The restoration phase

  • When no point in the funnel is filter-admissible, restoration searches for an acceptable point that is not necessarily a node-relaxation minimizer, or returns an outcome that closes the node.A restoration result may also update the incumbent or return a filter-admissible point; the algorithm terminates if the open pool empties.Source: §2.5 · p. 7

2.6 The branch-and-filter algorithm

  • The outer algorithm initializes the root relaxation, branches, updates incumbents and fathoms nodes, checks global bounds, then admits a filter point or invokes restoration.Its inputs include β, γ, δ, and a funnel function; the initialization sets the reference level to the root LP value plus δ.Source: §2.6 · p. 8

3 Global convergence and optimality

Under assumptions including exact LP solves and a finitely terminating restoration oracle, the algorithm preserves coverage of incumbent-improving feasible points and either terminates with a certificate or optimal solution, or converges toward global optimality. A modified filter-only variant instead targets feasibility.

3 Global convergence and optimality

  • The guarantees assume exact LP subproblem solutions, valid finite branching actions, and a restoration oracle that returns one prescribed outcome after finitely many steps.The paper notes that the oracle's finite-step condition can be difficult to satisfy in practice; its proposed realization assumes bounded integer variables.Source: §3 · p. 9
  • The filter's admission rule ensures that between any two admitted iterates, either integrality violation contracts by β or the incumbent-gap measure decreases by at least γ times the later violation.This progress relation underlies the proof that integrality violation converges to zero.Source: §3 · pp. 9, 13
  • The proof maintains coverage of every feasible point that can improve the incumbent through valid node updates, supporting the global termination tests.For a nonempty open pool, the best global relaxation lower bound does not exceed the mixed-integer optimum.Source: §3 · pp. 10–12
  • Theorem 3.6 gives three outcomes: finite infeasibility certification, finite termination at a mixed-integer optimum, or an infinite sequence whose objective values converge to the optimum.In the infinite case, integrality violation vanishes and every limit point is globally optimal.Source: §3 · pp. 12–14

3.1 The filter as a feasibility mechanism

  • Removing the funnel changes the restoration target from node-optimal points to mixed-integer feasible points, while the filter still drives integrality violation to zero.Every accumulation point is then feasible, and the paper states feasibility can be recovered in finitely many outer iterations.Source: §3.1 · p. 14

4 Iteration complexity

The section bounds the outer iterations needed to obtain an ε-optimal feasible solution by tracking filter admissions and recovering feasible points through fixed-integer LP solves. Ignoring logarithmic terms, the resulting worst-case bound is O(ε^-1).

4 Iteration complexity

  • Recovery rounds the admitted point's integer coordinates to a nearest integer vector and solves the corresponding fixed-integer LP over the original constraints.If feasible, the resulting point updates the incumbent and its gap to the lower bound is tested against the tolerance.Source: §4 · p. 15
  • The complexity analysis assumes the incumbent-gap measure is uniformly bounded over successful iterations.Under bounded integer variables and a nonempty feasible set, the paper gives a condition ensuring such a bound when an initial feasible solution is available.Source: §4 · p. 15
  • The iteration count is obtained by bounding admissions above integrality-violation thresholds and then choosing a threshold that guarantees ε-optimal recovery.The stated theorem returns an ε-optimal feasible solution or terminates earlier with a global optimum.Source: §4 · pp. 16–17
  • Ignoring logarithmic terms, the worst-case number of outer iterations to an ε-optimal solution, or an earlier exact optimum, is O(ε^-1).The theorem invokes feasibility recovery after replacement-node construction and at the end of initialization.Source: §4 · pp. 16–17
  • Replacing the incumbent-gap metric g with the objective function f yields a tighter iteration-complexity bound.The paper attributes this to monotonicity of lower bounds together with the funnel property.Source: §4 · p. 17

5 A realization of the restoration oracle

The restoration oracle can be realized with different solvers, including a cell-deletion procedure that preserves mixed-integer feasible and filter-funnel-admissible points. Under a bounded-integer-variable restriction and exact inner solves, the procedure terminates finitely; its inner subproblem also admits an exact polyhedral representation.

5.1 The cell-deletion algorithm

  • Cell deletion repeatedly excludes rejected points’ touching cells while preserving mixed-integer feasible and filter-funnel-admissible points.The process continues until it finds an admissible fractional point, a node-optimal mixed-integer solution, or certifies that no improving feasible solution exists at the node.Source: §5 · p. 18, §5.1 · p. 19
  • 2p LPs form the initial test; feasible solutions yield a global optimum or (OR3), while infeasibility in all directions triggers the iterative stage.Source: §5.1 · pp. 18–19
  • Under F5’s bounded-integer-variable restriction on relaxations, exact inner solves make cell deletion terminate finitely with one of (OR1)–(OR3).The restriction allows continuous variables to remain unbounded.Source: §5 · p. 18, §5.1 · p. 21

5.2 An exact polyhedral representation of the inner subproblem

  • The inner subproblem has an exact union-of-polyhedra representation that can be solved through finitely many LPs or disjunctive programming, but this decomposition can be computationally expensive.In the worst case, restoration may require exhaustive exploration.Source: §5.2 · pp. 22–23

6 Numerical experiments

The experiments compare three branch-and-filter restoration-oracle implementations with benchmark solvers, testing restoration speed, optimality performance, and time to approximate solutions. Results show trade-offs among early filter-admissible returns, node completion, and approximate-solution speed.

6.1 Implementations of branch-and-filter

  • BF-BB and BF-BC solve node-restricted Gurobi models with cuts disabled or enabled, while BF-CD uses grouped cell deletion represented by an indicator MILP.All variants use specified solver tolerances, and reported optimality is validated within an error gap of at most 10^-6.Source: §6.1 · p. 24

6.2 Restoration experiments

  • BF-CD is faster on 13 of 16 shared OR3 cases against BF-BB and 10 of 13 against BF-BC, with a median elapsed time of 0.010 s.It tends to return admissible points with higher integrality violation but better objective reduction, while branching alternatives more often complete node optimization.Source: §6.2 · p. 25

6.3 Optimality experiments

  • With the second parameter setting, both BF-BB variants outperform SCIP on every problem, and BF-BB and BF-BC terminate within two outer iterations per instance.They return almost no OR3 outcomes, compared with about 17 outer iterations on average in the previous run.Source: §6.3 · p. 26, Table 3 · p. 26

6.4 Time to approximate solutions

  • At 0.5% error, BF-BC-g has a 1.620 ratio, lowering τ_ε from 212.356 to 131.066 ms versus Gurobi-BC.The advantage extends across approximately 0.3%–0.7% error, although Gurobi reaches optimality faster in both parameter settings.Source: Figure 3 · p. 27, §6.4 · p. 28
  • In the tighter parameter setting, BF-BB-g outperforms Gurobi-BB over 0.52%–1% error; at ε = 0.002, batch maximum and mean target times are 52.5% and 20.8% lower.In both settings, however, Gurobi reaches optimality faster than BF.Source: Figure 3 · p. 27, §6.4 · p. 28

7 Discussion

The discussion reports faster approximate-solution identification than Gurobi in the selected batch, while emphasizing restoration costs and open questions about parameter tuning, optimality mechanisms, and broader evaluation.

7 Discussion

  • The authors propose adding cut generation and domain propagation, trying nonmonotone filters, and testing branch-and-filter in settings such as convex MINLP.They note that warranties for more complicated filters require rigorous verification.Source: §7 · p. 28
  • The filter acceptance rule should be studied as a node-selection component against best-bound, depth-first, and hybrid strategies in a common solver environment.The discussion also proposes studying its role in finding a first feasible solution and comparing it with feasibility-pump methods.Source: §7 · p. 28
  • The g objective measure promotes increasing rather than decreasing objective values and seems to perform better in settings where branch-and-filter is competitive, despite a worse outer-iteration complexity bound than f.The authors call for analysis of the measures’ respective advantages and limitations.Source: §7 · p. 29
  • The filter drives iterates toward integrality, while the funnel mechanism ensures convergence to global optimality; alternative optimality mechanisms remain a research direction.The authors propose investigating alternatives while preserving global-optimality guarantees.Source: §7 · p. 29
  • Cell deletion often quickly returns a fractional filter-admissible point, but repeated auxiliary disjunctive solves can make its full stage expensive.A branch-and-bound fallback accelerates convergence; the experiments suggest balancing fractional filter-admissible and node-optimal points can reduce computational work.Source: §7 · p. 29
  • The tested panel’s worst-case time-to-target results indicate faster approximate optimal-solution identification than Gurobi under standard branch-and-bound and branch-and-cut restoration.The authors say a much more thorough computational study is needed to determine the method’s absolute efficiency.Source: §7 · p. 29
  • A significant part of the computational work occurs in restoration, making improvement of that phase a central research direction.The authors identify efficient restoration as important to realizing branch-and-filter’s potential for generic MILPs.Source: §7 · p. 30

Use of AI Statement

The author acknowledges ChatGPT-Pro (GPT-6 Astra) for figure generation and table exposition, and the same model and Codex for assisting with numerical-experiment implementation.

Use of AI Statement

  • ChatGPT-Pro (GPT-6 Astra) helped generate figures and improve the final exposition of tables.The author takes responsibility for the veracity of the paper’s theoretical claims and technical details.Source: Use of AI Statement · p. 30
  • ChatGPT-Pro (GPT-6 Astra) and Codex assisted with implementing the numerical experiments in Section 6.The statement separately acknowledges figure and table assistance from ChatGPT-Pro (GPT-6 Astra).Source: Use of AI Statement · p. 30
Loading 2610.32165v1…