Introduction
Combinatorial optimisation is a fundamental field in applied mathematics and computer science that focuses on finding an optimal object from a finite set of objects. In this context, problems are typically characterised by discrete variables and complex constraints, with many of these problems being NP‐hard—indicating that, in general, no efficient solution method is known to exist for the worst-case scenarios.
Examples include determining optimal network configurations, scheduling, resource allocation, and various spanning tree problems, where conflict constraints or additional criteria further complicate the solution landscape.
To address these challenges, researchers have developed a wide array of algorithms ranging from exact methods, such as mixed integer linear programming formulations, to heuristic and metaheuristic methods, which aim to obtain near-optimal solutions within reasonable computational times.
The integration of multiple criteria, as well as the treatment of additional conflicts and precedence relations, has led to versatile and robust algorithmic frameworks with applications in logistics, telecommunications, and bioinformatics.
Research from Nature Portfolio
No recent Nature Portfolio content available
Research from All Publishers
Recent developments in combinatorial optimisation have seen the advent of advanced metaheuristic approaches and bi-criteria models that tackle problems with intricate conflict constraints.
Examples of Recent Research Approaches
- Minimum Conflict Weighted Spanning Tree Problem
A two-phase metaheuristic method has been successfully employed by initially focusing on reducing conflict pairs and subsequently refining the cost optimisation [1]. - Set Covering Problems with Conflict Constraints
Novel bi-criteria strategies have been introduced where the simultaneous goals of maximising coverage and minimising resource selection are balanced through integer programming models and epsilon-constraint methods [2]. - Precedence-Constrained Arborescences
Research has provided scalable mixed integer linear programming formulations, offering a new perspective on problems where ordering relationships must be preserved, thereby extending classical spanning tree challenges into more complex network design scenarios [3].
These emerging trends illustrate the dynamic and interdisciplinary nature of research in combinatorial optimisation, which continuously integrates advanced mathematical programming techniques and innovative search strategies.
Technical Terms
- NP‐hard: A classification for problems for which no polynomial-time solution method is known, implying that solving large instances exactly is computationally intractable.
- Metaheuristic: A high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimisation methods, particularly useful for complex problems where exact methods fail.
- Mixed Integer Linear Programming (MILP): A mathematical optimisation technique where some variables are constrained to be integers, used extensively in modelling combinatorial optimisation problems.
- Conflict Constraints: Restrictions that prevent certain combinations of elements (such as edges in a graph) from appearing simultaneously in a solution, commonly used to model incompatibilities in network design problems.
Combinatorial Optimization Problems and Algorithms Publication Trend
The graph below shows the total number of publications each year in Combinatorial Optimization Problems and Algorithms.
