Skip to content
Open access

Branch-And-Cut and a Sequential Heuristic for Multimodal Multi-Demand Routing

Aug 2026 · Global Journal of Engineering and Technology Research · Vol 02 · 0 citations

TL;DR

This work compares two complementary solution paradigms—an exact branch-and-cut algorithm and a greedy sequential construction heuristic—in a scalability study on 1000 instances, measuring CPU time, primal quality relative to the certified optimum, and structural growth of the compact model.

Abstract

We study multimodal multi-demand routing with coupled capacities on a formal/informal urban network, modeled by the compact MILP Pext. We compare two complementary solution paradigms—an exact branch-and-cut algorithm (BAC) and a greedy sequential construction heuristic (SEQ)—in a scalability study on 1000 instances (20 groups × 50), measuring CPU time, primal quality relative to the certified optimum, and structural growth of the compact model. Both methods use the same elementary-path decoder, so that the reported time–quality trade-off isolates the algorithmic paradigm rather than incidental modeling differences.

Read PDF

Similar papers

Preprint Sep 2026

On the T-Adaptive Segment Routing Problem

In this paper, we present a multi-period optimization problem arising from the traffic engineering of core IP/MPLS networks, called T-ASR. This problem aims at computing a sequence of segment routing paths that adapt to a multi-period scheduled maintenance, while allowing limited number of path reconfigurations between...

Amal Benhamiche, Kaoutar Bouaachra, Y. Carlinet et al. · 0 citations
Conference

Branch and Incremental Benders cuts for two stage stochastic hub and spoke location-allocation problem

Two-stage stochastic optimization has applications in various domains, including location-allocation, scheduling, routing, and other network flow problems. In practice, most of these problems are solved following a decomposition framework such as L-shaped algorithms based on Benders decomposition. Conventional multi-cu...

Kazi Wahadul Hasan, P. Mirchandani · 0 citations
Preprint Sep 2026

A Spatial Benders Algorithm for Delay Constrained Routing

We study the Delay Constrained Routing (DCR) problem arising in IP computer networks to support high bandwidth applications. The goal is to route IP packets, from source to destination, subject to quality of service constraints -- in particular, bounding the worst case delay -- while minimizing the total allocated band...

A. Frangioni, Laura Galli, L. Mencarelli et al. · 0 citations
Preprint Sep 2026

An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support

Standard Big-M mixed-integer programming reformulations of chance-constrained programs (CCPs) with finite support often yield weak linear relaxations and scale poorly as the number of scenarios increases. To address this limitation, we derive two families of intersection cuts from problem-specific S-free sets and devel...

Soumya Ranjan Pathy, Hamed Rahimian · 0 citations
Preprint Sep 2026

Lexicographic Minimax Load Balancing for T-Adaptive Segment Routing

We introduce the T-Adaptive Segment Routing, a multi-period optimization problem that emerges in the traffic engineering of core IP/MPLS networks when scheduled maintenance operations are involved. The problem seeks a sequence of Segment Routing (SR) configurations that can adapt to a multi-period scheduled maintenance...

Kaoutar Bouaachra · 0 citations
Open access Nov 2026

A graph-based iterative strategy for solving the all-line transmission switching problem

The transmission switching problem aims to determine the optimal network topology that minimizes the operating costs of a power system. This problem is typically formulated as a mixed-integer optimization model, which involves big-M constants that lead to weak relaxations and significant computational challenges, par...

M. Aguilar-Moreno, S. Pineda, J. Morales · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.