{"id":"4476b41c-0a35-4515-acf2-0a07dff44d40","arxiv_id":"2506.20216","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A mixed-integer linear reformulation and a sampling heuristic let network designers trade off transportation cost against next-day delivery coverage that depends on overlapping warehouse inventories.","lead":"This paper introduces a network design model that balances shipping costs against how many unique items can be delivered next day, using a piecewise-linear approximation of inventory coverage. The authors reformulate the joint problem as a mixed-integer linear program and report average cost improvements of 8.36% over a cost-only baseline on synthetic networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sampling heuristic restricts feasible speed vectors to an unproven subset; no exact-benchmark comparison for n_O>κ exists, so the 8.36% improvement and the method's practical claims rest on an unvalidated design-space pruning.","rationale":"The paper's theoretical core — the concave-closure reformulation (7)-(8) and Proposition 1 — is correct for the full domain Z_d. The load-bearing risk is in the step that makes the problem tractable: replacing Z_d with \\tilde{Z}_d in Section 3.3. Because z_d is binary, this replacement is not a smooth approximation of the objective; it is a hard constraint on the feasible speed assignments. The greedy top-κ selection has no worst-case guarantee, and for submodular coverage functions the optimal set can require origins that are weak individually but complementary jointly. The authors' experiments do not close this gap: the only instance where the heuristic is compared with exactness (n_O=10, κ=10) is the one where the heuristic is trivial; for n_O=20,50,100 no exact benchmark exists. The reported 8.36% improvement is also tied to this unvalidated heuristic and, as the reader notes, is not reproducible from Table 2. These observations support the reader's conditional verdict: the theoretical contribution can stand, but the empirical claims require either a corrected, reproducible experiment or a formal approximation guarantee.","tokens_in":13138,"tokens_out":12229,"duration_ms":125256,"concrete_test":"On randomly generated instances with n_O=12,14,16 and n_D=5, enumerate all 2^{n_O} coverage vectors per destination, solve the full MILP (8) to a tight optimality gap, and compare the resulting objective and chosen speed-vector set against the outputs of Algorithm 1 with κ=10. If the heuristic objective is within 1% of the exact optimum across all instances, the design-space restriction is empirically benign; if the gap is larger, the approximation's lack of a guarantee is load-bearing and the paper's practical claims are not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reformulation (8) is exact only when the full domain Z_d is used (Prop. 1). The implemented method replaces Z_d with \\tilde{Z}_d from Algorithm 1, and because z_d is binary, any 0-1 speed vector not in \\tilde{Z}_d is infeasible in the MILP. Thus the heuristic does not merely approximate the coverage value; it restricts the feasible design space itself. The selection rule ranks origins by singleton coverage I_d(1_o); for submodular coverage functions this can miss high-value combinations where an origin's contribution is complementary to others, so the top-κ set is not guaranteed to contain the optimal speed assignment. No approximation guarantee is provided, and the experiments never compare against the exact MILP for any instance with n_O>κ: for n_O=10 and κ=10 the heuristic is exact, so the approximate regime is validated only through self-comparisons of κ. The headline 8.36% improvement is computed against a cost-only baseline that ignores NDD revenue, and it is not reproducible from Table 2 under a consistent revenue definition (the Cost-Rev column implies a different γ than stated in the text). Hence the practical claim that the sampling heuristic preserves most of the benefit is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13420,"tokens_out":10899,"duration_ms":107715,"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":[{"comment":"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.","section":"Section 3.3, Algorithm 1, equation (9)"},{"comment":"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.","section":"Table 2, Section 4.2"},{"comment":"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.","section":"Abstract and Section 4.2"},{"comment":"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.","section":"Table 1, Section 4.1"}],"minor_comments":[{"comment":"Typo: 'off-the-self solvers' should be 'off-the-shelf solvers'.","section":"Section 3.2"},{"comment":"Typo: 'NND' should be 'NDD' in the sentence 'we can offer NND for all items stored at origin o'.","section":"Section 4.1"},{"comment":"The caption says 'four randomly generated network' but the table reports five networks; correct the count.","section":"Table 1 caption"},{"comment":"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.","section":"Algorithm 1, line 7"},{"comment":"The notation 'Cvx(C)' for convex hull is unusual; consider using 'conv(C)' for readability.","section":"Section 1.4"},{"comment":"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.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The mathematical core of the paper is sound; the main risk is entirely in the experimental section. The inconsistent revenue computations and the unreproducible 8.36% claim are serious but correctable. I would recommend asking the authors to supply corrected tables, a precise statement of how each column is computed, and at least one exact-benchmark comparison for the heuristic in a regime where it is not trivially exact. If those are provided, the paper could become a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe thing to know about this paper is that the theory is fine but the experiments don't support the headline. The authors formulate a speed-aware network design problem where NDD coverage is the number of unique items reachable in one day, with overlapping inventory across origins. They then use the concave closure of the coverage function to turn the nonlinear objective into a MILP, and prove that the interpolation is exact at integer points. That is a legitimate, useful reformulation, and the paper deserves credit for making the inventory-overlap structure explicit and for recognizing the function's submodularity.\n\nThe soft spots are all in the approximation and the validation. Algorithm 1 samples a subset of speed vectors. Because speed variables are binary, any vector not in the sampled set is infeasible in the MILP—this is not just an approximation of the coverage value, it is a restriction of the feasible design space. The paper offers no guarantee on this restriction, and the experiments never compare against the exact MILP for n_O > κ. The only instance where the method is provably exact is n_O=10 with κ=10, which is the trivial case. The claims about the heuristic's effectiveness rest on self-comparisons of κ, not on a ground-truth optimum.\n\nThe numerical reporting is also internally inconsistent. In Table 2, the baseline row for n_O=10, n_D=20 has Costs 1419.2, Rev. 370.7, but Cost-Rev. printed as 677.7 rather than 1048.5; the n_O=100, n_D=100 baseline has a similar inconsistency. That makes the headline 8.36% average improvement impossible to reproduce from the reported numbers. The baseline itself is a cost-only design that ignores NDD revenue entirely, so comparing against it does not demonstrate that the method beats a reasonable speed-aware alternative. No code or data are provided.\n\nThe paper is worth a serious referee, but only with major revision. The reformulation is sound and the problem is relevant for middle-mile logistics. A referee should ask for corrected tables, code or data, a comparison against an exact or near-exact solver for small cases with n_O > κ, and a more meaningful baseline. As it stands, the practical claims outrun the evidence.","headline":"A sound concave-closure reformulation with an unvalidated sampling heuristic and inconsistent experimental tables; the theory is worth refereeing, the empirical claims are not.","tokens_in":13939,"tokens_out":4274,"would_cite":false,"duration_ms":43745,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90B10","90C31"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["network design","speed coverage","next-day delivery","mixed-integer linear programming","parametric optimization","concave closure","submodular coverage","transportation networks"],"falsifier":"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.","tokens_in":12938,"feed_emoji":"🚚","tokens_out":9105,"duration_ms":90820,"temperature":0.7,"pith_summary":"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.","feed_headline":"Delivery speed and shipping cost optimized together in one model","feed_subtitle":"By replacing next-day delivery coverage with an exact concave interpolation, the model beats cost-only design by 8.36% on average.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the parametric-optimization background that the interpolation method builds on.","marker":"[2]"},{"why":"Establishes that the parametric linear program in (7) yields a concave piecewise-linear function, enabling the MILP reformulation.","marker":"[7, Chapter 6]"},{"why":"Provides the multiparametric linear programming theory underlying the parametric program.","marker":"[23]"},{"why":"Introduces the concave closure used to extend the submodular coverage function to the continuous domain.","marker":"[24]"},{"why":"Defines the middle-mile next-day-delivery coverage model and its submodularity, the setting this paper extends.","marker":"[5]"},{"why":"Shows that maximizing such submodular coverage functions is NP-hard, motivating the reformulation and sampling.","marker":"[20]"}],"fun_headline_variants":["Network design that balances cost and next-day delivery speed","Optimizing shipping cost and speed together yields 8.36% gain","Exact method for joint cost-speed optimization in networks","Speed-aware networks: parametric approach beats cost-only by 8.36%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Network design that balances cost and next-day delivery speed","Optimizing shipping cost and speed together yields 8.36% gain","Exact method for joint cost-speed optimization in networks","Speed-aware networks: parametric approach beats cost-only by 8.36%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1523,"prompt_tokens":1007,"completion_tokens":516,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":623,"completion_tokens_details":{"reasoning_tokens":444}},"tokens_in":623,"tokens_out":516,"duration_ms":5048,"temperature":1.0,"reasoning_tokens":444,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:55:32.615887+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the parametric-optimization background that the interpolation method builds on."},{"cited_title":"Gal, and J","cited_arxiv_id":null,"evidence_quote":"Provides the multiparametric linear programming theory underlying the parametric program."},{"cited_title":"Submodular function maximization via the multilinear relaxation and contention resolution schemes","cited_arxiv_id":null,"evidence_quote":"Introduces the concave closure used to extend the submodular coverage function to the continuous domain."},{"cited_title":"Last Truck Scheduling for Middle-mile Next-day Delivery Coverage","cited_arxiv_id":"2310.18388","evidence_quote":"Defines the middle-mile next-day-delivery coverage model and its submodularity, the setting this paper extends."}],"review_version":1}