This paper introduces weighted-BMP, a variant of the Bandwidth Minimization Problem (BMP), with a significant application in optimizing quantum emulation. Weighted-BMP optimizes particles ordering to reduce the emulation costs, by designing a particle interaction matrix where strong interactions are placed as close as possible to the diagonal. We formulate the problem using a Mixed Integer Linear Program (MILP) and solve it to optimality with a state-of-the-art solver. To strengthen our MILP model, we introduce symmetry-breaking inequalities and establish a lower bound. Through extensive numerical analysis, we examine the impacts of these enhancements on the solver’s performance. The introduced reinforcements result in an average CPU time reduction of 25.61%. Additionally, we conduct quantum emulations of realistic instances. Our numerical tests show that the weighted-BMP approach outperforms the Reverse Cuthill-McKee (RCM) algorithm—an efficient heuristic used for site ordering tasks in quantum emulation— achieving an average memory storage reduction of 24.48%. From an application standpoint, this study is the first to apply an exact optimization method, weighted-BMP, that considers interactions for site ordering in quantum emulation pre-processing, and shows its crucial role in cost reduction. From an algorithmic perspective, it contributes by introducing important reinforcements and lays the groundwork for future research on further enhancements, particularly on strengthening the weak linear relaxation of the MILP.

This paper presents a study of the optimal Admission Control in Damper-based Networks (ACDN) problem. The use of dampers in large-scale networks is becoming increasingly beneficial for a wide range of applications as it provides a reliable means of achieving deterministic delay guarantees without the need for synchronization between routers. In this context, optimal admission control solutions are required to fully utilize capacity. The problem being studied is a variant of the Unsplittable Multi-Commodity Flow (UMCF) problem, with additional constraints related to forwarding and shaping. This paper proposes two Integer Linear Programming (ILP) formulations to address the ACDN problem. The former is a compact formulation, which is solved using the CPLEX solver. The latter is an extended path formulation, for which a Branch-and-Price algorithm is developed, including a column generation procedure, an efficient branching scheme, and reinforced by a primal heuristic. Tests on realistic instances show that solving the path formulation using the Branch-and-Price algorithm is better than solving the compact formulation using CPLEX. Our algorithm divides by 14 the average running time given by CPLEX, and the path formulation gives a stronger linear relaxation with an average optimally gap of 0.3%. This work builds upon previous research [1] that developed a heuristic for finding near-optimal solutions, and instead aims to find exact optimal solutions for ACDN.

With 5G networking, deterministic guarantees are emerging as a key enabler. In this context, we present a scalable Damper-based architecture for Large-scale Deterministic IP Networks (D-LDN) that meets required bounds on end-to-end delay and jitter. This work extends the original LDN [1] architecture, where flows are shaped at ingress gateways and scheduled for transmission at each link using an asynchronous and cyclic opening of gate-controlled queues. To further relax the need for clock synchronization between devices, we use dampers, that consist in jitter regulators, to control the burstiness flows to provide a constant target delay at each hop. We introduce in details how data plane functionalities are implemented at all nodes (gateways and core) and we derive how the end-to-end delay and jitter are calculated. For the control plane, we propose a column generation algorithm to quickly take admission control decisions and maximize the accepted throughput. For a set of flows, it determines acceptance and selects the best shaping and routing policy. Through a proof-of-concept implementation in simulation, we verify that the architecture meets promised guarantees and that the control plane can operate efficiently at large-scale.