Pith. sign in

REVIEW 4 major objections 6 minor 28 references

Speed-Aware Network Design: A Parametric Optimization Approach

T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper shows that delivery-speed objectives can be folded into a mixed-integer linear program with no loss at integer points, and that a sampling heuristic keeps the program solvable.

desk verdict A sound concave-closure reformulation with an unvalidated sampling heuristic and inconsistent experimental tables; the theory is worth refereeing, the empirical claims are not. read the letter →

arxiv 2506.20216 v1 pith:BEYS6HCK submitted 2025-06-25 math.OC

Ugo Rosolia , Marc Bataillou Almagro , George Iosifidis , Martin Gross , Georgios Paschos This is my paper · ORCID
classification math.OC MSC 90C1190B1090C31
keywords networkdesignspeedcoveragenext-daydeliverymixed-integerlinearprogrammingparametricoptimizationconcaveclosuresubmodulartransportationnetworks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's aim is to show that the delivery-speed side of network design can be optimized jointly with shipping cost instead of being imposed as a hard constraint. It introduces speed-coverage, the count of unique items that can be delivered within one day, which depends on which origins have short paths to destinations and on how inventories overlap across origins. Because this coverage function is submodular and has exponentially many data points, the paper replaces it with a concave piecewise-linear interpolation (its concave closure) and proves the interpolation is exact at all integer points, producing a mixed-integer linear program equivalent to the original problem. A sampling heuristic keeps that program manageable, and experiments on random networks report an average 8.36% improvement in combined cost minus next-day revenue compared with a cost-only design. If correct, this gives logistics planners a practical way to tune the cost/speed tradeoff with a single parameter.

What carries the argument

The central object is the concave closure of the speed-coverage function: for each destination d and each binary vector z indicating which origins have short paths, the paper defines tilde-I_d(z_d) as the value of the linear program that maximizes a convex combination of known coverage values I_d(z_d^i), yielding a concave piecewise-linear function that is exact at integer vertices. This conversion turns the nonlinear, submodular term into linear constraints and variables, giving the mixed-integer linear program (8). The approximation stage then replaces the full set of integer points with the four families H0–H3 selected by ranking origins on their individual coverage I_d(1_o), which is what makes the program tractable in the experiments.

What would settle it

On a small network with few origins per destination, enumerate every possible speed pattern and solve problem (5) exhaustively; then run the full mixed-integer reformulation (8) on the same data and confirm it matches the exhaustive optimum, and run Algorithm 1 with the smallest kappa and compare the true cost-minus-revenue. Any gap in the first comparison falsifies the equivalence claim, and any gap in the second shows the sampling heuristic is lossy.

Watch

Extended reading notes

Core claim

The paper introduces the speed-aware network design problem P2, in which a middle-mile network is chosen to minimize truck costs minus gamma times the number of unique items eligible for next-day delivery, with coverage depending jointly on which origin–destination pairs get short paths and on the overlap of inventory stored at origins. Because the coverage function is submodular and has $2^{{n_O}}$ integer points per destination, the paper replaces it with a concave closure: the best convex combination of known integer coverage values. The key claim is that this replacement is exact at every integer speed assignment (Proposition 1), so the full reformulated problem is an equivalent mixed-integer linear program. For tractability, Algorithm 1 samples a subset of speed assignments based on per-origin coverage; numerical tests on randomly generated networks show the sampled program improves combined cost-and-revenue by 8.36% over a cost-only baseline.

Load-bearing premise

The sampled set of speed patterns built from the top-ranked origins is assumed, without proof, to contain the patterns an optimal speed-aware network would use; any pattern left out is treated as forbidden in the approximate mixed-integer linear program, so the reported 8.36% advantage rests on this unverified restriction.

Editorial extensions

If this is right

  • Network designers can trade off transportation cost and next-day coverage continuously by varying gamma, with higher gamma empirically leading to more direct speed-paths and higher coverage.
  • The sampled mixed-integer linear program can be solved with off-the-shelf solvers, avoiding evaluation of all 2^{n_O} inventory patterns per destination.
  • For the tested 20-origin case, using only 59 data points per destination (kappa=1) still improves over the cost-only baseline by 8.36% on average, and raising the sample to 1081 points improves the combined cost by a further 1.79%.
  • For the full set of speed patterns, the interpolation is exact at all integer points, so the full reformulation and the original problem have the same optimal value.
  • The approach explicitly handles partially overlapping inventories, which earlier speed-aware network models did not optimize directly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Left implicit: the concave-closure device is not specific to one-day delivery; any submodular coverage term that can be evaluated on integer subsets could be inserted into a mixed-integer linear program the same way, so the device should transfer to other service-level or assortment-coverage objectives.
  • The reported 8.36% is an empirical property of the sampled program with the heuristic's chosen speed patterns, not of the exact reformulation alone; on larger networks the gap between sampled and true optima could be measured by re-solving with increasing kappa until the combined cost stabilizes.
  • A natural testable extension is to make the sampling adaptive: after solving with a small top-kappa set, check the marginal value of promoting the next-ranked origin into the top set, and add that pattern if it changes the chosen network.
  • Because any speed pattern not in the sampled set is simply forbidden, the algorithm's actual guarantee is over the sampled design space; interpreting the reported improvements as properties of the exact problem requires noting that restriction.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper introduces a speed-aware variant of the minimum-cost multicommodity capacitated network design problem (MCND-U), where the objective trades off routing costs against a submodular 'speed-coverage' function that counts unique items eligible for next-day delivery. The central methodological contribution is an exact mixed-integer linear programming reformulation of this nonlinear problem using the concave closure of the coverage function (Section 3.2, Proposition 1), followed by a sampling heuristic (Algorithm 1) that selects a small subset of speed-assignment vectors to keep the MILP tractable. Numerical experiments on random networks are used to support the claim that the approach outperforms a cost-only baseline by 8.36% on average.

Significance. If the central derivation and the empirical claims both hold, the paper would make a useful contribution: the concave-closure reformulation is correct and elegantly connects submodular coverage functions with off-the-shelf MILP solvers, and the sampling heuristic addresses a real scalability bottleneck. The proof of Proposition 1 is sound, and the idea of embedding a data-defined coverage function into a network design MILP is novel and practically relevant. However, the experimental validation is currently not sound as reported: key table entries are internally inconsistent, the headline improvement percentage is not reproducible from the printed numbers, and the sampling heuristic is validated only by self-comparisons across its own hyperparameter rather than against exact solutions in the approximate regime. These issues are fixable within the manuscript's scope, so the paper is a candidate for major revision rather than rejection.

major comments (4)
  1. [Section 3.3, Algorithm 1, equation (9)] The sampling heuristic does not merely approximate the coverage value; it restricts the feasible speed-assignment space itself. Because every z_d and every sampled vector \tilde{z}^i_d is binary, the constraint \sum_i \alpha_i \tilde{z}^i_d = z_d with \alpha_i \ge 0 forces z_d to be one of the vectors in \tilde{Z}_d. Any binary speed vector not in \tilde{Z}_d is infeasible in the approximated MILP. The paper acknowledges this ('Dropping vectors from Z_d means that certain paths will always be chosen to be long'), but it provides no approximation guarantee and no experiment that compares against the exact MILP for any instance with n_O > \kappa. The only exact comparison is for n_O = 10 with \kappa = 10, where the heuristic is trivially exact. Consequently, the claim that the sampling heuristic 'preserves most of the benefit' is unsupported. Please add experiments on small instances with \kappa < n_O compared against the full-domain MILP, or provide a formal bound on the resulting optimality gap.
  2. [Table 2, Section 4.2] The Cost-Rev column is not consistent with the Costs and Rev columns under the stated conversion factor \gamma = 0.1. For example, the baseline row with n_O = 10, n_D = 20 reports Costs = 1419.2 and Rev = 370.7, so Costs \,−\, Rev = 1048.5, yet the printed Cost-Rev is 677.7. The baseline row with n_O = 20, n_D = 10 is consistent (1392.2 \,−\, 770.4 = 621.8), while the n_O = 100 baseline is consistent with Costs \,−\, 10\times Rev (62204.2 \,−\, 36511 = 25693.2). The revenue factor thus appears to vary across rows, contradicting the caption. Because the headline 8.36% improvement is computed from this table, the experimental validation is not sound as reported. Please correct the revenue computations, state the exact formula used for each column, and rerun the experiments.
  3. [Abstract and Section 4.2] The claimed 8.36% average improvement over the baseline cannot be reproduced from the printed Cost-Rev values in Table 2. Using those values, the average improvement of \kappa = 1 over baseline is approximately 4.9%, and the best per-network \kappa gives approximately 6.6%. The paper should either show the exact calculation that yields 8.36% or correct the claim to match the reported data.
  4. [Table 1, Section 4.1] For n_O = 100, the columns 'A vg. Items' and 'App. A vg. Items' differ, with the approximate value sometimes larger than the exact value (e.g., 2032.2 vs 2010 for \gamma = 0; 2037.3 vs 2025.3 for \gamma = 0.1). If both columns are evaluated at the same binary speed vector, Proposition 1 implies that they should coincide whenever that vector lies in \tilde{Z}_d. Please clarify how the exact and approximate coverage columns are computed; otherwise the claim that (9) is exact at the sampled integer points is not supported by the reported numbers.
minor comments (6)
  1. [Section 3.2] Typo: 'off-the-self solvers' should be 'off-the-shelf solvers'.
  2. [Section 4.1] Typo: 'NND' should be 'NDD' in the sentence 'we can offer NND for all items stored at origin o'.
  3. [Table 1 caption] The caption says 'four randomly generated network' but the table reports five networks; correct the count.
  4. [Algorithm 1, line 7] The notation 'Td(i), i = \kappa+1,...,n_O' is unclear; it should specify that T_d(i) denotes the set of top-i origins for destination d.
  5. [Section 1.4] The notation 'Cvx(C)' for convex hull is unusual; consider using 'conv(C)' for readability.
  6. [Abstract] The abstract states that the problem is converted into 'an equivalent mixed-integer linear program', but the sampling version in Section 3.3 is approximate. Please qualify the equivalence as holding for the full domain, with the sampling method presented as a heuristic approximation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the parametric concave-closure reformulation is exact by construction at integer points, and the sampling heuristic is explicitly presented as an approximation rather than as a prediction.

full rationale

The paper's central equivalence claim (Section 3.2, 'The above MILP is equivalent to the original problem (5), as the interpolation from (7) is exact at integer points') is supported by Proposition 1, which is a direct mathematical identity. For any binary z_d, the parametric program (7) has a unique one-hot convex combination because binary vectors are vertices of the hypercube, so tilde{I}_d(z_d) = I_d(z_d). Since both (5) and (8) constrain z_od to be binary, the objective values coincide exactly; this is not an input fitted to an output. The approximation in Section 3.3 explicitly replaces Z_d with tilde{Z}_d and concedes that 'Dropping vectors from Z_d means that certain paths will always be chosen to be long,' so the paper does not present the heuristic as exact. The 8.36% improvement in Section 4.2 is an empirical comparison against a cost-only baseline on the joint objective; the baseline is not used to define the method's parameters. The quantities gamma and kappa are user-specified hyper-parameters, not fitted to produce the reported result. The paper cites its own prior work [5] for submodularity of the coverage function, but the equivalence proof of Proposition 1 does not use submodularity, and the concave closure is attributed to the external reference [24]; hence the self-citation is not load-bearing. The main limitation is that Algorithm 1 has no formal approximation guarantee for kappa < n_O, as the authors acknowledge when they say the strategy 'only computes a lower bound' for n_O=100; that is a robustness/correctness concern, not a circular derivation.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central derivation rests on standard convex-analysis results and a data-derived coverage function; no new physical entities are introduced. The user-chosen parameters γ, κ, and max_tt are the main free choices affecting the reported improvements.

free parameters (3)
  • γ (customer conversion factor) = 0, 0.1, or 1 in experiments
    User-chosen weight balancing transportation cost and NDD revenue; the reported results depend on it.
  • κ (top-origins hyperparameter) = 1, 5, 10, 12, 14, 16 in experiments
    Controls the size of the sampled set Z~_d and hence the accuracy/complexity tradeoff.
  • max_tt (short-path threshold) = 8 hours
    Defines which paths count as next-day-eligible; chosen by hand.
assumptions (4)
  • domain assumption The coverage function I_d can be expressed as (4) and is submodular.
    Used to justify the concave-closure reformulation and the diminishing-returns intuition; based on [5] and the counting definition.
  • standard math Data points z_i^d are vertices of the hypercube, so the parametric program (7) is exact at integer points.
    Relies on convex hull properties of binary vectors; Proposition 1.
  • standard math The value function of the linear parametric program (7) is concave piecewise linear.
    Standard result in parametric programming, cf. [7, Chapter 6].
  • ad hoc to paper The top-κ origins by individual coverage are sufficient to capture near-optimal speed assignments.
    Heuristic premise of Algorithm 1; no bound is given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Speed-Aware Network Design: A Parametric Optimization Approach." pith.science (2026). https://pith.science/paper/BEYS6HCK

@misc{pith2026250620216,
  author       = {Pith},
  title        = {Pith review of: Speed-Aware Network Design: A Parametric Optimization Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BEYS6HCK}},
  note         = {Machine review of arXiv:2506.20216}
}
read the original abstract

Network design problems have been studied from the 1950s, as they can be used in a wide range of real-world applications, e.g., design of communication and transportation networks. In classical network design problems, the objective is to minimize the cost of routing the demand flow through a graph. In this paper, we introduce a generalized version of such a problem, where the objective is to tradeoff routing costs and delivery speed; we introduce the concept of speed-coverage, which is defined as the number of unique items that can be sent to destinations in less than 1-day. Speed-coverage is a function of both the network design and the inventory stored at origin nodes, e.g., an item can be delivered in 1-day if it is in-stock at an origin that can reach a destination within 24 hours. Modeling inventory is inherently complex, since inventory coverage is described by an integer function with a large number of points (exponential to the number of origin sites), each one to be evaluated using historical data. To bypass this complexity, we first leverage a parametric optimization approach, which converts the non-linear joint routing and speed-coverage optimization problem into an equivalent mixed-integer linear program. Then, we propose a sampling strategy to avoid evaluating all the points of the speed-coverage function. The proposed method is evaluated on a series of numerical tests with representative scenarios and network sizes. We show that when considering the routing costs and monetary gains resulting from speed-coverage, our approach outperforms the baseline by 8.36% on average.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [1]

    Pipage rounding: A new method of constructing algorithms with proven performance guarantee

    Alexander A Ageev and Maxim I Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization , 8:307--328, 2004

    work page 2004

  2. [2]

    B. Bank, J. Guddat, D. Klatte, B. Kummer, and K. Tammer . Non-Linear Parametric Optimization . Akademie-Verlag, Berlin, 1982

    work page 1982

  3. [3]

    Fortz, L

    B. Fortz, L. E. Neves Gouveia, and M. Joyce-Moniz . Models for the Piecewise Linear Unsplittable Multicommodity Flow Problems . Eur. J. Oper. Res. , 261(1):30--42, 2017

    work page 2017

  4. [4]

    Air network design for express shipment service

    Cynthia Barnhart and Rina R Schneur. Air network design for express shipment service. Operations Research , 44(6):852--863, 1996

    work page 1996

  5. [5]

    Last Truck Scheduling for Middle-mile Next-day Delivery Coverage

    Konstantinos Benidis, Georgios Paschos, Martin Gross, and George Iosifidis. Middle-mile optimization for next-day delivery. arXiv preprint arXiv:2310.18388 , 2023

    work page Pith review arXiv 2023

  6. [6]

    Perspectives on integer programming for time-dependent models

    Natashia L Boland and Martin WP Savelsbergh. Perspectives on integer programming for time-dependent models. Top , 27(2):147--173, 2019

    work page 2019

  7. [7]

    Predictive control for linear and hybrid systems

    Francesco Borrelli, Alberto Bemporad, and Manfred Morari. Predictive control for linear and hybrid systems . Cambridge University Press, 2017

    work page 2017

  8. [8]

    Campbell

    F. Campbell. Hub location for time definite transportation. Computers And Operations Research , 36(12):3107--3116, 2009

    work page 2009

Show all 28 references
  1. [9]

    The rise of crowd logistics: a new way to co-create logistics value

    Valentina Carbone, Aur \'e lien Rouquet, and Christine Roussat. The rise of crowd logistics: a new way to co-create logistics value. Journal of Business Logistics , 38(4):238--252, 2017

    2017

  2. [10]

    Decomposition methods for large-scale network expansion problems

    Ioannis Fragkos, Jean-Fran c ois Cordeau, and Raf Jans. Decomposition methods for large-scale network expansion problems. Transportation Research Part B: Methodological , 144:60--80, 2021

    2021

  3. [11]

    Multicommodity capacitated network design

    Bernard Gendron, Teodor Gabriel Crainic, and Antonio Frangioni. Multicommodity capacitated network design. In Telecommunications network planning , pages 1--19. Springer, 1999

    1999

  4. [12]

    Greening, Mathieu Dahan, and Alan L

    Lacy M. Greening, Mathieu Dahan, and Alan L. Erera. Lead-time-constrained middle-mile consolidation network design with fixed origins and destinations. Transportation Research Part B: Methodological , 174:102782, 2023

    2023

  5. [13]

    Palsson, F

    H. Palsson, F. Pettersson, and L. W. Hiselius . Energy consumption in e-commerce versus conventional trade channels - insights into packaging, the last mile, unsold products and product returns. Journal of Cleaner Production , 164:765--778

  6. [14]

    New formulations for the scheduled service network design problem

    Mike Hewitt and Fabien Lehuede. New formulations for the scheduled service network design problem. Transportation Research Part B: Methodological , 172:117--133, 2023

    2023

  7. [15]

    Pappas, et al

    I. Pappas, et al. Multiparametric programming in process systems engineering: Recent developments and path forward. Front. Chem. Eng. , 2, 2021

    2021

  8. [16]

    The one-dimensional dynamic dispatch waves problem

    Mathias A Klapp, Alan L Erera, and Alejandro Toriello. The one-dimensional dynamic dispatch waves problem. Transportation Science , 52(2):402--415, 2018

    2018

  9. [17]

    Dynamic demand management and online tour planning for same-day delivery

    Vienna Klein and Claudius Steinhardt. Dynamic demand management and online tour planning for same-day delivery. European Journal of Operational Research , 307(2):860--886, 2022

    2022

  10. [18]

    Submodular function maximization

    Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability , 3(71-104):3, 2014

    2014

  11. [19]

    Scalable timing-aware network design via lagrangian decomposition

    CL Lara, J Koenemann, Y Nie, and CC de Souza. Scalable timing-aware network design via lagrangian decomposition. European Journal of Operational Research , 309(1):152--169, 2023

    2023

  12. [20]

    An analysis of approximations for maximizing submodular set functions—i

    George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical programming , 14:265--294, 1978

    1978

  13. [21]

    Chopra, I

    S. Chopra, I. Gilboa, and S. T. Sastry . Source Sink Flows with Capacity Installation in Batches . Discrete Applied Mathematics , 85:165--192, 1998

    1998

  14. [22]

    Shahmohammadi, Z

    S. Shahmohammadi, Z. J. N. Steinmann, L. Tambjerg, P. van Loon, J. M. H. King, and M. A. J. Huijbregts . Comparative greenhouse gas footprinting of online versus traditional shopping for fast-moving consumer goods: A stochastic approach. Environ. Sci. Technol. , 54:3499--3509

  15. [23]

    Gal, and J

    T. Gal, and J. Nedoma . Multiparametric linear programming. Management Science , 18:406--442

  16. [24]

    Submodular function maximization via the multilinear relaxation and contention resolution schemes

    Jan Vondr \'a k, Chandra Chekuri, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 783--792, 2011

    2011

  17. [25]

    Service network design for same-day delivery with hub capacity constraints

    Haotian Wu, Ian Herszterg, Martin Savelsbergh, and Yixiao Huang. Service network design for same-day delivery with hub capacity constraints. Transportation Science , 57(1):273--287, 2023

    2023

  18. [26]

    ADMM -based problem decomposition scheme for vehicle routing problem with time windows

    Yu Yao, Xiaoning Zhu, Hongyu Dong, Shengnan Wu, Hailong Wu, Lu Carol Tong, and Xuesong Zhou. ADMM -based problem decomposition scheme for vehicle routing problem with time windows. Transportation Research Part B: Methodological , 129:156--174, 2019

    2019

  19. [27]

    Hub location, routing, and route dimensioning: Strategic and tactical intermodal transportation hub network design

    Baris Yildiz, Hande Yaman, and Oya Ekin Karasan. Hub location, routing, and route dimensioning: Strategic and tactical intermodal transportation hub network design. Transportation Science , 55(6):1351--1369, 2021

    2021

  20. [28]

    Optimizing package express operations in china

    Barış Yıldız and Martin Savelsbergh. Optimizing package express operations in china. European Journal of Operational Research , 300(1):320--335, 2022

    2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.