{"id":"776b2dd6-8b8f-4b2f-a42d-9313903f7b2c","arxiv_id":"1908.02376","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Quantile inverse optimization trims a fraction of noisy observations to infer linear objective functions that are both inverse-stable and forward-stable.","lead":"This paper designs a way to recover an optimization model's objective from noisy decisions by ignoring a chosen fraction of the worst-fitting observations. The quantile-based inverse linear programming method produces objective functions and recommended decisions that are more stable under outliers and small data shifts than earlier approaches.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 4's forward-stability guarantee rests on a false implication: n selected facets need not form a unique optimal solution, so the tau-bound can fail in degenerate polytopes.","rationale":"The reader's weakest_assumption identifies exactly this point: Proposition 4 assumes the n selected facets bound a unique optimal point, and this can fail for degenerate polytopes or unreachable selections. My analysis sharpens the concern into a formal counterexample. The paper's central forward-stability claim and the design of the MQIO surrogate objective (maximizing sum_i v_i) both depend on Proposition 4. Since the proof's step from |I|=n to a singleton X*(c) is invalid without linear independence, the theoretical guarantee is not established. This is not a merely cosmetic gap: network-flow LPs (including the transshipment application in Section 5.4) are typically degenerate, so the failure mode is practically relevant. That said, the issue is fixable by adding a simplicity/nondegeneracy assumption or by restating the forward-stability guarantee as existence of an optimal solution within tau (which is true because each kept point's perturbed version lies in the optimal face). The rest of the paper—MIP characterization, biclique connection, heuristics, and experiments—does not obviously depend on the false singleton assertion. Therefore the appropriate outcome remains conditional acceptance with a major revision to Proposition 4, matching the reader's verdict. The secondary concern about the exact algorithm's u*_1=1 condition is also valid but is less load-bearing, since it is explicitly checked post hoc and the algorithm is described primarily as a practical exact/heuristic method.","tokens_in":37302,"tokens_out":18586,"duration_ms":208082,"concrete_test":"Verify the explicit counterexample analytically: for the 4D polytope P described above, set K=1, hat x=(0,0,0,0), tau=0.1, theta=1, and construct v with v_i=1 exactly for facets x1=0, x2=0, x3=0, x1=x2, and v_i=0 otherwise, with epsilon_1=0. Confirm this satisfies constraints (6b)-(6e). Then choose c = e1+e2+e3+(1,-1,0,0)/sqrt(2) (after normalizing), solve FO(c), and observe X*(c) = {x : x1=x2=x3=0, 0<=x4<=1}. Compute max_{x in X*(c)} ||x - hat x||_inf = 1 > tau, which directly disproves Proposition 4. If the authors maintain Proposition 4, they should identify the missing condition (e.g., linear independence of selected normals) and supply a corrected proof under that assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 4 (Section 3.2) is false as stated. Its proof says X*(\\bar c) is a singleton 'because X is an n-dimensional polytope and |I|=n.' In a general polytope, n facets can intersect in a positive-dimensional face unless the normals are linearly independent; the paper never assumes simplicity. MQIO maximizes the number of selected facets (sum_i v_i) without enforcing independence, so an optimal solution can select n facets whose intersection is an edge or higher-dimensional face. Then FO(\\bar c) has multiple optimal solutions spread over that face, and the worst-case distance in the forward-stability measure (4) can exceed tau. Concrete counterexample in R^4: let P = {x1>=0, x2>=0, x3>=0, x1-x2>=0, x2-x3>=0, x1+x2+x3<=1, 0<=x4<=1}, with normalized normals. For data point (0,0,0,0), tau=0.1, theta=1, the facets x1=0, x2=0, x3=0, x1=x2 are all active at the point and selecting them is feasible for MIP (6) with sum v_i = 4 = n. Their intersection is the edge x1=x2=x3=0, 0<=x4<=1. Any strict conic combination of the four normals has zero x4 coefficient and positive coefficients on x1,x2,x3, so X*(c) is exactly that entire edge. The optimal point (0,0,0,1) is distance 1 from the data, contradicting the claimed tau bound. The result requires an extra nondegeneracy or linear-independence condition, or must be weakened to an existence guarantee rather than a worst-case guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a quantile-based inverse linear programming (QIO) method and its mixed-integer reformulation (MQIO) to address instability of inverse LP under data noise and outliers. It formalizes inverse and forward stability measures, characterizes the set of inverse-feasible cost vectors through conic combinations of constraint normals (Theorem 1), establishes a connection to biclique problems, and proposes an exact algorithm and two heuristics. Numerical experiments are reported on randomly generated LPs, a diet recommendation problem, and a transshipment problem, with comparisons against a previous inverse LP model.","tokens_in":37669,"tokens_out":17549,"duration_ms":178748,"significance":"The quantile idea is a reasonable adaptation of robust regression to inverse LP, and the biclique connection provides a useful algorithmic perspective. The paper contains several formal propositions and a reproducible algorithmic framework, which are strengths. However, the central forward-stability guarantee (Proposition 4) is false as stated, which undermines the paper's main claim of providing forward-stable cost vectors. The inverse-stability monotonicity (Proposition 1) is largely a direct consequence of the model's definition rather than an independent property, and the numerical evaluation is entirely synthetic. If the theoretical gaps are corrected, the framework could be a valuable contribution to robust inverse optimization.","major_comments":[{"comment":"The inverse-stability monotonicity result is a direct consequence of the fact that decreasing θ enlarges the feasible set of cost vectors, as the proof in Appendix C demonstrates via set inclusion. While mathematically correct, this does not by itself establish that the MQIO model is 'more stable' than the previous inverse LP model in a substantive sense; the reported improvement in inverse stability is partially built into the model definition. The numerical experiments in Section 5.2.2 are the appropriate evidence, and the paper should present Proposition 1 accordingly.","section":"Section 3.1, Proposition 1"}],"minor_comments":[{"comment":"The cost vector is written as 0.5a1 + 0.5a1; this appears to be a typo and should read 0.5a1 + 0.5a2.","section":"Example 4 (page 19)"},{"comment":"The symbol X is used both for the feasible region of the forward problem and for the shifted dataset in the definitions of inverse and forward stability (e.g., in equations (3) and (4)). This creates notational confusion; a different symbol for the dataset, such as \\mathcal{X}, would help.","section":"Section 2.4"},{"comment":"The use of an infinitesimal constant σ in \\bar{τ}=τ+σ is informal; a limiting argument with σ followed by σ↓0 would be more rigorous.","section":"Appendix C, proof of Proposition 3"},{"comment":"Several rows appear to have a missing objective value for the ˜D-Alg-Heuristic column (for example, the row for (n,m,K)=(50,300,500) with τ=3.0). Please check the table entries for completeness and alignment.","section":"Table 1"},{"comment":"The forward-stability experiment samples 50 cost vectors from each cone C_h rather than computing the worst-case distance over the entire cone. The claim that the distance is 'eventually within the threshold' should be framed as an empirical observation, not a worst-case guarantee.","section":"Section 5.2.1"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is Proposition 4: the forward-stability guarantee is false in degenerate polytopes, and this is a load-bearing error for the central claim. If the authors can correct the statement (e.g., by adding a nondegeneracy assumption or converting it to an existence guarantee), the contribution would be substantially more credible. Additionally, the exactness condition of Algorithm 2 and the largely definitional nature of Proposition 1 should be addressed in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real news here is the quantile-trimming idea applied to inverse LP, plus the biclique connection that yields practical algorithms. That combination is new relative to the cited inverse optimization literature, and the paper deserves a serious referee.\n\nWhat is solid: Theorem 1's MIP equivalence is coherent, Proposition 2's structure result is correct, and the reduction to a maximum subset intersection / biclique problem is a real contribution. The exact and heuristic algorithms are sensible, and the computational experiments show they beat directly solving the large MIP. The inverse stability discussion is thoughtful, and the numerical trend that more selected facets gives better forward stability is plausible.\n\nNow the soft spots, in proportion. Proposition 4 is the load-bearing forward-stability claim, and it is false as stated. The proof asserts that if n facets are selected, X*(c) is a singleton because X is an n-dimensional polytope. That only holds when the selected normals are linearly independent (simplicity). MQIO only maximizes the count of selected facets; it does not enforce independence. A feasible solution can select n facets whose intersection is an edge or higher-dimensional face, and then a strict conic combination of those normals has that entire face as its optimal set, so the worst-case distance to the data can exceed tau. The stress-test counterexample in R^4 is valid. This is not a cosmetic gap: it breaks the paper's headline guarantee that the inverse model produces forward solutions within tau of the kept data. The fix is either to add a nondegeneracy or linear-independence condition (e.g., restrict to simple polytopes or enforce independent columns), or to weaken the statement to an existence guarantee for some point in the optimal face. That is fixable, but it must be done before the paper is accepted.\n\nTwo smaller issues: Proposition 8's exactness requires u*_1 = 1, checked only post hoc; the authors acknowledge this but it limits the practical exactness claim. Also, the inverse stability measure is defined and bounded under a pointwise-shift noise model, which is narrower than the general notion the introduction promises. No code or data are released, and the diet and transshipment experiments are illustrative rather than rigorous.\n\nWho is this for? Researchers working on data-driven inverse LP and robust optimization variants of inverse problems. They will want the quantile formulation and the biclique algorithms even if they ignore the flawed forward-stability proof.\n\nRecommendation: send it to peer review, with a clear instruction that Proposition 4 must be repaired or honestly weakened. I would not cite the forward-stability guarantee until that happens, but the algorithmic and modeling contributions are worth engaging with seriously.","headline":"A genuinely new quantile-based inverse LP framework with clever biclique algorithms, but Proposition 4's forward-stability guarantee is false as stated and the numerical support is thin.","tokens_in":38173,"tokens_out":1276,"would_cite":false,"duration_ms":18144,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C05","90C11","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Quantile inverse optimization infers LP objective functions that stay stable under noisy, outlier-laden data, with guarantees that kept observations remain within a prescribed distance of the forward-optimal solution.","keywords":["inverse optimization","inverse linear programming","quantile regression","mixed-integer programming","biclique","stability measures","online learning","robust estimation"],"falsifier":"Take a two-dimensional forward polytope and place all observations near a single facet, with τ small enough that no other facet can be activated; then the MQIO optimum selects fewer than n facets, Proposition 4's guaranteed forward-stability bound does not apply, and the inferred cost vector can produce a forward solution far from the data. Similarly, reorder any dataset so that an outlier is first; if the exact algorithm then reports u*_1 = 0, its completeness guarantee fails unless a different seeding order is used.","tokens_in":37086,"feed_emoji":"🎯","tokens_out":7303,"duration_ms":67625,"temperature":0.7,"pith_summary":"Inverse linear programming infers the objective function of an optimization problem from observed decisions, but the cost vectors produced by standard methods can swing wildly when the observations are noisy or contain outliers. This paper introduces quantile inverse optimization (QIO), which keeps only the fraction θ of observations whose optimality error is no larger than a threshold τ and infers cost vectors from that subset. The paper defines formal inverse-stability and forward-stability measures, shows QIO is at least as stable as previous inverse-LP models, and proposes a mixed-integer formulation (MQIO) that maximizes the number of polytope facets spanned by the inferred cost vector. That maximum is a tractable proxy for forward stability: when n facets are selected, the resulting cost vector has a unique forward optimum within distance τ of every kept data point. The authors also connect MQIO to biclique problems, give an exact algorithm and heuristics, and demonstrate the method on diet recommendation and transshipment problems.","feed_headline":"Quantile inverse LP finds stable cost vectors despite noisy data","feed_subtitle":"It drops a chosen share of observations and keeps inferred objectives from lurching at every outlier.","key_machinery":"The central machinery is the pair of binary variables (v for facets, u for data points) together with the quantile threshold τ and fraction θ. Constraint (6b) forces any kept observation to lie on all selected facets, and (6c) bounds its perturbation by τ; maximizing Σ v_i then selects the widest facet set consistent with the data. The biclique view—rows are observations, columns are facet normals, and feasible solutions are all-one submatrices with at least ⌈θK⌉ rows—is what lets the authors split the large MIP into per-observation feasibility checks and a smaller clique MIP, and it is also the route to the NP-hardness proof.","core_discovery":"The central discovery is a characterization of all inverse-feasible cost vectors for a quantile threshold: a cost vector c makes at least ⌈θK⌉ observations within τ of optimality if and only if it lies in the conic hull of the facet normals ai whose indicator variables are 1 in a feasible solution to the mixed-integer feasibility problem (6), with the data-subset indicators u marking the kept observations (Theorem 1). Building on this, Proposition 4 shows that if a feasible solution activates exactly n facets, then any strict conic combination c of those normals makes the forward LP have a unique optimal solution, and that solution is within τ of every kept data point. The paper's working strategy is therefore to maximize the number of activated facets (the MQIO objective), which Proposition 5 shows cannot hurt either forward or inverse stability, and which numerical experiments confirm brings forward solutions close to the trusted data.","pith_inferences":["The same biclique machinery could be adapted to inverse problems over other polyhedral sets—e.g., inverse conic or mixed-integer programs—by replacing facet normals with the appropriate extreme rays, though the uniqueness guarantee would need rederivation.","The exact algorithm's condition that the first data point be kept (u*_1 = 1) is only checked after the run; a natural robustness upgrade would be to run the seed selection on several candidate points in parallel and take the best, which the paper's own cut-based enumeration already hints at.","The forward-stability bound is stated for the kept subset; a practitioner could treat the unkept fraction as outliers and validate the chosen τ on held-out data, giving a cross-validated way to set τ.","Since the inverse-stability lower bound grows as θ shrinks, one could combine the method with a breakdown-point argument to choose θ adaptively—matching the paper's suggested interpretation of θ as an outlier fraction."],"forward_implications":["If MQIO's optimal solution activates all n facets, every cost vector in the returned conic set yields a unique forward solution within distance τ of all retained data points—the forward-stability guarantee is exact, not heuristic.","Lowering θ—allowing the model to discard more outliers—monotonically increases inverse stability, so the user can trade fit against tolerance by tuning one parameter.","The QIO feasible set contains the cost vectors of the standard inverse-LP model (2) for a suitable τ, so the new method is a strict generalization rather than a replacement.","The online-learning extension converges to a cost-vector set that includes the true cost vector in the transshipment experiments, suggesting the method can track drifting preferences.","Because maximizing the number of selected facets improves both stability measures, the MQIO objective is a principled surrogate for the hard-to-compute forward-stability measure."],"supporting_citations":[{"why":"supplies the inverse-LP model with noisy data (formulation (2)) whose instability motivates the quantile approach.","marker":"Aswani et al. (2018)"},{"why":"establishes the inverse-LP/regression analogy and the closed-form solution with cost vectors orthogonal to a facet, which QIO exploits.","marker":"Chan et al. (2019)"},{"why":"introduces least-median-of-squares regression, the trimming idea behind quantile-based outlier tolerance.","marker":"Rousseeuw (1984)"},{"why":"formulates least-quantile regression, the template for the θ-quantile optimality-error objective.","marker":"Bertsimas and Mazumder (2014)"},{"why":"provides an efficient exact algorithm for the previous inverse-LP model used as a comparison point in the stability experiments.","marker":"Babier et al. (2018)"},{"why":"frames maximum one-sided edge cardinality biclique problems, used for the NP-hardness argument and algorithm design.","marker":"Dawande et al. (2001)"},{"why":"proves the maximum κ-subset intersection problem is NP-hard, the target of the reduction in Proposition 6.","marker":"Xavier (2012)"},{"why":"gives the uniqueness-of-LP-solution result for n active constraints, which underlies Proposition 4's uniqueness claim.","marker":"Mangasarian (1979)"},{"why":"characterizes the inverse-feasible region of an LP, grounding the conic-combination structure of the cost vectors.","marker":"Tavaslıoğlu et al. (2018)"}],"fun_headline_variants":["Quantile inverse LP stabilizes cost estimation under noise","Drop outliers, keep stable cost vectors in inverse LP","Stable inverse LP via quantile trimming of data","Inverse LP that ignores a fraction of noisy data","Quantile trimming yields stable inverse LP solutions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The stability and exactness guarantees depend on the MQIO solution selecting exactly n facets that bound a unique point, and on the first data point being one of the kept points; on degenerate or highly noisy datasets those conditions may not hold.","fun_headline_variants_meta":{"raw":{"variants":["Quantile inverse LP stabilizes cost estimation under noise","Drop outliers, keep stable cost vectors in inverse LP","Stable inverse LP via quantile trimming of data","Inverse LP that ignores a fraction of noisy data","Quantile trimming yields stable inverse LP solutions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000442,"raw_usage":{"total_tokens":2206,"prompt_tokens":878,"completion_tokens":1328,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":494,"completion_tokens_details":{"reasoning_tokens":1254}},"tokens_in":494,"tokens_out":1328,"duration_ms":10384,"temperature":1.0,"reasoning_tokens":1254,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:47:14.508505+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-dimensional forward polytope and place all observations near a single facet, with τ small enough that no other facet can be activated; then the MQIO optimum selects fewer than n facets, Proposition 4's guaranteed forward-stability bound does not apply, and the inferred cost vector can produce a forward solution far from the data. Similarly, reorder any dataset so that an outlier is first; if the exact algorithm then reports u*_1 = 0, its completeness guarantee fails unless a different seeding order is used.","supporting_citations":[{"cited_title":"Management Science 65(3):680--695","cited_arxiv_id":null,"evidence_quote":"establishes the inverse-LP/regression analogy and the closed-form solution with cost vectors orthogonal to a facet, which QIO exploits."},{"cited_title":"Journal of the American Statistical Association 79(388):871--880","cited_arxiv_id":null,"evidence_quote":"introduces least-median-of-squares regression, the trimming idea behind quantile-based outlier tolerance."},{"cited_title":"The Annals of Statistics 42(6):2494--2525","cited_arxiv_id":null,"evidence_quote":"formulates least-quantile regression, the template for the θ-quantile optimality-error objective."},{"cited_title":"An Ensemble Learning Framework for Model Fitting and Evaluation in Inverse Linear Optimization","cited_arxiv_id":"1804.04576","evidence_quote":"provides an efficient exact algorithm for the previous inverse-LP model used as a comparison point in the stability experiments."},{"cited_title":"Journal of Algorithms 41(2):388--403","cited_arxiv_id":null,"evidence_quote":"frames maximum one-sided edge cardinality biclique problems, used for the NP-hardness argument and algorithm design."},{"cited_title":"Information Processing Letters 112(12):471--472","cited_arxiv_id":null,"evidence_quote":"proves the maximum κ-subset intersection problem is NP-hard, the target of the reduction in Proposition 6."},{"cited_title":"Linear Algebra and its Applications 25:151--162","cited_arxiv_id":null,"evidence_quote":"gives the uniqueness-of-LP-solution result for n active constraints, which underlies Proposition 4's uniqueness claim."}],"review_version":1}