A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives

• URL: http://arxiv.org/abs/2505.22244v1
• Date: Wed, 28 May 2025 11:26:14 GMT
• Title: A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives
• Authors: Yaron Halle, Ariel Felner, Sven Koenig, Oren Salzman,
• Abstract summary: We consider the bi-objective shortest-path (BOSP) problem in the presence of correlated objectives.<n>BOSP is generally computationally challenging as the size of the search space is exponential in the number of objective functions and the graph size.<n>We propose an efficient algorithm that reduces the search effort in the presence of correlated objectives.
• Score: 21.108406629056173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The bi-objective shortest-path (BOSP) problem seeks to find paths between start and target vertices of a graph while optimizing two conflicting objective functions. We consider the BOSP problem in the presence of correlated objectives. Such correlations often occur in real-world settings such as road networks, where optimizing two positively correlated objectives, such as travel time and fuel consumption, is common. BOSP is generally computationally challenging as the size of the search space is exponential in the number of objective functions and the graph size. Bounded sub-optimal BOSP solvers such as A*pex alleviate this complexity by approximating the Pareto-optimal solution set rather than computing it exactly (given a user-provided approximation factor). As the correlation between objective functions increases, smaller approximation factors are sufficient for collapsing the entire Pareto-optimal set into a single solution. We leverage this insight to propose an efficient algorithm that reduces the search effort in the presence of correlated objectives. Our approach for computing approximations of the entire Pareto-optimal set is inspired by graph-clustering algorithms. It uses a preprocessing phase to identify correlated clusters within a graph and to generate a new graph representation. This allows a natural generalization of A*pex to run up to five times faster on DIMACS dataset instances, a standard benchmark in the field. To the best of our knowledge, this is the first algorithm proposed that efficiently and effectively exploits correlations in the context of bi-objective search while providing theoretical guarantees on solution quality.

Related papers

• Exact and Heuristic Algorithms for Constrained Biclustering [0.0]
  Biclustering, also known as co-clustering or two-way clustering, simultaneously partitions the rows and columns of a data matrix to reveal submatrices with coherent patterns.<n>We study constrained biclustering with pairwise constraints, namely must-link and cannot-link constraints, which specify whether objects should belong to the same or different biclusters.
  arXiv  Detail & Related papers  (2025-08-07T15:29:22Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
  Pathwise methods allow to efficiently compute the full path for penalized estimators.<n>We apply these algorithms to the penalized estimation of processes observed at discrete times.
  arXiv  Detail & Related papers  (2024-12-05T10:38:29Z)
• Graph Convolutional Branch and Bound [1.8966938152549224]
  We propose using neural networks to learn informatives-most notably, an optimality score that estimates a solution's proximity to the optimum.<n>This score is used to evaluate nodes within a branch-and-bound framework, enabling a more efficient of the solution space.
  arXiv  Detail & Related papers  (2024-06-05T09:42:43Z)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  In this paper, we show a natural connection between non-dominated solutions and the extreme quantile of the joint cumulative distribution function. Motivated by this link, we propose the Pareto-compliant CDF indicator and the associated acquisition function, BOtied. Our experiments on a variety of synthetic and real-world problems demonstrate that BOtied outperforms state-of-the-art MOBO acquisition functions.
  arXiv  Detail & Related papers  (2023-06-01T04:50:06Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  Facility location problems (FLPs) are a typical class of NP-hard optimization problems, which are widely seen in the supply chain and logistics. In this paper, we consider the multi-objective facility location problem (MO-FLP) that simultaneously minimizes the overall cost and maximizes the system reliability. Two graph neural networks are constructed to learn the implicit graph representation on nodes and edges.
  arXiv  Detail & Related papers  (2022-10-27T07:15:55Z)
• Arch-Graph: Acyclic Architecture Relation Predictor for Task-Transferable Neural Architecture Search [96.31315520244605]
  Arch-Graph is a transferable NAS method that predicts task-specific optimal architectures. We show Arch-Graph's transferability and high sample efficiency across numerous tasks. It is able to find top 0.16% and 0.29% architectures on average on two search spaces under the budget of only 50 models.
  arXiv  Detail & Related papers  (2022-04-12T16:46:06Z)
• Effective and efficient structure learning with pruning and model averaging strategies [9.023722579074734]
  This paper describes an approximate BN structure learning algorithm that combines two novel strategies with hill-climbing search. The algorithm starts by pruning the search space graphs, where the pruning strategy can be viewed as an aggressive version of the pruning strategies. It then performs model averaging in the hill-climbing search process and moves to the neighbouring graph that maximises the objective function.
  arXiv  Detail & Related papers  (2021-12-01T10:35:34Z)
• The Minimax Complexity of Distributed Optimization [0.0]
  I present the "graph oracle model", an extension of the classic oracle framework that can be applied to distributed optimization. I focus on the specific case of the "intermittent communication setting" I analyze the theoretical properties of the popular Local Descent (SGD) algorithm in convex setting.
  arXiv  Detail & Related papers  (2021-09-01T15:18:33Z)
• Many Objective Bayesian Optimization [0.0]
  Multi-objective Bayesian optimization (MOBO) is a set of methods that has been successfully applied for the simultaneous optimization of black-boxes. In particular, MOBO methods have problems when the number of objectives in a multi-objective optimization problem are 3 or more, which is the many objective setting. We show empirical evidence in a set of toy, synthetic, benchmark and real experiments that GPs predictive distributions of the effectiveness of the metric and the algorithm.
  arXiv  Detail & Related papers  (2021-07-08T21:57:07Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Balanced Order Batching with Task-Oriented Graph Clustering [28.05598654297136]
  We propose an end-to-end learning and optimization framework named Balanced Task- Clustering Network (BTOGCN) to solve the Balanced Order Estimation Problem (BOBP) BOBP arises from the process of picking in Cainiao, the largest logistics platform in China.
  arXiv  Detail & Related papers  (2020-08-19T08:42:50Z)

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.