Coordinate Partitioning for Difficult Euclidean Max-Sum Diversity Problems

被引:0
|
作者
Spiers, Sandy [1 ,2 ]
Bui, Hoa T. [1 ,2 ]
Loxton, Ryan [1 ,2 ]
机构
[1] Australian Res Council Ctr Transforming Maintenanc, Perth, WA 6102, Australia
[2] Curtin Ctr Optimisat & Decis Sci, Perth, WA 6102, Australia
基金
澳大利亚研究理事会;
关键词
diversity problem; functional decomposition; cutting-plane methods; nonconvex quadratic programming; METRIC-SPACES; P-DISPERSION; ALGORITHMS;
D O I
10.1287/opre.2023.0612
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The Euclidean max-sum diversity problem becomes substantially more difficult as the number of coordinates increases despite the number of decision variables not changing. In this paper, we overcome this complexity by constructing a new set of locations whose squared Euclidean distances equal that of the original. Using squared distances allows the objective function to be decomposed into the sum of pairwise distances within each coordinate. A partition set of the coordinates is then used to enable a functional decomposition of the objective. Each functional component is expected to be simpler than the original and, therefore, easier to approximate via cutting plane methods. We prove the global convergence of our new approach and introduce several partitioning strategies. Furthermore, we show how a principal component analysis of coordinate influence can be conducted with minimal extra computation, the results of which can be used to guide the partitioning process. Extensive numerical results demonstrate the efficiency of the partitioned cutting-plane method with the algorithm able to solve large, 20-coordinate problems of up to 1,000 locations. Finally, we introduce a new class of challenging diversity problems, characterized by locations situated on the edge of a ball.
引用
收藏
页数:23
相关论文
共 50 条
  • [21] A Max-Sum algorithm for training discrete neural networks
    Baldassi, Carlo
    Braunstein, Alfredo
    JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2015,
  • [22] Collision Avoiding Max-Sum for Mobile Sensor Teams
    Pertzovskiy, Arseni
    Zivan, Roie
    Agmon, Noa
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2024, 79 : 1281 - 1311
  • [23] Applying Max-Sum to Asymmetric Distributed Constraint Optimization
    Zivan, Roie
    Parash, Tomer
    Naveh, Yarden
    PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015, : 432 - 438
  • [24] Max-sum equivalence of conditionally dependent random variables
    Jiang, Tao
    Gao, Qingwu
    Wang, Yuebao
    STATISTICS & PROBABILITY LETTERS, 2014, 84 : 60 - 66
  • [25] Collision Avoiding Max-Sum for Mobile Sensor Teams
    Pertzovskiy A.
    Zivan R.
    Agmon N.
    Journal of Artificial Intelligence Research, 2024, 79 : 1281 - 1311
  • [26] Locating multiple facilities using the max-sum objective
    Kalczynski, Pawel
    Drezner, Zvi
    COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 129 : 136 - 143
  • [27] Modeling Flowchart Structure Recognition as a Max-Sum Problem
    Bresler, Martin
    Prusa, Daniel
    Hlavac, Vaclav
    2013 12TH INTERNATIONAL CONFERENCE ON DOCUMENT ANALYSIS AND RECOGNITION (ICDAR), 2013, : 1215 - 1219
  • [28] Max-Sum with Quadtrees for Decentralized Coordination in Continuous Domains
    Troullinos, Dimitrios
    Chalkiadakis, Georgios
    Samoladas, Vasilis
    Papageorgiou, Markos
    PROCEEDINGS OF THE THIRTY-FIRST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2022, 2022, : 518 - 526
  • [29] Explorative Max-sum for Teams of Mobile Sensing Agents
    Yedidsion, Harel
    Zivan, Roie
    Farinelli, Allesandro
    AAMAS'14: PROCEEDINGS OF THE 2014 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, 2014, : 549 - 556
  • [30] Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates
    Borodin, Allan
    Jain, Aadhar
    Lee, Hyun Chul
    Ye, Yuli
    ACM TRANSACTIONS ON ALGORITHMS, 2017, 13 (03)