Network Optimization

Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem

Categories Network Optimization, Nonlinear Optimization Tags , , ,

Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support … Read more

Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design

Categories Combinatorial Optimization, Network Optimization, Transportation

Dynamic Discretisation Discovery (DDD) is a framework for solving a problem by iteratively solving and refining a relaxed version of the problem. DDD is the basis for state-of-the-art algorithms for various problems, including the continuous-time service network design problem (CTSNDP), which we study here. In the refinement step, such algorithms must identify conflicts in the … Read more

Integrated Master Planning and Demand Fulfillment in Multi-Echelon Supply Chains: Partial vs. All-or-Nothing Fulfillment

Categories Applications - OR and Management Sciences, Network Optimization, Supply Chain Management Tags , , , ,

Modern supply chains differ in lead times, bottlenecks, and demand volatility. Advanced Planning Systems conventionally decouple Master Planning (MP) and Demand Fulfillment (DF) hierarchically, which improves tractability but ignores critical interdependencies between material availability, capacity utilization, and delivery promising. We propose an integrated MP‑DF model, formulate it as a Minimum‑Cost Multicommodity Flow (MCMCF) on a … Read more

A guide to inexact contiguity constraints

Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , ,

For decades, researchers have complained that contiguity constraints make problems like districting much harder than other combinatorial optimization problems. This has prompted the use of integer programming models with inexact contiguity constraints that may be fast in practice but are invalid in the sense that they cut off or “overlook” some contiguous solutions. Examples include … Read more

Second shortest simple paths in directed graphs: a crossing decomposition and a span-adaptive exact algorithm

Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization Tags , , , ,

We study the computation of a second shortest simple \(s\)–\(t\) path (2-SP) in a directed graph with \(n\) nodes, \(m\) arcs and nonnegative integer arc costs bounded by \(C\). Working with reduced costs and a depth-first search that gives priority to a fixed shortest path \(P_{st}\), every candidate second path is a prefix of \(P_{st}\), … Read more

Attention Mechanisms in Physics-Inspired Graph Neural Networks for the Max-Cut Problem

Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization Tags , , ,

Physics-Inspired Graph Neural Networks (PI-GNNs) reformulate MAX-CUT as QUBO energy minimization, training a GNN to produce soft binary node assignments without labeled data. The baseline PI-GCN uses static, degree-normalized aggregation, while its attention-augmented counterpart PI-GAT—built on GATv2—introduces additional hyperparameters whose effects remain uncharacterized. This paper addresses that gap through controlled experiments on five Gset benchmark … Read more

A Catalog of Formulations for the Multi-Follower Discrete Bilevel Network Design Problem

Categories Bilevel Optimization, Branch and Cut Algorithms, Network Optimization Tags , , ,

Network design problems increasingly arise in settings where strategic infrastructure decisions and operational routing choices are made by different actors. Such interactions are naturally modeled as bilevel problems: a network operator designs or modifies a network, while users respond by selecting routes according to their own utilities. This structure captures many applications in transportation and … Read more

Designing Autonomous Aerial Cable Car Networks for Sustainable Urban Logistics

Categories Network Optimization, Other Topics, Transportation Tags , , , ,

This paper investigates the emerging autonomous aerial cableway technology to reduce the negative impacts of urban freight transportation. We focus on the infrastructure design problem to minimize the road-transportation externalities, taking pricing, investment costs, and the physical footprint into account. The network design problem is formulated as a mixed-integer linear programming (MILP) model that explicitly … Read more

A cut-based mixed integer programming formulation for the hop-constrained cheapest path problem

Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

Given a simple graph G = (V, E) with edge cost c ∈ ℝ^|E|, a positive integer h, source s ∈ V and terminal t ∈ V, the hop-constrained cheapest path problem (HCCP) seeks to find an s–t path of length at most h hops with the cheapest cost. This paper proposes a cut-based mixed … Read more

Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Network Optimization

Scenario-based optimization problems can be solved via Benders decomposition, which separates first-stage (master problem) decisions from second-stage (subproblem) recourse actions and iteratively refines the master problem with Benders cuts. In conventional Benders decomposition, all subproblems are solved at each iteration. For problems with many scenarios, solving only a selected subset can reduce computation. We quantify … Read more