An Exact Approach for the Train Single-Routing Selection Problem
A.L. Croella, F. Furini, I. Ljubic, B. Pascariu, P. Pellegrini, P. San Segundo
European Journal of Operational Research, 2026 · in corso di stampa
Given a set of train routes with route costs and a set of compatible route pairs with pairing costs, the Train Single-Routing Selection Problem (TSRSP) seeks to assign one route to each train, minimizing the total cost while ensuring pairwise compatibility among the selected routes. This problem is of significant practical relevance in rail traffic management and it is a special case of the Train Routing Selection Problem. We introduce a Binary Quadratic Programming formulation for the TSRSP and apply a linearization technique from the literature that requires a linear number of additional variables and constraints. This yields a novel and effective Mixed Integer Linear Programming (MILP) formulation for the TSRSP. By exploiting the structure of the problem, we further propose a method to strengthen the Linear Programming (LP) relaxation of the MILP formulation, substantially improving its computational performance. The resulting formulation is the first to efficiently solve real-world TSRSP instances to optimality within short computational times—instances that, until now, have only been addressed using heuristic approaches in the literature. Extensive computational results show that our MILP model consistently outperforms existing formulations, both in terms of computational time and the number of instances solved to optimality, primarily due to the strength of its LP relaxation.
Exact Algorithms for Two-Dimensional Knapsack Problems: A Unified Framework with New Benchmark Results
S. Wang, R. Baldacci, F. Furini, L. Wei, Q. Liu
INFORMS Journal on Computing, 2026 · in corso di stampa
This paper investigates two-dimensional knapsack problems modeled as a Generalized Two-Dimensional Knapsack Problem, which has not been studied previously in the literature and whose importance arises in designing Branch-Price-and-Cut (BPC) algorithms for the classic Two-Dimensional Bin-Packing Problem. We propose a novel exact solution framework and design both non-numerically exact and numerically exact algorithms tailored to the, which effectively solve the generated problem instances. The proposed framework demonstrates state-of-the-art performance on the well-known Two-Dimensional Knapsack Problem with and without item conflicts and on the basic Two-Dimensional Orthogonal Packing Problem, solving several previously unsolved instances and providing new benchmark results. These findings demonstrate the framework's potential for inspiring algorithm development for higher-dimensional problems and pricing algorithms in other related BPC techniques. To facilitate these interesting future research directions, the algorithm code, instance data, and detailed results are made openly accessible.
Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem
F. Ciccarelli, V. Dose, F. Furini, M. Monaci
Discrete Applied Mathematics, 2026 · in corso di stampa
We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds.
Integer linear programming formulations for the maximum flow blocker problem
I. Bentoumi, F. Furini, A.R. Mahjoub, S. Martin
European Journal of Operational Research, 2025
Given a network with capacities and blocker costs associated with its arcs, we study the maximum flow blocker problem (FB). This problem seeks to identify a minimum-cost subset of arcs to be removed from the network, ensuring that the maximum flow value from the source to the destination in the remaining network does not exceed a specified threshold. The FB finds applications in telecommunication networks and monitoring of civil infrastructures, among other domains. We undertake a comprehensive study of several new integer linear programming (ILP) formulations designed for the FB. The first type of model, featuring an exponential number of constraints, is solved through tailored Branch-and-Cut algorithms. In contrast, the second type of ILP model, with a polynomial number of variables and constraints, is solved using a state-of-the-art ILP solver. The latter formulation establishes a structural connection between the FB and the maximum flow interdiction problem (FI), introducing a novel approach to obtaining solutions for each problem from the other. blackThe ILP formulations proposed for solving the FB are evaluated thanks to a theoretical analysis assessing the strength of their LP relaxations. Additionally, the exact methods presented in this paper undergo a thorough comparison through an extensive computational campaign involving a set of real-world and synthetic instances. Our tests aim to evaluate the performance of the exact algorithms and identify the features of instances that can be solved with proven optimality.
A Numerically Exact Algorithm for the Bin-Packing Problem
R. Baldacci, S. Coniglio, F. Furini
INFORMS Journal on Computing, 2024
We propose a numerically exact algorithm for solving the Bin-Packing Problem (BPP) based on a branch-price-and-cut framework combined with a pattern-enumeration method. Key to the algorithm is a novel technique for the computation of numerically safe dual bounds for the widely adopted set covering reformulation of the BPP (tightened with additional valid inequalities) with a precision that is higher than the one of general-purpose floating-point solvers. Our branch-price-and-cut algorithm also relies on an exact integer (fixed-point) label setting algorithm for solving the pricing problem associated with the tightened set-covering formulation. To the best of our knowledge, ours is the first algorithm for the BPP that is numerically exact and practical for solving large-scale instances. Extensive computational results on instances affected by notorious numerical difficulties (those of the Augmented Non-IRUP class) show that our exact algorithm outperforms all of the not numerically exact state-of-the-art algorithms based on branch-and-cut-and-price techniques that rely on a set-covering formulation of the BPP.
