Improving Solution Quality of Bounded Max-Sum Algorithm to Solve DCOPs involving Hard and Soft Constraints

• URL: http://arxiv.org/abs/2012.01369v1
• Date: Wed, 2 Dec 2020 18:10:14 GMT
• Title: Improving Solution Quality of Bounded Max-Sum Algorithm to Solve DCOPs involving Hard and Soft Constraints
• Authors: Md. Musfiqur Rahman, Mashrur Rashik, Md. Mamun-or-Rashid and Md. Mosaddek Khan
• Abstract summary: Bounded Max-Sum (BMS) is a message-passing algorithm that provides approximation solution to a specific form of de-centralized coordination problems. In particular, BMS algorithm is able to solve problems of this type having large search space at the expense of low computational cost.
• Score: 3.0969191504482243
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Bounded Max-Sum (BMS) is a message-passing algorithm that provides approximation solution to a specific form of de-centralized coordination problems, namely Distributed Constrained Optimization Problems (DCOPs). In particular, BMS algorithm is able to solve problems of this type having large search space at the expense of low computational cost. Notably, the traditional DCOP formulation does not consider those constraints that must be satisfied(also known as hard constraints), rather it concentrates only on soft constraints. Hence, although the presence of both types of constraints are observed in a number of real-world applications, the BMS algorithm does not actively capitalize on the hard constraints. To address this issue, we tailor BMS in such a way that can deal with DCOPs having both type constraints. In so doing, our approach improves the solution quality of the algorithm. The empirical results exhibit a marked improvement in the quality of the solutions of large DCOPs.

Related papers

• Evolutionary Algorithm with Detection Region Method for Constrained Multi-Objective Problems with Binary Constraints [9.764702512419946]
  This paper proposes a novel algorithm called DRMCMO based on the detection region method. In DRMCMO, detection regions dynamic monitor feasible solutions to enhance convergence, helping the population escape local optima. We have modified three existing test suites to serve as benchmark test problems for CMOPs with binary constraints.
  arXiv  Detail & Related papers  (2024-11-13T08:39:04Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• Solution to Advanced Manufacturing Process Problems using Cohort Intelligence Algorithm with Improved Constraint Handling Approaches [0.07989135005592125]
  Cohort Intelligence (CI) algorithm is a socio inspired optimization technique which is successfully applied for solving several unconstrained & constrained real-world problems from the domains such as design, manufacturing, supply chain, healthcare, etc.
  arXiv  Detail & Related papers  (2023-10-16T05:40:23Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  This paper presents an algorithm to solve the Soft k-Means problem globally. A new model, named Minimal Volume Soft kMeans (MVSkM), is proposed to address solutions non-uniqueness issue.
  arXiv  Detail & Related papers  (2022-12-07T12:06:55Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Optimal Solutions for Joint Beamforming and Antenna Selection: From Branch and Bound to Machine Learning [47.10315221141495]
  This work revisits the joint beamforming (BF) and antenna selection (AS) problem, as well as its robust beamforming (RBF) version under imperfect channel state information (CSI) The main contribution of this work is threefold. First, an effective it branch and bound (B&B) framework for solving the problems of interest is proposed. Second, to expedite the potentially costly B&B algorithm, a machine learning (ML)-based scheme is proposed to help skip intermediate states of the B&B search tree.
  arXiv  Detail & Related papers  (2022-06-11T17:43:02Z)
• A Particle Swarm Inspired Approach for Continuous Distributed Constraint Optimization Problems [7.512486812178571]
  Continuous DCOPs can explicitly model problems with continuous variables. State-of-the-art approaches for solving C-DCOPs experience either onerous memory or computation overhead. We propose a new C-DCOP algorithm, namely Particle Swarm Optimization Based C-DCOP (PCD), which is inspired by Particle Swarm Optimization (PSO)
  arXiv  Detail & Related papers  (2020-10-20T11:04:47Z)
• On Population-Based Algorithms for Distributed Constraint Optimization Problems [12.21350091202884]
  We study an emerging class of incomplete algorithms that are broadly termed as population-based algorithms. Our first approach, Anytime Evolutionary DCOP or AED, exploits evolutionary optimization meta-heuristics to solve DCOPs. While in our second contribution, we show that population-based approaches can be combined with local search approaches.
  arXiv  Detail & Related papers  (2020-09-02T06:39:30Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max optimization algorithms encounter problems far greater because of the existence of periodic cycles and similar phenomena. We show that there exist algorithms that do not attract any points of the problem. We illustrate such challenges in simple to almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost
  arXiv  Detail & Related papers  (2020-06-16T10:49:27Z)
• A Constraint Driven Solution Model for Discrete Domains with a Case Study of Exam Timetabling Problems [6.788217433800101]
  A variation of Intelligent constraint handling evolutionary algorithm (ICHEA) has been demonstrated to solve benchmark exam timetabling problems. ICHEA first uses its inter-marriage crossover operator to satisfy all the given constraints incrementally and then uses combination of traditional and enhanced operators to optimize the solution.
  arXiv  Detail & Related papers  (2020-02-08T06:53:38Z)

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.