Network Optimization

A New Exact Algorithm for Continuous-Time Service Network Design with Splittable Deliveries

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Network Optimization Tags , , , ,

The Continuous-Time Service Network Design Problem (CTSNDP) arises in consolidation-based transportation systems, where shipments share paths in space and time to reduce cost. The CTSNDP determines minimum-cost transportation plans over a continuous-time horizon. To provide more consolidation opportunities and achieve further cost reductions, CTSNDP with Splittable Deliveries (SCTSNDP) allows each commodity to be divided into … Read more

Network flow-based cuts for binary bilevel programs

Categories Bilevel Optimization, Integer Programming, Network Optimization Tags , , , , ,

Binary bilevel programs are challenging to solve due to the lack of compact single-level reformulations. Recent extended network flow-based reformulations have emerged as a promising approach, providing strong dual bounds. However, their increasing size can make them computationally prohibitive. We develop a cutting-plane framework that exploits these networks without requiring an extended-space formulation. We introduce … Read more

Robust Network Enhancement: Formulations and Approximations

Categories Integer Programming, Network Optimization, Robust Optimization Tags , ,

We study robust network enhancement problems that improve network performance through component upgrades, where both network utilities and enhancement costs are uncertain. We consider two formulations: a lower-bound problem that improves the minimum utility across feasible network structures and an upper-bound problem that improves the maximum utility. For the lower-bound problem, we develop an exact … Read more

From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing

Categories Convex Optimization, Network Optimization, Nonlinear Optimization

We study decentralized minimization of sums of smooth strongly convex functions, one per agent, with communication restricted to neighbors in a graph. Existing decentralized algorithms typically emulate a {\it centralized} method; {\it the network serves only to exchange information}, from which agents approximate the global quantities that the method needs. This paper breaks with this … Read more

A Formulation for Power Flow Interdiction with Bounded Big-M Values

Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Network Optimization Tags , , ,

Interdiction for the direct current optimal power flow problem is commonly modeled in two stages, where an attacker disables components in the first stage and an operator makes remedial adjustments in the second stage. The resulting bilevel mathematical program is often solved via transformation into a single-level mixed-integer program using duality. A drawback of this … Read more

solving the multi-objective integer minimum cost flow problem via circulations

Categories Combinatorial Optimization, Multi-Criteria Optimization, Network Optimization Tags , ,

The Multi-objective Integer Minimum Cost Flow Problem (MOIMCF) asks for the efficient integer flows of a capacitated network whose arcs carry vectors of conflicting costs. We present an exact algorithm that computes a minimal complete set of efficient flows, based on a characterization of efficiency by circulations in the residual network. The feasible set is … Read more

Beyond Local Influence: Improved Bounds, Exact Models and Efficient Algorithms for Component-Based Diffusion in Networks

Categories Combinatorial Optimization, Network Optimization Tags , ,

Diffusion in networks is often modeled as a local neighbor-based process: a node becomes active as a result of influence exerted by its active neighbors. However, in many technological and communication settings, adoption is driven not only by local influence, but by access to sufficiently large active connected regions. This paper studies such component-based diffusion … Read more

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