Main Free Edition Commercial Edition Docs FAQ Forum About Us

Mixed-integer nonlinear programming

ALGLIB provides two parallel mixed-integer nonlinear programming (MINLP) solvers: BBSYNC, a branch-and-bound method for models with analytic derivatives and relaxable integer variables, and MIVNS (variable-neighborhood search with surrogate models) for derivative-free problems with non-relaxable integer variables and expensive objectives/constraints.

Both solvers support box, linear, and nonlinear constraints in convex or nonconvex settings. Free (fully functional, no limits on problem size) and commercial cross-platform implementations are available for C++, C#, Java, Python, and Delphi.

See also: NLP • DFO • Global optimization

MINLP overview

MINLP solvers

The ALGLIB MINLP solver suite includes two solvers, each designed for a different class of problems: BBSYNC and MIVNS. Both solvers are available under free and commercial licensing:

• BBSYNC is an NLP-based branch-and-bound solver with deterministic behavior in parallel mode. It supports both convex and non-convex MINLP problems with analytic derivatives. BBSYNC requires integer variables to be relaxable - that is, even when an integer solution is required, it is still must be possible to compute objective, constraints and their gradients at fractional points.
• MIVNS is an unique algorithm developed by the ALGLIB Project for derivative-free MINLP problems with non-relaxable integer variables and/or expensive objectives/constraints. It combines variable-neighborhood search over integer grid with fast local searches using surrogate models in continuous subspaces corresponding to a fixed assignment of integer variables. This solver is particularly effective for challenging industrial optimization tasks involving long-running simulations or real-world measurements.

Convex vs non-convex

Both BBSYNC and MIVNS can handle convex and nonconvex problems, but they approach nonconvexity in different ways. BBSYNC deals with nonconvexity by performing multiple restarts from quasi-random points, while MIVNS makes no convexity assumptions when exploring the grid of integer feasible points.

Parallelism

The commercial edition of ALGLIB includes multithreading support. Both BBSYNC and MIVNS have the batchsize parameter that tell the solver to simultaneously process several subproblems, if possible. Depending on the parallelism settings, you can parallelize internal solver calculations, objective/constraints evaluations (if your callback is thread-safe) or both. Note that parallelism characteristics differ between solvers (see details below).

Solvers: detailed overview

BBSYNC solver

The BBSYNC algorithm is an NLP-based branch-and-bound algorithm for nonlinear optimization. The basic idea is straightforward: at each node of the branch-and-bound tree, solve a relaxed continuous subproblem. If any integer variable is fractional, generate two subproblems by rounding it up and down, then insert them into the tree.

What makes BBSYNC a high-performance solver is the way this idea is implemented:

• up to batchsize of the best nodes are selected and processed in the parallel manner
• a limited depth-first search is performed to quickly generate integer feasible candidates
• rounding heuristics are applied at nodes
• special measures ensure deterministic behavior even in parallel mode
• non-convex problems are addressed by performing multiple restarts from quasi-random points and by using spatial splits

BBSYNC is gradient-based (internally it uses a filter SQP method) and requires user-supplied gradients. It expects the objective and constraints to be smooth. Additionally, integer variables must be relaxable, i.e. it must be possible to compute objective/constraints at fractional points.

The solver scales well with the number of variables - the cost of one iteration is comparable to that of a sparse SQP method. Obviously, larger MINLP problems need more iterations and more time, but the number of continuous variables alone is not a limiting factor as long as the number of integer variables (and thus the branch-and-bound tree size) is manageable. BBSYNC has successfully solved problems with more than 100,000 continuous variables.

Convex/nonconvex problems. BBSYNC is designed to handle both convex and nonconvex problems. For mixed integer problems with convex objective and constraints, it can guarantee finding a global solution, thanks to properties of convex optimization.

In contrast, for nonconvex problems the solver may get stuck in a local solution and miss the global optimum. BBSYNC deals with nonconvexity by making multiple restarts from quasi-random points (this option is configured with the minlpsolversetmultistarts function).

Parallelism. BBSYNC parallelism is controlled by the batchsize parameter. Up to batchsize of the most promising subproblems can be selected from the tree and processed simultaneously. Depending on the parallelism settings, it is possible to parallelize internal computations (SQP steps), objective/constraints evaluations (callback parallelism) or both. If a single iteration (callback+SQP) takes longer than ~1ms, at least one of these phases is long enough to offset multithreading overhead.

Parallel scaling depends strongly on problem properties, specifically on the BB tree shape. Difficult problems with many independent branches scale well with the number of cores, since it is usually possible to find batchsize unprocessed nodes to solve in parallel. By contrast, simpler problems that require only a few variable splits often produce nearly-linear trees that can be traversed only sequentially.

When not to use BBSYNC. First, when integer variables are non-relaxable (a common limitation of all BB methods). Second, when objectives or constraints are very costly to evaluate and the computational budget is limited. Branch-and-bound is designed to raise the dual bound (the lower estimate from integer infeasible relaxations) as quickly as possible, not to steadily improve the primal bound (the best feasible solution). As a result, branch-and-bound methods are generally unsuited for early stopping - it is likely to produce no feasible solution at all.

The MIVNS solver (see below) is designed to overcome both of these limitations.

MIVNS solver

MIVNS (Mixed-Integer Variable Neighborhood search with Surrogates) is a unique algorithm developed by the ALGLIB Project for derivative-free MINLP problems with non-relaxable integer variables and expensive objectives/constraints. It builds on our earlier work on surrogate model optimization for continuous problems.

The solver performs a variable-neighborhood search over the integer grid, evaluating only integer-feasible assignments of discrete variables. For each fixed assignment of integer variables, the corresponding continuous subspace is explored using fast local searches with surrogate RBF models. This approach makes highly efficient use of limited computational budgets, making MIVNS particularly valuable for challenging industrial problems such as those involving long-running simulations or physical measurements.

Unlike B&B-based solvers, MIVNS respects integrality of variables at all trial points and respects linear constraints over integral variables (e.g. one-hot encoding constraints, permutation-like or cardinality-like constraints, etc). It means that the solver will evaluate objective/constraints only at meaningful points (true one-hot, valid permutation, valid cardinality) and won't ask your simulation software to compute something impossible, like simulating a "2.58-stage" rocket.

MIVNS incorporates several heuristics to improve performance under limited budgets:

• careful balance between exploration (neighborhood scanning) and exploitation (improving incumbent points)
• steady progress towards feasibility and optimality
• Batch processing with deterministic parallelization: up to batchsize best candidates are evaluated in parallel using a stable, reproducible tie-break
• caching and reusing previously computed points to reduce redundant evaluations

Problem sizes and running time. MIVNS is intended for moderate-sized problems with up to several tens of integer variables. The number of continuous variables can be larger; problems with up to one hundred continuous variables are feasible.

Keep in mind that in a derivative-free setting, achieving progress comparable to a single gradient-based step typically requires O(N) objective evaluations. Surrogate models substantially reduce the constant hidden behind the big-O notation, but the solver's computational budget still needs to scale with the product of N_int (integer variables) and N_frac (continuous variables).

Robustness. The solver is designed to handle models where changes in integer variables cause structural changes in the system. If your model has if/then/else switches that depend on integer variables (rewiring constraints, enabling or disabling variables, or switching entire subsystems on/off), MIVNS can optimize it correctly.

Convex/nonconvex problems. MIVNS makes no convexity assumptions when exploring the grid of integer feasible points. Multiple local extrema make it harder to reach the global optimum, but nonconvexity of an integer-only problem does not break the algorithm. Mixed problems with both integer and continuous variables are different: surrogate searches in continuous subspaces may converge to local extrema rather than global ones. However, much of the nonconvexity is often factored out due to integer variables being fixed during local searches.

Parallelism. MIVNS solver can simultaneously process up to batchsize nodes (a user-controlled parameter) from the current neighborhood. Depending on parallelism settings, it can parallelize internal computations (surrogate model optimization), objective/constraints evaluations (callback parallelism; needs thread-safe callbacks) or both. If one node (callback+internals) takes longer than 1ms, at least one of these phases is long enough to pay off multithreading overhead. Large batches may allow you to parallelize even sub-millisecond tasks.

MIVNS generally scales well with the cores count. Up to 2N_int neighbors of a central node are already there, and the solver can expand the neighborhood proactively if some cores are idle.

Early progress. Unlike branch-and-bound, MIVNS is designed to deliver good feasible solutions quickly and then keep improving them as time allows. If you have a tight wall-clock budget, MIVNS is usually the safer first choice.

When not to use the solver. If your problem has relaxable integers and inexpensive analytic derivatives, BBSYNC is a better fit. If the number of discrete variables is very large (hundreds+), the MIVNS may have hard time navigating the integer grid. Each neighborhood expansion involves solving up to 2N_int MIQP subproblems to identify nearest nodes, so this step may become costly when N_int is large. Finally, if you require hard optimality gaps rather than "best-found" solutions, prefer a branch-and-bound workflow.

Docs and examples

BBSYNC and MIVNS solvers are provided in the minlpsolvers subpackage of the MINLP package (the link opens the Reference Manual for your chosen programming language).

The Reference Manual includes a complete description of the current API and two examples: minlp_bnb_dfo (using BBSYNC and MIVNS to solve a toy MINLP problem) and minlp_expensive_dfo (solving a simulation-based MINLP problem with MIVNS).

We also provide two online articles (see below) that discuss these examples and offers deeper insights and guidance beyond the raw code.

CPU cluster: MINLP with analytic derivatives

The CPU cluster article shows how ALGLIB's branch-and-bound BBSYNC algorithm can be applied to a toy MINLP problem: composing a cluster of identical commodity-grade CPUs with the minimal total cost of ownership subject to minimal compute throughput and maximum power consumption constraints. For realism, it uses power consumption and compute throughput data for a real-world quad-core Cortex-A57 CPU.

Rocket: simulation-based derivative-free MINLP

The Rocket article demonstrates how ALGLIB's MIVNS algorithm can be applied to a toy derivative-free, simulation-based MINLP problem: designing a minimal-cost rocket capable of delivering a small payload to low Earth orbit. The objective is to minimize cost while ensuring the burnout velocity reaches at least 7.8 km/s. Solving this problem requires running multiple flight simulations for different designs and fuel loads.

ALGLIB® - numerical analysis library, 1999-2025.
ALGLIB is a registered trademark of the ALGLIB Project.
Policies for this site: privacy policy, trademark policy.