{"id":"a74d8b70-7117-4382-a138-9274f9ff8d66","arxiv_id":"2506.09793","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"A window-based matheuristic that solves 13-19 facility subsegments exactly with MIP matches or improves every best-known solution on the standard large SRFLP benchmarks, setting 17 new bests.","lead":"This paper introduces a matheuristic for the single row facility layout problem: simulated annealing builds good layouts, then a mixed-integer program optimally reorders a small moving window of 13 to 19 facilities while the rest stays fixed. On standard large benchmarks the method matches or improves every best-known solution, with 17 new best values.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation (14) in §4.2 does not express the full objective it claims to bound, so the window update may accept a worse layout.","rationale":"The reader's weakest_assumption focuses on the uncontrolled runtime comparison with KMPG in §5.1/§5.4, which is indeed a real limitation of the 'outperforms state-of-the-art' phrasing. That concern is legitimate and would justify a CONDITIONAL verdict even on its own. However, I regard the Eq. (14) issue as more load-bearing because it concerns the internal correctness of the method as specified: the improvement constraint, as printed, does not equal the full objective and therefore cannot guarantee that the window update accepts only improving solutions. This was mentioned in the reader's rationale but not chosen as the weakest assumption. The empirical results may still be correct if the implementation deviates from Eq. (14), but the manuscript's algorithmic description is then not faithful to the executed method. The concrete test of enumerating window permutations on a small instance would settle immediately whether Eq. (14) can admit a worsening move. The paper does have independent support: Proposition 1's decomposition appears algebraically correct, and the §5.3 ablation under identical time limits provides genuine evidence that the window component helps. Thus I do not see grounds to reject the paper, but the Eq. (14) defect reinforces the CONDITIONAL verdict rather than removing it.","tokens_in":23704,"tokens_out":11098,"duration_ms":106397,"concrete_test":"Take a small SRFLP instance, for example n=20, and a feasible layout π. Pick a window of size 5, for instance positions 8–12, and enumerate all 5! internal permutations σ with the outside order fixed. For each σ, compute (a) the true objective F(σ) via Eq. (1) and (b) the LHS of Eq. (14) with the x variables read off from σ. Check whether any σ satisfies LHS(σ) < F(π) while F(σ) > F(π). If such a permutation exists, Eq. (14) is not a valid improvement cut; if none exists for this instance, repeat with random windows and random instances. This directly tests the 'only improvements are accepted' claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The improvement constraint in §4.2, Eq. (14), is not the full objective. Proposition 1 and Eq. (10)–(11), (21) correctly decompose the SRFLP objective into fixed(sw,ew,π) plus three permutation-dependent summands: before-window to inside-window, inside-inside, and inside-window to after-window. Eq. (14) writes the LHS as fixed(sw,ew,π) + Σ_{i<j in window} w_ij Σ_{k≠i,k≠j} ℓ_k x_{i,k,j}, i.e., only the variable part of the inside-inside summand. The boundary-dependent before-inside and inside-after terms are omitted, as are the constant (ℓ_i+ℓ_j)/2 contributions. The text states that this LHS 'represents the objective value of the solution,' which is false. If the MIP actually enforces Eq. (14), the window approach can return a permutation whose inside-inside betweenness sum improves while the omitted boundary terms worsen enough that the total objective F(π') exceeds F(π); the method would then accept a worse solution, contradicting the claimed guarantee that 'only improvements are accepted.' If the implementation instead uses a correct objective inequality, then the printed equation does not describe the implemented method. Either way, the manuscript as written does not fully support the central algorithmic claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a matheuristic for the single row facility layout problem (SRFLP), combining a multi-start simulated annealing phase with two local search procedures and a new \"window approach\" that optimally reorders a contiguous block of facilities via a betweenness-based MIP while keeping the remaining layout fixed. The authors report that the method matches or improves the best-known solution values on all 70 benchmark instances from the Anjos-large, Sko-large, and Palubeckis-large sets (improving 17 of them), and they include an ablation study showing that the window component is beneficial under identical time limits. The paper also provides a formal decomposition of the objective function in Proposition 1 and an appendix proof.","tokens_in":23922,"tokens_out":11852,"duration_ms":125006,"significance":"If the results are correct, the window approach is a novel and effective intensification mechanism for large-scale SRFLP instances, and the paper would be the first matheuristic specifically designed for this problem. The algebraic decomposition in Proposition 1 is sound, the ablation in Section 5.3 cleanly isolates the value of the window component under identical time limits, and the benchmark coverage is broad. However, the external comparison in Section 5.4 is not time-controlled, and the improvement constraint in Section 4.2 is mis-specified, so the central claim of outperforming state-of-the-art metaheuristics requires clarification before the paper can be accepted.","major_comments":[{"comment":"Equation (14) does not express the objective value it claims to bound. By Proposition 1 and Eq. (21), the objective of a candidate window permutation π' is fixed(sw,ew,π) plus three permutation-dependent sums: the before-inside terms, the inside-inside terms (including the constant (ℓ_i+ℓ_j)/2), and the inside-after terms. The left-hand side of Eq. (14) contains only the inside-inside betweenness sum, omitting the two boundary-dependent sums and the inside-inside constant. Therefore the statement that the left-hand side \"represents the objective value of the solution\" is false, and the constraint as printed does not by itself guarantee \"that only improvements are accepted.\" In Algorithm 4, line 15 recomputes F(π') and would reject a non-improving permutation, so a worse solution may not be accepted in the implementation; however, the MIP solved inside MIP_BB is not precisely specified. If the MIP minimizes the left-hand side of Eq. (14), it optimizes a wrong objective; if it minimizes the correct objective, the printed improvement constraint should be rewritten in terms of the full window objective. Please correct Eq. (14) and state the exact objective and constraints of the MIP used in Algorithm 4.","section":"§4.2, Eq. (14)"},{"comment":"The headline comparison with KMPG and GRASP-F is not a controlled comparison. The paper assigns its own method a time limit of n^1.7 seconds (about 35 hours per run at n=1000) but does not report the runtimes or hardware used by Tang et al. (2022) or Cravo and Amaral (2019), and Section 5.1 explicitly states that runtime is not included in the comparison. Under these conditions, the 17 improved bounds in Tables 7–9 may reflect a larger computational budget rather than an algorithmic advantage. The internal ablation in Section 5.3, which compares the window and no-window variants under identical time limits, is convincing evidence for the value of the window mechanism, but the broader claim of \"outperforming current state-of-the-art metaheuristics\" needs either a time-controlled re-run of the competitors on the same hardware, or a report of the competitor runtimes together with a justification that the n^1.7-second budget is comparable. Please provide this information or soften the claim accordingly.","section":"§5.1 and §5.4"},{"comment":"The correctness of the MIP subproblem is asserted but not demonstrated in enough detail. The text states that after introducing the two dummy facilities and aggregating external weights, \"we can use the general objective function for the MIP after this modification, see equation (21)\"; however Eq. (21) is a decomposition of the original objective, not a derivation showing that the betweenness model on the window plus dummy facilities reproduces the three permutation-dependent sums in Eq. (10). Since the entire method relies on solving these window subproblems exactly, the paper should give the precise MIP formulation solved in MIP_BB—variables, objective, constraints, and how f_wd is combined with the MIP objective—and a short argument why the dummy-facility weight aggregation yields the correct window subproblem.","section":"§3.2 and Algorithm 4"}],"minor_comments":[{"comment":"The index i is reused in the outer sum over wf and in the inner sum over the window, and the formula appears to multiply each facility length by the sum of all minimum weights rather than by its own minimum weight; please correct the indexing and reconcile the formula with the accompanying text about \"the combined length of all facilities inside the window.\"","section":"§3.2, Eq. (13)"},{"comment":"The text mentions that a check for the direction of the permutation is necessary, but this check is not shown in the pseudocode of create_order; please specify how the algorithm determines whether s is the left or right endpoint and how the final order is oriented correctly.","section":"Appendix B.2, Algorithm 6"},{"comment":"There are typographical errors, including \"Implemention\" in the section title and \"procudure\" in the text; these should be corrected before publication.","section":"Appendix B.1"},{"comment":"Several table entries lack a separator between the instance name and the objective value (e.g., \"400 03920860291.00\" and \"430286334521.50\"), which makes the tables difficult to read; please reformat the instance labels consistently.","section":"Tables 4–6"},{"comment":"The hardware description (Intel Xeon X5570, 6GB memory) is useful, but the paper should also report the number of replicates used for the no-window variant in Section 5.3 and the total time consumed by the window-MIP component, since the window step is the main computational bottleneck.","section":"§5.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of a computational optimization journal and the ablation study is a genuine strength. The main risk is that the reported improvements over previous state-of-the-art methods may be budget-driven rather than algorithmic, since no competitor runtimes are reported. The authors should also be encouraged to make the code and detailed results available, as the paper currently refers to the first author's master's thesis for implementation details, which is a barrier to reproducibility."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper introduces the first matheuristic for SRFLP: multi-start simulated annealing with periodically solving a betweenness-based MIP on a moving window of facilities while the rest of the layout is fixed. Proposition 1's decomposition checks out, and the dummy-facility aggregation is a clean handling of boundary weights. The ablation (Tables 4–6) isolates the window's contribution under identical time limits, and the 17 improved best-known values are internally consistent (2+6+9). This is a competent, honestly reported engineering contribution.\n\nThe biggest issue is Eq. (14). As printed, the left-hand side omits the boundary-dependent terms and the constant half-length contributions, so it does not equal the objective value as the text claims. The good news: the algorithm also checks F(π') < F(π) before accepting (line 15 of Algorithm 4), so it cannot actually accept a worse solution. The equation is therefore a pruning cut, not a valid representation of the objective. The paper should be corrected to say this; as written, the description is misleading.\n\nSecond, no code or data is released, and implementation details rely on the first author's master's thesis. Third, the headline comparison with KMPG uses only objective values, not runtime or hardware, and the n^1.7 second budget is large for n=1000 (tens of hours). The internal ablation is not affected by this, but the \"outperforms state-of-the-art\" claim is weaker than it looks.\n\nWho it's for: anyone working on SRFLP or permutation problems with betweenness formulations. It deserves a serious peer review; the referee should ask for code/data and a corrected Eq. (14).","headline":"A solid, first-of-its-kind matheuristic for SRFLP with credible improved bounds, but the printed improvement constraint is wrong and the lack of code/runtime controls tempers the state-of-the-art claim.","tokens_in":24561,"tokens_out":3833,"would_cite":true,"duration_ms":41543,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C27","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"A moving-window MIP sets 17 new best-known layouts for the single-row facility layout problem.","keywords":["single row facility layout problem","matheuristic","window approach","betweenness-based MIP","multi-start simulated annealing","local search","permutation optimization","large-scale benchmark instances"],"falsifier":"Run the previous best-known algorithm on the same machine with the same $n^{1}$.7-second time limit for every one of the 70 benchmark instances; if the window matheuristic no longer improves or matches every best-known value under equal budgets, the claimed superiority is an artifact of the comparison rather than the window mechanism.","tokens_in":23404,"feed_emoji":"🏭","tokens_out":9651,"duration_ms":101180,"temperature":0.7,"pith_summary":"The paper claims that the single row facility layout problem (SRFLP) — arranging facilities on a line to minimize weighted center-to-center distances — can be solved to higher quality by a matheuristic that repeatedly solves small pieces of a layout exactly. Its window approach keeps every facility outside a moving interval fixed, then uses a betweenness-based mixed-integer program to reorder the facilities inside the interval optimally, with dummy facilities representing the fixed left and right parts. Embedded in multi-start simulated annealing with two local searches, this method is claimed to be the first matheuristic designed for the SRFLP. On 70 standard large benchmark instances, it improves the best-known solution value for 17 instances and matches it for the other 53, with the gains concentrated on instances with at least 500 facilities.","feed_headline":"Matheuristic improves 17 of 70 best-known facility layout solutions","feed_subtitle":"The window method also matches the previous best on all 53 remaining large instances, with very low run-to-run variation.","key_machinery":"The central object is the betweenness-based MIP formulation, whose binary variables indicate whether one facility lies between two others, together with the window adaptation that makes it tractable for large instances. On any window the algorithm fixes all facilities outside the chosen interval, introduces two zero-length dummy facilities for the aggregated left and right parts, aggregates external weights into the MIP weight matrix, and precomputes the fixed part of the objective so the solver optimizes only the window's internal permutation. The machinery also includes an improvement constraint that makes the MIP return only strictly better permutations, plus an orientation check because the endpoint pair produced by the ordering routine can be read in either direction.","core_discovery":"The paper's central claim is that a moving-window exact optimization defines a new neighborhood for the SRFLP: fix the order outside an interval, precompute all distances that cannot change, aggregate the weights of external facilities into two zero-length dummy facilities, and solve the betweenness-based MIP for the window's contents, accepting a new order only if it strictly lowers the objective. The objective decomposes into fixed, partially dependent, and fully variable terms, and Proposition 1 formalizes this decomposition. In the full algorithm the window operator runs with window size 13 inside the multi-start simulated annealing phase and sizes 17 and 19 in a refinement phase, after insertion and swap local searches. On the three standard large benchmark sets, the paper reports new best-known upper bounds on 17 of 70 instances and matches the previous best-known value on the remaining 53, and the ablation without the window component shows that the improvements come from the window on the larger instances.","pith_inferences":["The paper does not report the time budgets of the baseline runs; if those budgets were smaller than the n^1.7-second limit used here, part of the 17 improvements could be a time artifact. An equal-budget rerun of the previous best-known algorithm on identical hardware would settle this.","The window operator only needs a betweenness-based MIP and a feasible permutation, so it should transfer to permutation problems such as minimum linear arrangement; a natural test is whether window sizes 13 to 19 remain effective there.","The strict-improvement constraint rejects equal-cost reorderings; allowing ties with a tie-breaker might escape plateaus where an equal layout could unlock later improvements.","The ablation shows that windows pay off mainly at 400 or more facilities, so an instance-size-aware schedule that skips windows on smaller instances could save MIP time with little quality loss."],"forward_implications":["On the 70 benchmark instances, the paper's method reaches or beats every previous best-known solution, so at least 17 of the large-instance bounds in the literature can be lowered.","For instances with at least 500 facilities, the window component is the deciding factor: the no-window version is strictly improved upon in most of these cases, so this neighborhood is the most promising target for future large-scale SRFLP heuristics.","The window approach acts as a self-contained improvement operator on any feasible permutation, so it can be embedded in other metaheuristic frameworks, not only multi-start simulated annealing.","The method is consistent across independent runs: the largest relative standard deviation reported is below 0.0065 percent, and several instances return the same best value in all 15 runs.","Matching every previous best-known value and improving 17 of them suggests that the previous bounds were not optimal and that exact optimization can still contribute at scales where pure metaheuristics dominate."],"supporting_citations":[{"why":"Supplies the betweenness-based MIP formulation that the window operator solves exactly.","marker":"Amaral (2009)"},{"why":"Supplies the multi-start simulated annealing framework and the efficient swap and insertion move-gain formulas reused throughout the algorithm.","marker":"Palubeckis (2017)"},{"why":"Provides the KMPG algorithm and the best-known solution values that form the comparison baseline.","marker":"Tang et al. (2022)"},{"why":"Provides the GRASP F algorithm, the second state-of-the-art baseline used on the same benchmark sets.","marker":"Cravo and Amaral (2019)"},{"why":"Provides benchmark instances and the GRASP with path relinking context used for parameter tuning.","marker":"Rubio-Sánchez et al. (2016)"},{"why":"Defines the problem and the center-to-center distance formula that the objective decomposition builds on.","marker":"Simmons (1969)"}],"fun_headline_variants":["Window matheuristic sets 17 new best-known layouts","First matheuristic for SRFLP improves 17 solutions","Exact window in SA beats best-known on 17 instances","SA plus exact window: 17 new best layout solutions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The comparison with state of the art assumes the published best-known values were produced under computational budgets comparable to this paper's $n^{1}$.7-second time limit, since the paper reports only objective values and not competitor runtimes or hardware.","fun_headline_variants_meta":{"raw":{"variants":["Window matheuristic sets 17 new best-known layouts","First matheuristic for SRFLP improves 17 solutions","Exact window in SA beats best-known on 17 instances","SA plus exact window: 17 new best layout solutions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000189,"raw_usage":{"total_tokens":1348,"prompt_tokens":967,"completion_tokens":381,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":312}},"tokens_in":583,"tokens_out":381,"duration_ms":4537,"temperature":1.0,"reasoning_tokens":312,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:43:16.988234+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the previous best-known algorithm on the same machine with the same $n^{1}$.7-second time limit for every one of the 70 benchmark instances; if the window matheuristic no longer improves or matches every best-known value under equal budgets, the claimed superiority is an artifact of the comparison rather than the window mechanism.","supporting_citations":[{"cited_title":", year 2009","cited_arxiv_id":null,"evidence_quote":"Supplies the betweenness-based MIP formulation that the window operator solves exactly."},{"cited_title":", year 2017","cited_arxiv_id":null,"evidence_quote":"Supplies the multi-start simulated annealing framework and the efficient swap and insertion move-gain formulas reused throughout the algorithm."},{"cited_title":", author Li, Z","cited_arxiv_id":null,"evidence_quote":"Provides the KMPG algorithm and the best-known solution values that form the comparison baseline."},{"cited_title":", author Amaral, A.R","cited_arxiv_id":null,"evidence_quote":"Provides the GRASP F algorithm, the second state-of-the-art baseline used on the same benchmark sets."},{"cited_title":", author Gallego, M","cited_arxiv_id":null,"evidence_quote":"Provides benchmark instances and the GRASP with path relinking context used for parameter tuning."},{"cited_title":", year 1969","cited_arxiv_id":null,"evidence_quote":"Defines the problem and the center-to-center distance formula that the objective decomposition builds on."}],"review_version":1}