Linear Ordering Problem: Time for a Change

• URL: http://arxiv.org/abs/2605.31051v2
• Date: Fri, 05 Jun 2026 09:21:29 GMT
• Title: Linear Ordering Problem: Time for a Change
• Abstract summary: The Linear Ordering Problem (LOP) is a fundamental optimization problem with important applications in areas such as economics, social choice, and machine learning.<n>We introduce a novel benchmark suite derived from up-to-date real-world economic data and an algorithmic scheme that leverages state-of-the-art LOP metaheuristics to generate diverse sets of high-quality solutions.<n>Experiments were conducted to report results on the proposed benchmark suite under both the traditional single-solution setting and the newly introduced multi-solution scenario.
• Score: 0.9176056742068811
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Linear Ordering Problem (LOP) is a fundamental combinatorial optimization problem with important applications in areas such as economics, social choice, and machine learning. Its most prominent use is the triangulation of economic input-output tables, which helps identify critical industries in an economy. Most existing algorithms have been evaluated on benchmarks derived from outdated macroeconomic data, which no longer reflect the structure of contemporary economies. Furthermore, LOP instances often exhibit many distinct global optima that can differ substantially from one another, creating challenges for applications that rely on a single solution. To address these limitations, we introduce a novel benchmark suite derived from up-to-date real-world economic data and an algorithmic scheme that leverages state-of-the-art LOP metaheuristics to generate diverse sets of high-quality solutions, together with metrics for assessing both quality and diversity. Experiments were conducted to report results on the proposed benchmark suite under both the traditional single-solution setting and the newly introduced multi-solution scenario

Related papers

• Selective Ensemble Based on Preference-Directed Multi-Objective Bandits [90.75513823660775]
  We formalize a sequential decision problem under partially specified linear preferences.<n>We then propose a preference-directed upper confidence bound (PrefUCB) algorithm.<n> Experiments on large pre-trained model selective ensemble tasks and online asset allocation under institutional mandates validate our method.
  arXiv  Detail & Related papers  (2026-06-20T07:52:46Z)
• Applying a Random-Key Optimizer on Mixed Integer Programs [0.36700088931938835]
  Mixed-Integer Programs (MIPs) are NP-hard optimization models that arise in a broad range of decision-making applications.<n>This paper explores the use of the Random-Key integer (RKO) framework as a flexible, metaheuristic alternative for computing high-quality solutions to MIPs.
  arXiv  Detail & Related papers  (2026-02-25T18:20:03Z)
• Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data [57.996437077411315]
  We study the reasoning behavior of large language models (LLMs) under limited computation budgets.<n>We introduce an anytime reasoning framework and the Anytime Index, a metric that quantifies how effectively solution quality improves as reasoning tokens increase.<n> Experiments on NaturalPlan (Trip), AIME, and GPQA datasets show consistent gains across Grok-3, GPT-oss, GPT-4.1/4o, and LLaMA models.
  arXiv  Detail & Related papers  (2026-01-16T07:09:30Z)
• Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving [18.62245790631018]
  A common challenge in real-time operations is deciding whether to re-solve an optimization problem or continue using an existing solution.<n>We propose a framework called Proximal Policy Optimization with Change Point Detection.
  arXiv  Detail & Related papers  (2025-09-27T19:47:15Z)
• An Identifiable Cost-Aware Causal Decision-Making Framework Using Counterfactual Reasoning [18.324601057882386]
  We propose a minimum-cost causal decision (MiCCD) framework via counterfactual reasoning to solve the necessary cause.<n> Emphasis is placed on making counterfactual reasoning processes identifiable in the presence of mixed anomaly data.<n>MiCCD outperforms conventional methods across multiple metrics, including F1-score, cost efficiency, and ranking quality(nDCG@k values)
  arXiv  Detail & Related papers  (2025-05-13T08:41:45Z)
• Pareto Optimal Algorithmic Recourse in Multi-cost Function [0.44938884406455726]
  algorithmic recourse aims to identify minimal-cost actions to alter an individual features, thereby obtaining a desired outcome.<n>Most current recourse mechanisms use gradient-based methods that assume cost functions are differentiable, often not applicable in real-world scenarios.<n>This work proposes an algorithmic recourse framework that handles nondifferentiable and discrete multi-cost functions.
  arXiv  Detail & Related papers  (2025-02-11T03:16:08Z)
• Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
  This paper approaches the problem of $textitautoformulation$: the automated creation of solver-ready optimization models from natural language problem descriptions.<n>We identify three core challenges of autoformulation: $textit(1)$ the vast, problem-dependent hypothesis space, and $textit(2)$ efficient and diverse exploration of this space under uncertainty.<n>We present a novel method leveraging $textitLarge Language Models$ with $textitMonte-Carlo Tree Search$, exploiting the hierarchical nature of optimization modeling to generate and systematically explore possible formulations
  arXiv  Detail & Related papers  (2024-11-03T20:41:38Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• An Efficient Approach for Solving Expensive Constrained Multiobjective Optimization Problems [0.0]
  An efficient probabilistic selection based constrained multi-objective EA is proposed, referred to as PSCMOEA. It comprises novel elements such as (a) an adaptive search bound identification scheme based on the feasibility and convergence status of evaluated solutions. Numerical experiments are conducted on an extensive range of challenging constrained problems using low evaluation budgets to simulate ECMOPs.
  arXiv  Detail & Related papers  (2024-05-22T02:32:58Z)
• Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime [59.27851754647913]
  Predictive optimization is the precise modeling of many real-world applications, including energy cost-aware scheduling and budget allocation on advertising. We develop a modular framework to benchmark 11 existing PtO/PnO methods on 8 problems, including a new industrial dataset for advertising. Our study shows that PnO approaches are better than PtO on 7 out of 8 benchmarks, but there is no silver bullet found for the specific design choices of PnO.
  arXiv  Detail & Related papers  (2023-11-13T13:19:34Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  Energy systems optimization problems are complex due to strongly non-linear system behavior and multiple competing objectives. In some cases, proposed optimal solutions need to obey explicit input constraints related to physical properties or safety-critical operating conditions. This paper proposes a novel data-driven strategy using tree ensembles for constrained multi-objective optimization of black-box problems.
  arXiv  Detail & Related papers  (2021-11-04T20:18:55Z)
• Solving Multistage Stochastic Linear Programming via Regularized Linear Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
  We propose a novel regularization scheme for linear decision rules (LDR) based on the AdaSO (adaptive least absolute shrinkage and selection operator) Experiments show that the overfit threat is non-negligible when using the classical non-regularized LDR to solve MSLP. For the LHDP problem, our analysis highlights the following benefits of the proposed framework in comparison to the non-regularized benchmark.
  arXiv  Detail & Related papers  (2021-10-07T02:36:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.