ABSTRACT The purpose of this work is to develop an algorithmic optimization approach for a capacitated multi‐commodity flow problem, where the objective is to minimize the total link costs, where the cost of each arc increases convexly with its utilization. This objective is particularly relevant in telecommunication networks, where device performance can deteriorate significantly as the available bandwidth on a link becomes limited. By optimizing this convex function, traffic is efficiently distributed across the network, ensuring optimal use of available resources and preserving capacity for future demands. This paper describes the convex multi‐commodity flow problem and presents methodologies to solve both its Splittable and Unsplittable variants. In the Splittable version, flows can be fractionally distributed across multiple paths, while in the Unsplittable version, each commodity must be routed through a single path. Our approach employs Column‐Generation techniques to address the convexly increasing cost functions associated with arc utilization, effectively accommodating various forms of convex increasing cost functions, including non‐differentiable or black‐box convex increasing functions. The proposed methods demonstrate strong computational efficiency, offering a robust framework for managing network flows in complex telecommunication environments.

Solving the multi-commodity flow problem in large networks is the core of current telecommunication networks. Integer linear programming shows its ability to solve this problem efficiently in large networks by using decomposition techniques such as the Dantzig-Wolfe method to obtain a model based on path variables. Thanks to the sparsity of telecommunication networks, the path model can solve large-scale instances through a small mathematical model. This paper proposes a spatial decomposition derived from the Dantzig-Wolfe decomposition method. The goal is to split the network into several areas and treat each one independently. Column generation is used to find a routing consensus between areas. We show the gain in terms of linear relaxation and computational time using spatial decomposition on the well-known IPRAN network structure.

The Interior Gateway Protocol (IGP) weight design problem is a critical aspect of network optimization, aimed at determining the optimal set of weights assigned to the links in a network to achieve the desired performance objectives. This problem is essential to ensure efficient routing, minimize congestion, and improve overall network reliability. The IGP weight design problem involves complex mathematical modeling and algorithmic approaches to balance multiple factors such as traffic demands, link capacities, and network topology. Effective solutions to this problem can cause confusion among the maintenance team or network managers. One way to tackle this drawback is to find explainable optimization algorithms which aim to enhance the transparency and interpretability of optimization processes. Traditional optimization algorithms often operate as black-box models, providing solutions without insight into their decision-making processes. The goal is to bridge the gap between complex algorithmic operations and human interpretability, thus facilitating better decision-making and trust in automated systems. We propose a way to consider interpretability as an input of the optimization algorithm. The main goal is to compare the optimality loss provided by the interpretability requirement and provide efficient methods to solve the explainable IGP weight design problem. An Integer Linear Program and a local search algorithm are presented and compared with the original problem. An automatic analysis of the solution is proposed to help the maintenance team or network managers.

We propose and analyze a new policy gradient algorithm for reinforcement learning (RL), relative Monte Carlo (rMC). The method estimates policy gradients using relative returns between a root sample path and counterfactual simulated paths, instantiated by taking a different action from the root. The resulting gradient estimate is both unbiased and has low variance. rMC is compatible with any differentiable policy, including neural networks, and is guaranteed to converge even for infinite horizon tasks. The method utilizes common random number coupling of the simulated paths to reduce variance and increase the likelihood that paths merge, thereby reducing simulation complexity. It is particularly well suited to discrete event control problems where actions have a "local" effect, such as queueing, supply chain, or ride-hailing problems. Indeed, we show that it has provably low complexity for a family of inventory control problems. Numerical tests on a challenging inventory and fulfillment problem show that compared to traditional RL approaches, rMC converges in far fewer iterations (lower variance), has better policy performance (unbiased), and requires minimal hyperparameter tuning.

ABSTRACT In real‐life applications, most optimization problems are variants of well‐known combinatorial optimization problems, including additional constraints to fit with a particular use case. Usually, efficient algorithms to handle a restricted subset of these additional constraints already exist or can be easily derived, but combining them together is difficult. The goal of our paper is to provide a framework that allows merging several so‐called atomic algorithms to solve an optimization problem, including all associated additional constraints together. The core proposal, referred to as Atomic Column Generation (ACG) and derived from Dantzig–Wolfe decomposition, allows converging to an optimal global solution with any kind of atomic algorithms. We show that this decomposition improves the continuous relaxation and describe the associated Branch‐and‐Price algorithm. We consider a specific use case in telecommunication networks where several Path Computation Elements (PCE) are combined as atomic algorithms to route traffic. We demonstrate the efficiency of ACG on the resource‐constrained shortest path problem associated with each PCE and show that it remains competitive with benchmark algorithms.

Traffic Engineering (TE) represents one of the most essential tools in modern telecommunication networks. The rapid growth of exchanged traffic has required tackling a known NP-hard problem called the Multi-Commodity Flow problem (MCF). Many studies in the literature have already considered different variants of this problem. In this paper, we propose a new way to use a double Dantzig-Wolfe decomposition formulation to improve the quality of the linear relaxation. We apply our method on the classical multi-commodity flow problem where the throughput acceptance is first maximized and then the routing cost is minimized. We provide a computational experiment and conduct an in-depth analysis of the algorithm based on realistic instances.

In backbone networks, it is fundamental to quickly protect traffic against any unexpected event, such as failures or congestions, which may impact Quality of Service (QoS). Standard solutions based on Segment Routing (SR), such as Topology-Independent Loop-Free Alternate (TI-LFA), are used in practice to handle failures, but no distributed solutions exist for distributed and tactical congestion mitigation. A promising approach leveraging SR has been recently proposed to quickly steer traffic away from congested links over alternative paths. As the pre-computation of alternative paths plays a paramount role to efficiently mitigating congestions, we investigate the associated path computation problem aiming at maximizing the amount of traffic that can be rerouted as well as the resilience against any 1-link failure. In particular, we focus on two variants of this problem. First, we maximize the residual flow after all possible failures. We show that the problem is NP-Hard, and we solve it via a Benders decomposition algorithm. Then, to provide a practical and scalable solution, we solve a relaxed variant problem, that maximizes, instead of flow, the number of surviving alternative paths after all possible failures. We provide a polynomial algorithm. Through numerical experiments, we compare the two variants and show that they allow to increase the amount of rerouted traffic and the resiliency of the network after any 1-link failure.

Various routing protocols are deployed to operate networks, and border routers manage the exchange of routing information. Network engineers carefully configure routing policies to ensure reliable, efficient, and secure connectivity. However, the complexity of these configurations can lead to errors and issues like routing loops. Existing control plane verification solutions offer comprehensive analysis but struggle with scalability. This demonstration presents a scalable verification tool capable of locating routing loops in large multi-protocol and multi-instance networks, demonstrating its efficiency and performance with numerical results and live verification.

Multi-topology routing (MTR) provides an attractive alternative to segment routing for traffic engineering when network devices cannot be upgraded. However, due to a high overhead in terms of link state messages exchanged by topologies and the need to frequently update link weights to follow evolving network conditions, MTR is often limited to a small number of topologies and the satisfaction of loose QoS constraints. To overcome these limitations we propose vMTR, an MTR extension where demands are routed over virtual topologies that are silent, i.e., they do not exchange LSA messages, and that are continuously derived from a very limited set of real topologies, optimizing each a QoS parameter. In this context, we present a polynomial and exact algorithm for vMTR and, as a benchmark, a local search algorithm for MTR. We show that vMTR helps reducing drastically the number of real topologies and that it is more robust to QoS changes.

When working with generative artificial intelligence (AI), users may see productivity gains, but content generated with the help of AI may not match their preferences exactly. The boost in productivity may come at the expense of users' idiosyncrasies, such as personal style and tastes, preferences we would naturally express without AI. To let users express their preferences, many AI systems let users edit their prompt (e.g., Midjourney) or allow more natural interactions (e.g., ChatGPT), and users can always review and edit the AI-generated output themselves. However, aligning a user's intentions with an AI's output can take time and may not always be worth it if the AI's first or default output "does the job." In short, users face a trade-off between AI output fidelity and communication cost. The purpose of this work is to examine the impact of this human-AI interaction on the AI-generated content we produce as a society.

In collaboration with the San Francisco Unified School District (SFUSD), this paper introduces an interactive optimization framework to tackle complex school scheduling challenges. The choice of school start and end times is an optimization challenge, as schedules influence the district's transportation system, and limiting the associated costs is a computationally difficult combinatorial problem. However, it is also a policy challenge, as transportation costs are far from the only consequence of school schedule changes. Policymakers need time and knowledge to balance these considerations and reach a consensus carefully; past implementations have failed because of policy issues despite state-of-the-art optimization approaches.

We propose a constraint programming (CP)–based branch-and-price-and-cut framework to exactly solve bipath multicommodity flow (MCF): an MCF problem with two paths for each demand. The goal is to route demands in a capacitated network under the minimum cost. The two paths must have disjoint arcs, and the delays accumulated along the two paths must be within a small deviation of each other. CP is used at multiple points in this framework: for solving pricing problems, for cut generation, and for primal and branching node heuristics. These modules use a CP solver designed for network routing problems and can be adapted to other combinatorial optimization problems. We also develop a novel, complete, two-level branching scheme. On a set of diverse bipath MCF instances, experimental results show that our algorithm significantly outperforms monolithic CP and mixed integer linear programming models and demonstrate the efficiency and flexibility brought by the tailored integration of linear programming and CP methodologies. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada; Huawei Technologies. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0128 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0128 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

With the advent of big data applications, coflow scheduling has become a cornerstone for the engineering of traffic in datacenters. Minimizing the average weighted Coflow Completion Times (CCT) is a crucial step to minimize the execution time of jobs running in distributed computing frameworks. In this paper, we present a new$\sigma $-order coflow scheduling solution, ONE-PARIS, an online semi-clairvoyant and semi-distributed implementation suitable to minimize the weighted CCT in production environments. We achieves this through ONE-PARIS scheduler for ordering coflows and a decentralized resource allocation mechanism, called Sync-Rate, enabling to respect the order of priority of coflows provided by ONE-PARIS and ensuring efficient synchronization between flows of the same coflow in order to free up bandwidth for low-priority flows. Extensive simulations on both synthetic and real traffics show that our proposed coflow scheduler outperforms other state-of-art schemes.

Tactical Traffic Engineering (TE) solutions are a must to adapt traffic steering when unexpected congestions occur. While already available, centralized solutions to locally optimizes congested tunnels and links suffer from a slow reaction time of several minutes. To address this issue, we propose a distributed Congestion Mitigation (CM) mechanism that leverages Segment Routing (SR) to offload traffic away from congested links using Unequal Cost Multi Paths (UCMP) over alternative paths. In this paper, we introduce an efficient algorithm for alternative paths’ computation, and two methods to compute UCMP weights, depending on whether remote link loads are available or not. We show that the proposed path computation method is faster than a modified K-shortest path algorithm. For traffic splitting, we show that the knowledge of remote link loads and per-destination traffic is a key to mitigate congestions in loaded scenarios, approaching the results obtained with an optimal solution. However, when not available, a local solution can already mitigate congestions in lightly loaded scenarios.

In this paper, we consider the Unsplittable Shortest Path Routing (USPR) problem which arises in the field of traffic engineering for IP networks. This problem consists, given a bidirected graph and a set of commodities, to compute a set of routing paths and the associated link weights such that each commodity is routed along the unique shortest path between its origin and its destination, according to these weights. In this paper, we propose a novel extended formulation based on routing variables that is solved using a column generation procedure, further enriched by primal heuristics allowing to build of an efficient matheuristic. We show through a set of experiments that our algorithm allows to quickly identify good feasible solutions when compared to the results obtained by the state-of-the-art local search algorithm.

Given a directed graph with capacities and interdiction costs associated with its arcs, the maximum flow blocker problem (MFBP) asks to find a minimum-cost subset of arcs to be removed from the graph in such a way that the remaining maximum-flow value does not exceed a given threshold. The MFBP has applications in telecommunication networks and in the monitoring of civil infrastructures, among others. We propose an integer linear programming formulation (ILP) with an exponential number of constraints, called Benders cut, for the MFBP. Accordingly, we derive a branch-and-cut algorithm to optimally solve the problem. Preliminary experimental results are reported to assess performance of the formulation and more precisely to determine the dimension of the problem that could be solved to proven optimality.

In this paper, we propose two exact algorithms based on the computation of the Dijkstra tree to solve the multiple pairs shortest path problem. Traditionally, to solve this kind of problems, algorithms are based on distance matrices. For sparse graphs, the computation of these matrices is too costly. The two approaches that we propose allow tackling this issue by computing a small number of Dijkstra trees. We test our algorithms on telecommunication network instances and random instances, and we discuss the dependence of the obtained results on the structure of sources and destinations of commodities. We also propose an extension of the Bi-Dijkstra algorithm to consider several destinations together.

Quantum computing is a promising area to tackle optimization problems. Several algorithms are derived from this paradigm. One interesting method is called Quantum Approximate Optimization Algorithm (QAOA) where the goal is to solve a Quadratic Unconstrained Binary Optimization. This method is heuristic in practice but can converge on an optimal solution with enough time and a computer with enough resources. In this paper, we focus on the unsplittable multi-commodity flow problem and we propose a dedicated algorithm using QAOA as a sub-routine. Thanks to well-known methods, cutting plane, column generation, and Lagrangian relaxation, we propose a framework to solve this problem based on QAOA.

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.

Data routing in networks is required to be efficient and reliable. Fast detection and recovery from link or path failures play crucial roles in the reliability guarantee. In this work, we investigate a variant of the multi-commodity flow problem to address one formalization of reliability, where for each demand, a primary path transmits the demand without exceeding a jitter limit and an arc-disjoint secondary path signals the possible failure of the primary path. We first present a compact mixed-integer linear programming model and then we devise a Branch-and-Benders-Cut algorithm to solve this combinatorial optimization problem. On a diverse set of instances, we evaluate the algorithm's performance and discuss several numerical results.

Nowadays, centralized Path Computation Elements (PCE) integrate control plane algorithms to optimize routing and load-balancing continuously. When a link fails, the traffic load is automatically transferred to the remaining paths according to the configuration of load-balancers. In this context, we propose a load-balancing method that anticipates load transfers to ensure the protection of traffic against any Shared-Risk-Link-Group (SRLG) failure. The main objective of this approach is to make better use of bandwidth compared to existing methods. It consists in reserving a minimum amount of extra bandwidth on links so that the rerouting of traffic is guaranteed. We propose a non-linear non-convex model for the problem of minimizing the bandwidth reservation cost. We introduce a new approximation approach based on a neural network to convexify the problem and apply Kelley’s cutting plane method to solve the problem. Finally, we show that our algorithm significantly improves the CPU time against a compact model solved using the SCIP solver.

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.

To optimize bandwidth utilization in wide area networks, a centralized controller typically maintains routing policies at edge routers. In this context, we propose a versatile intent-based policy optimization model that carefully selects the set of overlay links which are allowed for applications based on their requirements and the overall intents of the operator. The optimization model embeds QoS and traffic predictions to anticipate the impact of routing decisions. To address large scale scenarios where the behavior of the network and devices is not known exactly, we integrate data-driven predictions into a local search algorithm to optimize routing policies. The algorithm supports several intents such as the minimization of the congestion or the maximization of the network quality. Thanks to packet-level simulations on an SD-WAN scenario, we show that our intent-based policy optimization system improves significantly performances. For instance, the latency is improved by 40% when the high-quality intent is selected. In addition, the percentage of time SLAs are met is improved by 10% compared to legacy load balancing mechanisms.

In this paper, we present Online Supply Values (OSV), a system for estimating the return of available rideshare drivers to match drivers to ride requests at Lyft. Because a future driver state can be accurately predicted from a request destination, it is possible to estimate the expected action value of assigning a ride request to an available driver as a Markov Decision Process using the Bellman Equation. These estimates are updated using temporal difference and are shown to adapt to changing marketplace conditions in real-time. While reinforcement learning has been studied for rideshare dispatch, fully-online approaches without offline priors or other guardrails had never been evaluated in the real world. This work presents the algorithmic changes needed to bridge this gap. OSV is now deployed globally as a core component of Lyft's dispatch matching system. Our A/B user experiments in major US cities measure a +(0.96±0.53)% increase in the request fulfillment rate and a +(0.73±0.22)% increase to profit per passenger session over the previous algorithm.

Deterministic performance is a key enabler for 5G applications. While specific data-plane solutions have been proposed to reach a low deterministic end-to-end latency and jitter, legacy round-robin schedulers can already be used to guarantee bounds on the end-to-end latency, when associated with per-flow shapers. In this context, we propose a latency-guaranteed network slicing solution that trades-off between complexity and performance. We propose control plane algorithms to configure sub-channelized interfaces with an independent QoS scheduler at each physical port used by a slice. The algorithms allocate service rates and decide about queue assignments and routing inside each slice. Through numerical results on large network topologies, we demonstrate that our column-generation and two-steps algorithms can improve traffic acceptance while reducing the amount of reserved capacity.

The deployment of 5G networks is paving the road to custom network services. It is now possible to envision the automatic decomposition of a physical network into several virtual networks to serve a wide range of user needs. This technology is also referred to as network slicing. To guarantee the strict isolation of virtual networks, it is possible to rely on underlay technologies such as Flex Ethernet (FlexE). In this demo, we present a slicing solution based on Multi-Topology-Routing (MTR). We will demonstrate how IGP weights can be designed for the embedding of a slice, described by a traffic matrix and end-to-end latency requirements, to minimize the cost of underlay bandwidth reservations.

Deterministic performance is a key enabler for 5G networking. In this context, we present a highly scalable Large-scale Deterministic Network (LDN) architecture providing end-to-end latency and bounded jitter guarantees in IP networks. At the data plane, flows are first shaped at ingress gateways using gate-control queues, achieving a very fine granularity compared to existing state of the art solutions. Inside the network, traffic is scheduled using an asynchronous cyclic queuing mechanism that can be implemented in real devices as it requires only 3 FIFO queues. The data plane relies on standard IP routing and a quasi-static mapping table to deterministically aggregate and forward packets over cycles with a low complexity in O(1). For the control plane, we present an advanced column generation algorithm to quickly take admission control decisions in large-scale networks. For a set of flows, it determines acceptance and selects the best shaping and routing policy. Through a proof-of-concept implementation and simulations, we show that our LDN architecture can guarantee end-to-end latency and bounded jitter. We also demonstrate that our advanced control plane algorithm brings an improvement up to 40% in terms of accepted traffic over classical routing.

We study the problem of partitioning a graph into k connected components, which may also be referred to as the maximum k-cutset problem. Firstly, we present an exact algorithm and a variant, both implemented as integer linear programming (ILP) models. We then present a heuristic approach that will be seen to be extremely competitive with the exact algorithm for the ranges of graph under consideration.

In this paper we present a mathematical formulation for solving open shop scheduling problem. We derived different classes of valid inequalities to strength the model. Exhaustive computational experiments on the well known sets of Taillard's benchmarks are presented. The derived valid inequalities show a good improvement to the computational time for the proposed model.

In this paper, we consider the bipartite complete matching vertex interdiction problem, taking into account some incompatibilities existing among the resources to assign. This problem ensures the obtainment of a robust assignment, which is defined by the number of missing resources still allowing a valid assignment. We introduce graph formulations, considering a single time period or several ones. This problem is shown to be NP-hard, even when considering only a single time period. For several time periods, we adapt the graph formulation, allowing us to solve the problem using polynomial heuristics. Two greedy algorithms and a genetic algorithm are proposed and compared on a randomly-generated testbed.

This paper deals with the mathematical modeling of a scheduling problem for unrelated parallel machines with precedence constraints in order to minimize the makespan (Cmax). This study was motivated by the quality of the Integer Program based on the interval graph. Three families of inequalities are proposed. The first two inequalities based on the idea of the precedence jobs and the third based on the shortest processing time(SPT). We studied the validity of the new inequalities and strength them by checking the linear combination. After an exhaustive computational and statistical analysis we can conclude that the addition of these inequalities decreases the computational requirements to obtain the optimal solution in many cases.

In this paper we discuss a variant of the well-known k-separator problem. Given a simple graph G = (V ∪ T, E) with V ∪ T the set of vertices, where T is a set of distinguished vertices called terminals, and E a set of edges, the multi-terminal vertex separator problem consists in partitioning V ∪T into k+1 subsets {S, V1, ..., Vk} such that the size of S is minimum, each subset Vicontains exactly one terminal and no vertex in Viis adjacent to a vertex in Vj. Three extended formulations are proposed for the problem. We develop Branch-and-Price algorithms for the two first formulations and a Branch-and-Cut-and-Price algorithm for the third one. Some experimental results are also discussed.

One important aim in tire industry when finalizing a tire design is the modeling of the noise characteristics as received by the passengers of the car. In previous works, the problem was studied using heuristic algorithms to minimize the noise by looking for a sequence under constraints. These constraints are imposed by tire industry. We present a new technique to compute the noise. We also propose an integer linear program based on that technique in order to solve this problem and find an optimal sequence. Our study shows that the integer linear programming approach shows significant improvement of the found tire designs, however it has to be improved further to meet the calculation time restrictions for real world problem size.

Given an indirected graph G = (V;E), a Vertex k-Separator is a subset of the vertex set V such that, when the separator is removed from the graph, the remaining vertices can be partitioned into k subsets that are pairwise edge-disconnected. In this paper we focus on the Balanced Vertex k-Separator Problem, i.e., the problem of finding a minimum cardinality separator such that the sizes of the resulting disconnected subsets are balanced. We present a compact Integer Linear Programming formulation for the problem, and present a polyhedral study of the associated polytope. We also present an Exponential-Size formulation, for which we derive a column generation and a branching scheme. Preliminary computational results are reported comparing the performance of the two formulations on a set of benchmark instances.

In this paper, we consider the Robust Nurse Assignment Problem. This consists in finding the maximum number of absences of qualified nurses still permitting an optimal treatment of patients, leading us to the notion of critical jobs. We introduce the Bipartite Complete Matching Vertex Interdiction Problem as the graph formulation of this problem. We show that it can be solved in polynomial time thanks to the integer polytope of an associated sub-problem. Then, we study the polytope associated with the Bipartite Complete Matching Vertex Interdiction Problem. We also extend the well-known Hall theorem to this problem.