Branch-and-Bound – Optimization Online

A branch-and-bound algorithm for the computation of optimal point mappings of parametric optimization problems

Published: 2026/09/22

We propose a novel branch‑and‑bound algorithm that constructs rigorous outer approximations of the optimal point mapping for parametric optimization problems with guaranteed feasibility and optimality tolerances. The method uses the improvement‑function reformulation to define discarding and inclusion tests on sub-boxes, constructing a rigorous outer approximation. Under the same regularity conditions that ensure exactness of this … Read more

On Spanning-Tree Integrality and a new Branching Rule for the Maximum Cut Problem

Published: 2026/09/17

Combinatorial Optimization, Integer Programming, Semi-definite Programming binary quadratic programming, Branch-and-Bound, combinatorial optimization, integer programming, Maximum Cut Problem, QUBO, semidefinite programming

State-of-the-art exact methods for the Maximum Cut problem are based on solving linear and semidefinite programming relaxations embedded into a branch-and-bound algorithm. For linear programming formulations, it was shown recently that it is thereby sufficient to enforce the integrality of the variables associated with the edges of a spanning tree. Our first contribution is to … Read more

Disjunctive Sum of Squares

Published: 2026/05/30

Cone Programming, Convex Optimization, Semi-definite Programming Branch-and-Bound, conic optimization, convex optimization, copositive programming, polynomial optimization, semidefinite programming, sum of squares, sum of squares optimization

We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more

Objective Domain Reduction for Enhancing Solver Performance on Challenging Integer Programs

Published: 2026/05/29, Updated: 2026/07/01

Combinatorial Optimization, Integer Programming, Transportation Binary Search, Branch-and-Bound, Domain-Reduced Reformulation, integer program, Objective domain reduction

In this study, we explore how the domain of objective function values for challenging integer programs can be reduced and whether such a reduction can improve the solution process. Our work is motivated by binary search, a technique that efficiently narrows a search space by repeatedly halving it through feasibility checks. Building on this idea, … Read more

A Binary Search-Based Criterion Space Algorithm for Solving Bi-Objective Integer Programs: The Quadtree Search Method

Published: 2026/05/07

Integer Programming, Multi-Criteria Optimization approximation, Bi-Objective Integer Programming, Binary Search, Branch-and-Bound, Criterion Space Search Method

We propose an exact binary search-based branch-and-bound algorithm, termed the Quadtree Search Method, for solving bi-objective integer programs. The existing literature on criterion space search methods for multi-objective optimization predominantly assumes that subproblems can be solved to optimality, an assumption that becomes computationally prohibitive for hard instances. In contrast, our approach departs from this assumption … Read more

Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements

Published: 2026/04/14, Updated: 2026/09/10

(Mixed) Integer Nonlinear Programming, Statistics Branch-and-Bound, hyperplane arrangements, Mixed-integer nonlinear optimization, robust statistics

We study computational aspects of a key problem in robust statistics—the penalized least trimmed squares (LTS) regression problem, a robust estimator that mitigates the influence of outliers in data by capping residuals with large magnitudes. Although statistically attractive, penalized LTS is NP-hard, and existing mixed-integer optimization (MIO) formulations scale poorly due to weak relaxations and … Read more

Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching

Published: 2026/04/06

(Mixed) Integer Linear Programming, Branch and Cut Algorithms Branch-and-Bound, machine learning, mixed-integer programming

Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typically with GPU parallelization. In this work, we take a different path by developing interpretable models that are … Read more

Beyond binarity: Semidefinite programming for ternary quadratic problems

Published: 2026/03/30

(Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Branch-and-Bound, integer semidefinite programming, quadratic ratio problems, ternary optimization problem

We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation … Read more

K-adaptability for two-stage stochastic optimization

Published: 2025/11/21

Global Optimization, Stochastic Programming Branch-and-Bound, k-adaptability, two-stage stochastic programming

ArticleDownload View PDF

A Combinatorial Branch-and-Bound Algorithm for the Capacitated Facility Location Problem under Strict Customer Preferences

Published: 2025/11/11

Bilevel Optimization, Branch and Cut Algorithms, Combinatorial Optimization Branch-and-Bound, computational optimisation, customer preferences, facility location, healthcare optimisation

This work proposes a combinatorial branch-and-bound (B&B) algorithm for the capacitated facility location problem under strict customer preferences (CFLP-SCP). We use combinatorial insights into the problem structure to do preprocessing, model branching implications, enforce feasibility or prove infeasibility in each node, select variables and derive primal and dual bounds in each node of the B&B … Read more