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:

Simpler code path: no relaxation infrastructure setup for convex MINLPs.
GPU scaling (future): the streamlined loop has fewer synchronization points for batch vmap solving.
No MIP solver dependency: useful in deployment environments without HiGHS.

discopt auto-selects NLP-BB for convex nonlinear MINLPs. For MILP and MIQP problems, specialized solvers (HiGHS, QP-BB) are faster and take priority. You can override with nlp_bb=True or nlp_bb=False.

import os

os.environ["JAX_PLATFORMS"] = "cpu"
os.environ["JAX_ENABLE_X64"] = "1"

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 a convex nonlinear MINLP automatically selects NLP-BB. The nlp_bb flag on the result confirms which solver mode was used.

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"Wall time:     {result.wall_time:.3f}s")

******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
 Ipopt is released as open source code under the Eclipse Public License (EPL).
         For more information visit https://github.com/coin-or/Ipopt
******************************************************************************

Status:        optimal
Objective:     21.4029
Gap:           0.0
NLP-BB used:   True
Gap certified: True
Nodes:         43
Wall time:     9.783s

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].

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} {rn.gap:>12.2e} {rs.gap:>12.2e}")
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}")

Metric                   NLP-BB  Spatial B&B
--------------------------------------------
Objective               21.4029      21.4029
Gap                    0.00e+00     0.00e+00
Nodes                        43           41
Wall time (s)             6.979        7.122
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})")

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.

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].