{"id":"38486913-d322-4806-b035-39b41e872771","arxiv_id":"1908.04104","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A quadratic-assignment based MIP formulation expresses arc reversals, dummy vertices, width, and scaling objectives directly and matches prior exact models in runtime.","lead":"This paper proposes a new exact mixed-integer programming model for the generalized graph layering problem, using quadratic assignment variables. It competes with prior ordering-based models on standard benchmarks, with mixed runtimes and no clear winner.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"QLA-W is exact only when Y is a valid upper bound; §5.1 sets Y = ⌈1.6√|V|⌉, which is not one for the unrestricted GLP-W, so the reported comparison solves a height-bounded variant.","rationale":"The reader’s stated weakest assumption, dependence on the compact linearization theorem from [5], is not where the argument breaks; that linearization is valid under the assignment constraints, and the paper’s use of the p variables for length, reversals, and dummy vertices checks out. My independent concern is the Y parameter. None of the problem statements in §2 bound the height, so GLP-W has unbounded layer count; an exact MIP must either use a provable upper bound or its reported optima are only optima for that height cap. Since §5.1 fixes Y ≈ 1.6√n, there are simple instances (a directed path) where the true optimum needs n layers, so the experiments cannot support the abstract’s unconditional exactness claim. The empirical competitiveness claim may survive as a claim about the height-bounded variant, but the paper should state this explicitly and either prove the chosen Y is sufficient for its instance sets or report results with a valid upper bound such as Y = |V|. I keep CONDITIONAL because the model itself, with a correct Y, is sound and the comparative experiments remain a useful data point, but the missing artifacts plus this Y mismatch prevent acceptance.","tokens_in":9737,"tokens_out":16977,"duration_ms":179910,"concrete_test":"Take the directed path on 60 vertices with arcs (i, i+1). Fix the §5.1 weights ω_len = 1, ω_wid = 1, ω_rev = 13·59. Solve QLA-W twice: once with Y = 13 and once with Y = 60. If the optimal objective values differ — the Y = 60 solution has objective 60 and no reversals, while the Y = 13 solution must reverse at least one arc and exceed 60 — then the Y = 13 experiment is not solving unrestricted GLP-W. Repeating this check on an AT&T or Random instance whose longest path exceeds ⌈1.6√|V|⌉ would show whether Fig. 3 ever solves the true GLP-W.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is not the linearization in §4.1: equations (2)–(3) do force p_{u,k,v,l} = x_{u,k}·x_{v,l} for binary x, and the derivations of arc length, reversals, and dummy vertices are correct. The weak point is the choice of Y in the GLP-W experiments. Problem 4 defines GLP-W with no height restriction, so an exact formulation needs Y to be an upper bound on the number of layers used by an optimal layering; the natural valid bound is |V|. Section 5.1 instead sets Y = ⌈1.6√|V|⌉, “as in [4]”. This is not an upper bound. For a directed path on 60 vertices, the optimal GLP-W layering with the §5.1 weights (ω_len = ω_wid = 1, ω_rev = 13·59) uses 60 layers, has width 1, total length 59, and no reversals, giving objective 60. Forced into 13 layers, any feasible layering must reverse at least one arc and pay 767 per reversal, so the Y = 13 optimum is far larger. Thus the QLA-W/CGL-W runtimes in Fig. 3 are not solving the problem defined in §2; they solve a height-bounded variant. Since the central claim is that QLA is a competitive exact approach, this mismatch is load-bearing: the empirical evidence does not establish exactness for GLP-W, even though the head-to-head comparison with CGL-W is internally fair.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two mixed-integer programming formulations, QLA-W and QLA-MS*, for the generalized graph layering problem with width minimization (GLP-W) and with adaptation to a target drawing area (GLP-MS*). The models use binary assignment variables x_{v,k} for the layer of each vertex and continuous product variables p_{u,k,v,l} intended to equal x_{u,k} x_{v,l}; equations (1)-(4) enforce a feasible layering, and the objective terms for arc length, reversed arcs, dummy vertices, width, and scaling factor are expressed linearly through these products, following a compact linearization theorem from the author's earlier paper [5]. The paper reports computational experiments comparing QLA-W with CGL-W and QLA-MS* with CGL-MS* on AT&T and random graphs with up to 60 vertices, using Gurobi with a half-hour time limit, and concludes that the quadratic-assignment-based models are computationally competitive with the prior exact models.","tokens_in":10079,"tokens_out":9458,"duration_ms":96595,"significance":"If the computational claims are valid, the paper offers a conceptually natural exact modeling alternative to the ordering-based CGL formulations: the QAP-style model expresses conjunctive layout conditions directly and is compact in the number of constraints. The modeling core is largely correct: for binary x variables, equations (2)-(3) force p_{u,k,v,l} = x_{u,k} x_{v,l}, and the derivations of arc length, reversal indicators, and dummy-vertex counts in Section 4 are sound. The GLP-MS* experiments are not affected by the main concern below because they use the valid bound Y = |V|. However, the experimental evidence for GLP-W is compromised by the choice of Y in Section 5.1, and the paper does not provide code or data for independent reproduction. The approach remains promising, but the empirical support for the central competitiveness claim on GLP-W needs to be corrected before the claim can be accepted.","major_comments":[{"comment":"The choice Y = ceil(1.6 sqrt(|V|)) is not an upper bound on the number of layers needed by an optimal GLP-W solution, so the model solved in Figure 3 is a height-bounded variant of GLP-W rather than the problem defined in Problem 4. Section 4.1 explicitly requires Y to be an upper bound on the number of layers, but Experiment (1) sets Y without any instance-specific justification. For example, a directed path on 60 vertices has an optimal layering under the weights of Experiment (1) that uses 60 layers, width 1, total length 59, and no reversals, giving objective value 60; forcing Y = 13 would require at least one reversal at cost omega_rev = 13 * 59 = 767, so the two optima are far apart. Thus the reported QLA-W and CGL-W runtimes do not establish that either model solves GLP-W as defined. Please either re-run the GLP-W experiments with a valid bound such as Y = |V|, or justify a valid instance-specific upper bound and state explicitly that the comparison is for a height-bounded variant.","section":"§5.1, Experiment (1), and §4.1"}],"minor_comments":[{"comment":"The stated total number of product variables is incorrect: after omitting the diagonal variables p_{u,k,v,k}, there are |A| * Y * (Y-1) such variables, not |A| * (Y-1)^2. Please correct or clarify the counting convention.","section":"§4.1"},{"comment":"The experiments report only solution times and timeout counts. Reporting optimal objective values, or final optimality gaps for timed-out instances, would let readers verify that QLA and CGL solve the same instance to the same optimum and would strengthen the equivalence claim.","section":"§5"},{"comment":"The sentence 'Gurobi 5 (release version 8)' is inconsistent; the solver should be identified as Gurobi 8 or as 'Gurobi (release version 8)'.","section":"§5.1"},{"comment":"The statement that width minimization can be obtained by setting r_W = 1 and r_H = infinity is informal, since the normalized ratios introduced in the paper are finite; a limiting or explicit degenerate-case statement would be more precise.","section":"§2"},{"comment":"In the description of the first instance set, 'The first set ATTar are the AT&T graphs' appears to contain a typo; 'ATTar' should likely be 'AT&T'.","section":"§5.1"},{"comment":"Since equations (2)-(3) rely on the compact linearization theorem from [5], a short statement of the lemma, or a precise pointer to the theorem in [5], would make the paper more self-contained.","section":"§4.1"}],"recommendation":"major_revision","confidential_remarks":"The modeling core of the paper is technically sound, and the main issue is the invalid height bound in the GLP-W experiments, which is fixable by re-running with a valid Y or by clearly repositioning the experiments as solving a height-bounded variant. I do not see grounds for rejection. The reliance on the author's own prior linearization theorem [5] is acceptable because the application of the theorem is correct and the theorem is published. I would ask the editor to ensure the revised version reports objective values in addition to runtimes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the thing you should know: this paper's quadratic assignment model for graph layering is real and clean, but the experiments quietly solve a height-bounded version of GLP-W because the chosen layer bound Y is not an upper bound. That doesn't kill the formulation, but it undercuts the headline claim of competitiveness on the unrestricted problem.\n\nWhat's actually new: no prior QAP-based exact model exists for the generalized layering variants, and the product-variable encoding of arc length, reversals, dummy vertices, width, and scaling is natural and correct. The compact linearization from the author's earlier work [5] is cited rather than proved, but equations (2)-(3) do force p = x_u * x_v for binary x, so the math holds up. The model is compact in constraints and the paper is well structured.\n\nThe main soft spot is the choice of Y in Section 5.1. For GLP-W, there is no height restriction, so an exact formulation needs Y to be at least the number of layers used by an optimal layering; |V| is a safe bound. Setting Y = ceil(1.6*sqrt(|V|)), as done \"as in [4]\", is not a bound. A directed path on 60 vertices has an optimal GLP-W layering using 60 layers, and forcing it into 13 layers forces reversals with high penalty. So the runtimes in Figure 3 do not solve the problem defined in Section 2; they solve a height-bounded variant. The head-to-head with CGL-W is still fair because both use the same Y, but the abstract's claim of an exact approach to the generalized problem is overstated.\n\nA second, lesser issue: there is no code or data, and the comparison is based on aggregated plots without per-instance results or statistical detail. That makes the empirical claims hard to verify. The paper's own conclusion acknowledges the size limitation, which is honest.\n\nWho is this for: researchers working on exact MIP models for layered graph drawing. The formulation is a genuinely new tool and the paper is worth a serious referee. I would not cite it for the experimental claim, but I'd cite it for the QLA model itself.\n\nRecommendation: send it to peer review, but ask for a revision that either uses a valid Y or explicitly states that the experiments target the height-bounded variant. The core contribution is sound; the experimental claim needs recalibration.","headline":"A clean new QAP formulation for layered graph drawing, but the GLP-W experiments use a layer bound that is not an upper bound, so the empirical claims address a height-bounded variant.","tokens_in":10582,"tokens_out":2693,"would_cite":true,"duration_ms":24980,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C27","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A quadratic assignment model matches the best exact solvers for layered graph drawing.","keywords":["graph layering","quadratic assignment problem","mixed-integer programming","compact linearization","graph drawing","arc reversal","minimum width"],"falsifier":"On any small directed graph (e.g., three vertices forming a directed cycle) and a small layer bound $Y$, enumerate all binary assignments satisfying equations (1)-(4) and check whether every variable $p_{u,k,v,\\ell}$ equals $x_{u,k} \\cdot x_{v,\\ell}$. If any feasible binary solution violates this equality, the objective can miscompute arc length or reversal counts, and the model would not solve the stated problem.","tokens_in":9533,"feed_emoji":"📐","tokens_out":2812,"duration_ms":31334,"temperature":0.7,"pith_summary":"The paper proposes new exact mixed-integer programming models, QLA-W and QLA-MS*, for the generalized graph layering problem, based on a quadratic assignment formulation. The models express arc reversals, dummy-vertex counts, width, and drawing-area scaling directly through quadratic terms that are linearized in a compact way. Computational experiments on AT&T and random graphs show these quadratic models are competitive with the previous ordering-based CGL models, with no clear winner overall. A sympathetic reader would care because this offers a more intuitive and potentially more extensible exact approach to a problem central to hierarchical graph drawing.","feed_headline":"QAP-style model matches best exact graph layering solvers","feed_subtitle":"A quadratic assignment MIP expresses width and arc reversals naturally and stays competitive with prior ordering-based models.","key_machinery":"The central object is the compact linearization of quadratic assignment constraints: for each arc $uv$ and layers $k,\\ell$, a continuous variable $p_{u,k,v,\\ell}$ is forced, by equations (2) and (3), to equal $x_{u,k} \\cdot x_{v,\\ell}$ whenever the $x$ variables are binary. Arc length, reversal, dummy-vertex counts, width, and inverse scaling factor are then expressed as sums of these $p$ variables, giving a model with only $2|A|Y + |V|$ constraints while avoiding artificial auxiliary variables for reversals and dummies.","core_discovery":"The central claim is that the quadratic-assignment-based MIP models QLA-W and QLA-MS* are computationally competitive with the previously best exact ordering-based models CGL-W and CGL-MS* for the generalized graph layering problem. Using binary variables that assign each vertex to a layer, and continuous product variables defined for each arc and pair of layers, the model expresses arc length, reversal, dummy vertices, width, and target-area scaling as linear sums over those products. The compact linearization, taken from the author's earlier work, ensures each product variable equals the product of its two binary assignment variables at every feasible binary solution, so the objective faithfully represents the geometric quantities. The paper reports that solution times and timeout counts are comparable across instance families and objective settings, concluding that neither model family is clearly superior.","pith_inferences":["The competitive performance suggests that the difficulty of the QAP does not carry over to this special assignment structure; the compact constraint count may be more decisive than the quadratic nature.","The model could be adapted to other optimization problems with assignment constraints and pairwise interaction costs, such as scheduling or facility layout, where the same compact linearization applies.","Testing QLA-W on larger sparse graphs, or with different MIP solvers, would reveal whether the observed competitiveness is robust or tied to the specific solver and instance densities used.","The natural expression of reversals and dummy vertices might also inspire new heuristic approaches, since the quadratic formulation exposes the pairwise decisions directly."],"forward_implications":["QLA-W and QLA-MS* can serve as drop-in exact alternatives to CGL-W and CGL-MS* when solving layered drawing problems with a general-purpose MIP solver.","The natural quadratic formulation makes it straightforward to add or adjust layout objectives, such as emphasizing width or fitting a specific drawing aspect ratio, without redesigning the model.","Experiments indicate that width-emphasized and aspect-ratio-constrained layering remain hard beyond about 50 vertices for all tested models, pointing to a common bottleneck rather than a model-specific weakness.","The 2:1 aspect-ratio case is consistently the hardest setting for both model families, suggesting that extreme aspect ratios impose particularly tight constraints on feasible layerings.","Because the model is assignment-based, it may more easily accommodate additional assignment-dependent constraints in future generalizations of the layering problem."],"supporting_citations":[{"why":"Provides the compact linearization theorem that equations (2) and (3) force $p_{u,k,v,\\ell} = x_{u,k} x_{v,\\ell}$, the correctness basis for the entire objective.","marker":"[5]"},{"why":"Defines the CGL-W model and EXT formulation that QLA-W is compared against as the prior exact approach for GLP-W.","marker":"[4]"},{"why":"Defines the CGL-MS* model for maximum-scale layering that QLA-MS* is compared against.","marker":"[8]"},{"why":"Introduces the generalized layering problem (GLP) with arc reversals and total arc-length objectives, the problem class this paper addresses.","marker":"[7]"}],"fun_headline_variants":["Quadratic assignment model ties top exact layering methods","QAP formulation matches state-of-the-art graph layering","Exact graph layering: quadratic assignment is competitive","New QAP approach holds its own on graph layering"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The model is correct only if the cited compact linearization result indeed guarantees that each product variable equals the product of its two binary assignment variables at every feasible binary solution; the paper relies on that theorem from earlier work without proving it here.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic assignment model ties top exact layering methods","QAP formulation matches state-of-the-art graph layering","Exact graph layering: quadratic assignment is competitive","New QAP approach holds its own on graph layering"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000162,"raw_usage":{"total_tokens":1141,"prompt_tokens":752,"completion_tokens":389,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":368,"completion_tokens_details":{"reasoning_tokens":324}},"tokens_in":368,"tokens_out":389,"duration_ms":3956,"temperature":1.0,"reasoning_tokens":324,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:51:33.986275+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On any small directed graph (e.g., three vertices forming a directed cycle) and a small layer bound $Y$, enumerate all binary assignments satisfying equations (1)-(4) and check whether every variable $p_{u,k,v,\\ell}$ equals $x_{u,k} \\cdot x_{v,\\ell}$. If any feasible binary solution violates this equality, the objective can miscompute arc length or reversal counts, and the model would not solve the stated problem.","supporting_citations":[{"cited_title":"4OR 16(3), 295--309 (Sep 2018)","cited_arxiv_id":null,"evidence_quote":"Provides the compact linearization theorem that equations (2) and (3) force $p_{u,k,v,\\ell} = x_{u,k} x_{v,\\ell}$, the correctness basis for the entire objective."},{"cited_title":"u egg, U., von Hanxleden, R.: Compact layered drawings of general directed graphs. In: Hu, Y., N \\","cited_arxiv_id":null,"evidence_quote":"Defines the CGL-W model and EXT formulation that QLA-W is compared against as the prior exact approach for GLP-W."},{"cited_title":"u egg, U., Ehlers, T., Sp \\","cited_arxiv_id":null,"evidence_quote":"Introduces the generalized layering problem (GLP) with arc reversals and total arc-length objectives, the problem class this paper addresses."}],"review_version":1}