Nonlinear Branch & Bound (NLP-BB)

Nonlinear Branch & Bound (NLP-BB)#

For MINLPs whose continuous relaxation is convex, discopt can use nonlinear Branch & Bound (NLP-BB) instead of the default spatial B&B with McCormick relaxations. NLP-BB branches only on discrete variables and solves the original continuous NLP at each node, using the NLP objective as a valid lower bound [Kröger et al., 2018].

NLP-BB is a simpler algorithm than spatial B&B: it skips McCormick relaxation compilation, alphaBB underestimators, OBBT/FBBT bound tightening, and strong branching setup. For convex models, discopt’s spatial B&B already bypasses most of this overhead, so the two methods produce similar performance on CPU. The primary value of NLP-BB is:

  1. Simpler code path: no relaxation infrastructure setup for convex MINLPs.

  2. GPU scaling (future): the streamlined loop has fewer synchronization points for batch vmap solving.

  3. No MIP solver dependency: useful in deployment environments without HiGHS.

Note

NLP-BB is no longer what a default solve() picks for a convex MINLP. A model certified convex at the root is now routed to the MIP–NLP family — outer approximation [Duran and Grossmann, 1986] — which closes it without opening a B&B node at all, so result.nlp_bb comes back False and result.node_count is 0. The cells below print result.algorithm_route so the route is visible, and reach NLP-BB explicitly with nlp_bb=True. For MILP and MIQP, specialized solvers (HiGHS, QP-BB) take priority.

import discopt.modeling as dm
import numpy as np

Problem: Facility Activation with Nonlinear Costs#

A company decides which of \(k\) facilities to activate (binary \(y_i\)) and how much capacity \(x_i\) to allocate. Operating costs follow an exponential model:

\[\min_{x,y} \; \sum_{i=1}^{k} \bigl(c_i \, y_i + e^{\alpha_i x_i}\bigr) \quad \text{s.t.} \quad \sum_i x_i \ge D, \quad x_i \le M\,y_i, \quad x_i \ge 0, \quad y_i \in \{0,1\}\]

This is a convex MINLP: \(e^{\alpha x}\) is convex for any \(\alpha > 0\), fixed costs are linear, and all constraints are linear.

k = 5
fixed_costs = np.array([5.0, 8.0, 6.0, 7.0, 4.0])
alphas = np.array([0.3, 0.25, 0.35, 0.28, 0.32])
M = 8.0
D = 10.0


def build_model():
    m = dm.Model("exp_facility")
    y = m.binary("activate", shape=(k,))
    x = m.continuous("capacity", shape=(k,), lb=0, ub=M)

    obj = 0
    for i in range(k):
        obj = obj + fixed_costs[i] * y[i] + dm.exp(alphas[i] * x[i])
    m.minimize(obj)

    total_cap = 0
    for i in range(k):
        total_cap = total_cap + x[i]
    m.subject_to(total_cap >= D)

    for i in range(k):
        m.subject_to(x[i] <= M * y[i])

    return m

Automatic Selection#

Calling solve() with default settings on this convex nonlinear MINLP selects neither NLP-BB nor spatial B&B: the convex-MINLP route hands it to OA, which certifies the optimum at the root. result.nlp_bb and result.algorithm_route together say which mode actually ran — the cell asserts on both rather than describing one.

m = build_model()
result = m.solve()

print(f"Status:        {result.status}")
print(f"Objective:     {result.objective:.4f}")
print(f"Gap:           {result.gap}")
print(f"NLP-BB used:   {result.nlp_bb}")
print(f"Gap certified: {result.gap_certified}")
print(f"Nodes:         {result.node_count}")
print(f"Route:         {result.algorithm_route}")
print(f"Wall time:     {result.wall_time:.3f}s")

# The claim above, asserted rather than described: the default is the convex-MINLP
# OA route, not NLP-BB and not spatial B&B.
assert result.nlp_bb is False, "the default route is no longer NLP-BB"
assert result.node_count == 0, "the OA route closes this model without a B&B node"
assert "oa" in (result.algorithm_route or ""), result.algorithm_route

OA: generating OA cuts for 0 of 6 rows (6 convex; the rest are either nonconvex or already exact in the master)

Status:        optimal
Objective:     21.4029
Gap:           0.0
NLP-BB used:   False
Gap certified: True
Nodes:         0
Route:         mip-nlp/oa: minlp certified convex at the root (DISCOPT_CONVEX_MINLP_ROUTE)
Wall time:     0.070s

Comparison: NLP-BB vs Spatial B&B#

We can force spatial B&B with nlp_bb=False and compare. Both should find the same optimum. For convex models, discopt’s spatial B&B already skips McCormick relaxations and uses the NLP objective as the lower bound, so the two methods solve similar subproblems at each node. Performance differences on CPU are largely due to setup overhead and multistart randomness [Belotti et al., 2013].

_fmt_gap = lambda v: f"{v:>12.2e}" if v is not None else f"{'n/a':>12}"
m = build_model()

result_nlpbb = m.solve(nlp_bb=True)
result_spatial = m.solve(nlp_bb=False)

rn = result_nlpbb
rs = result_spatial
print(f"{'Metric':<18} {'NLP-BB':>12} {'Spatial B&B':>12}")
print("-" * 44)
print(f"{'Objective':<18} {rn.objective:>12.4f} {rs.objective:>12.4f}")
print(f"{'Gap':<18} {_fmt_gap(rn.gap)} {_fmt_gap(rs.gap)}")
print(f"{'Nodes':<18} {rn.node_count:>12d} {rs.node_count:>12d}")
print(f"{'Wall time (s)':<18} {rn.wall_time:>12.3f} {rs.wall_time:>12.3f}")
print(f"{'Gap certified':<18} {str(rn.gap_certified):>12} {str(rs.gap_certified):>12}")

# Both arms must genuinely be the arm they are labelled, and must agree.
assert rn.nlp_bb is True, "the NLP-BB column did not run NLP-BB"
assert rs.nlp_bb is False and rs.node_count > 0, "the spatial column did not branch"
assert abs(rn.objective - rs.objective) < 1e-6, "the two methods disagree"

OA: generating OA cuts for 0 of 6 rows (6 convex; the rest are either nonconvex or already exact in the master)

Metric                   NLP-BB  Spatial B&B
--------------------------------------------
Objective               21.4029      21.4029
Gap                    0.00e+00     0.00e+00
Nodes                        31           41
Wall time (s)             0.351        0.511
Gap certified              True         True

Inspecting the Solution#

result = m.solve()

activated = result.x["activate"]
capacities = result.x["capacity"]

print("Facility  Cost  Alpha  Active  Capacity")
print("-" * 42)
for i in range(k):
    active = "Yes" if activated[i] > 0.5 else "No"
    c = fixed_costs[i]
    a = alphas[i]
    cap = capacities[i]
    print(f"  {i + 1:>3}    {c:>5.1f}  {a:.2f}   {active:<4}  {cap:>8.3f}")
print(f"\nTotal capacity: {np.sum(capacities):.3f} (demand: {D})")

OA: generating OA cuts for 0 of 6 rows (6 convex; the rest are either nonconvex or already exact in the master)

Facility  Cost  Alpha  Active  Capacity
------------------------------------------
    1      5.0  0.30   Yes      5.265
    2      8.0  0.25   No       0.000
    3      6.0  0.35   No      -0.000
    4      7.0  0.28   No       0.000
    5      4.0  0.32   Yes      4.735

Total capacity: 10.000 (demand: 10.0)

Nonconvex Problems: Heuristic Mode#

For nonconvex MINLPs, NLP-BB can still find good feasible solutions quickly, but the optimality gap cannot be certified because the NLP objective is not a valid lower bound. The solver sets gap_certified=False and logs a warning.

By default, nonconvex problems use spatial B&B (with McCormick relaxations for certified bounds). You must explicitly request nlp_bb=True to use NLP-BB on nonconvex problems.

m = dm.Model("nonconvex_minlp")
x = m.continuous("x", lb=-5, ub=5)
y = m.binary("y")

m.minimize(dm.sin(x) + 2 * y)
m.subject_to(x + y >= 0.5)

# Default: spatial B&B for nonconvex
result_default = m.solve()
print(
    f"Default solver:  nlp_bb={result_default.nlp_bb}, gap_certified={result_default.gap_certified}"
)

# Forced NLP-BB: heuristic mode
result_heuristic = m.solve(nlp_bb=True)
print(
    f"Forced NLP-BB:   nlp_bb={result_heuristic.nlp_bb}, "
    f"gap_certified={result_heuristic.gap_certified}"
)
print(f"Objective:       {result_heuristic.objective:.4f}")

NLP-BB on nonconvex model: running in heuristic mode (gap not certified). Pass skip_convex_check=True to suppress.

No valid dual bound was produced for model 'nonconvex_minlp': the relaxation layer could not bound this objective (status=feasible). The result cannot be certified globally optimal. A nonlinear term with no envelope is the usual cause; an epigraph reformulation (minimize z subject to f(x) <= z) often gives the relaxation something to bound.

Default solver:  nlp_bb=False, gap_certified=True
Forced NLP-BB:   nlp_bb=True, gap_certified=False
Objective:       -1.0000

Summary#

nlp_bb

Convex nonlinear MINLP

MILP / MIQP

Nonconvex MINLP

None (default)

Auto-selects NLP-BB

Specialized solver (HiGHS, QP-BB)

Spatial B&B

True

NLP-BB, certified gap

NLP-BB (bypasses fast path)

NLP-BB heuristic, gap not certified

False

Spatial B&B

Specialized solver

Spatial B&B

On CPU, NLP-BB and spatial B&B perform similarly on convex MINLPs because spatial B&B already skips relaxation overhead for convex models. NLP-BB provides a cleaner code path and is positioned for future GPU batch scaling, where the streamlined loop with fewer synchronization points will be advantageous [Kröger et al., 2018].