Clustered Orienteering Problem with Subgroups

• URL: http://arxiv.org/abs/2312.16154v2
• Date: Wed, 27 Dec 2023 16:24:00 GMT
• Title: Clustered Orienteering Problem with Subgroups
• Authors: Luciano E. Almeida and Douglas G. Macharet
• Abstract summary: Clustered Orienteering Problem with Subgroups (COPS) We show that our new formulation has the ability to model and solve two previous well-known variants.
• Score: 6.961946145048321
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces an extension to the Orienteering Problem (OP), called Clustered Orienteering Problem with Subgroups (COPS). In this variant, nodes are arranged into subgroups, and the subgroups are organized into clusters. A reward is associated with each subgroup and is gained only if all of its nodes are visited; however, at most one subgroup can be visited per cluster. The objective is to maximize the total collected reward while attaining a travel budget. We show that our new formulation has the ability to model and solve two previous well-known variants, the Clustered Orienteering Problem (COP) and the Set Orienteering Problem (SOP), in addition to other scenarios introduced here. An Integer Linear Programming (ILP) formulation and a Tabu Search-based heuristic are proposed to solve the problem. Experimental results indicate that the ILP method can yield optimal solutions at the cost of time, whereas the metaheuristic produces comparable solutions within a more reasonable computational cost.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Using Constraints to Discover Sparse and Alternative Subgroup Descriptions [0.0]
  Subgroup-discovery methods allow users to obtain simple descriptions of interesting regions in a dataset. We focus on two types of constraints: First, we limit the number of features used in subgroup descriptions, making the latter sparse. Second, we propose the novel optimization problem of finding alternative subgroup descriptions, which cover a similar set of data objects as a given subgroup but use different features.
  arXiv  Detail & Related papers  (2024-06-03T15:10:01Z)
• An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
  We present a tailored branch-and-cut algorithm for biclustering problems. We show that the proposed algorithm can solve instances 20 times larger than those handled by general-purpose solvers.
  arXiv  Detail & Related papers  (2024-03-17T21:43:19Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  We propose a family of algorithms for personalized federated learning with locally convex user costs. The proposed framework is based on a generalization of convex clustering in which the differences between different users' models are penalized.
  arXiv  Detail & Related papers  (2022-02-01T19:25:31Z)
• Interpretable Clustering via Multi-Polytope Machines [12.69310440882225]
  We propose a novel approach for interpretable clustering that both clusters data points and constructs polytopes around the discovered clusters to explain them. We benchmark our approach on a suite of synthetic and real world clustering problems, where our algorithm outperforms state of the art interpretable and non-interpretable clustering algorithms.
  arXiv  Detail & Related papers  (2021-12-10T16:36:32Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Robust subgroup discovery [0.2578242050187029]
  We formalize the problem of optimal robust subgroup discovery using the Minimum Description Length principle. We propose RSD, a greedy greedy that finds good subgroup lists and guarantees that the most significant subgroup is added in each iteration. We empirically show on 54 datasets that RSD outperforms previous subgroup set discovery methods in terms of quality and subgroup list size.
  arXiv  Detail & Related papers  (2021-03-25T09:04:13Z)
• A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group [29.714239628405515]
  We consider the class of synchronization problems which the group is a closed subgroup. We propose a unified approach for solving this class of problems. We show that our approach outperforms existing approaches.
  arXiv  Detail & Related papers  (2020-09-16T07:25: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.