New Core-Guided and Hitting Set Algorithms for Multi-Objective Combinatorial Optimization

• URL: http://arxiv.org/abs/2204.10856v1
• Date: Fri, 22 Apr 2022 09:46:44 GMT
• Title: New Core-Guided and Hitting Set Algorithms for Multi-Objective Combinatorial Optimization
• Authors: Jo\~ao Cortes, In\^es Lynce, Vasco Manquinho
• Abstract summary: We present two novel unsatisfiability-based algorithms for Multi-Objective Combinatorial Optimization. The first is a core-guided MOCO solver, the second is a hitting set-based MOCO solver. Experimental results show that our new unsatisfiability-based algorithms can outperform state-of-the-art SAT-based algorithms for MOCO.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In the last decade, a plethora of algorithms for single-objective Boolean optimization has been proposed that rely on the iterative usage of a highly effective Propositional Satisfiability (SAT) solver. But the use of SAT solvers in Multi-Objective Combinatorial Optimization (MOCO) algorithms is still scarce. Due to this shortage of efficient tools for MOCO, many real-world applications formulated as multi-objective are simplified to single-objective, using either a linear combination or a lexicographic ordering of the objective functions to optimize. In this paper, we extend the state of the art of MOCO solvers with two novel unsatisfiability-based algorithms. The first is a core-guided MOCO solver. The second is a hitting set-based MOCO solver. Experimental results obtained in a wide range of benchmark instances show that our new unsatisfiability-based algorithms can outperform state-of-the-art SAT-based algorithms for MOCO.

Related papers

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• Effective anytime algorithm for multiobjective combinatorial optimization problems [3.2061579211871383]
  A set of efficient solutions that are well-spread in the objective space is preferred to provide the decision maker with a great variety of solutions. We propose a new exact algorithm for multiobjective optimization combining three novel ideas to enhance the anytime behavior.
  arXiv  Detail & Related papers  (2024-02-06T11:53:44Z)
• A First-Order Multi-Gradient Algorithm for Multi-Objective Bi-Level Optimization [7.097069899573992]
  We study the Multi-Objective Bi-Level Optimization (MOBLO) problem. Existing gradient-based MOBLO algorithms need to compute the Hessian matrix. We propose an efficient first-order multi-gradient method for MOBLO, called FORUM.
  arXiv  Detail & Related papers  (2024-01-17T15:03:37Z)
• Improving Performance Insensitivity of Large-scale Multiobjective Optimization via Monte Carlo Tree Search [7.34812867861951]
  We propose an evolutionary algorithm for solving large-scale multiobjective optimization problems based on Monte Carlo tree search. The proposed method samples the decision variables to construct new nodes on the Monte Carlo tree for optimization and evaluation. It selects nodes with good evaluation for further search to reduce the performance sensitivity caused by large-scale decision variables.
  arXiv  Detail & Related papers  (2023-04-08T17:15:49Z)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  We study the effectiveness of various ZO optimization methods for optimizing molecular objectives. We show the advantages of ZO sign-based gradient descent (ZO-signGD) We demonstrate the potential effectiveness of ZO optimization methods on widely used benchmark tasks from the Guacamol suite.
  arXiv  Detail & Related papers  (2022-10-27T01:58:10Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• A Simple Evolutionary Algorithm for Multi-modal Multi-objective Optimization [0.0]
  We introduce a steady-state evolutionary algorithm for solving multi-modal, multi-objective optimization problems (MMOPs) We report its performance on 21 MMOPs from various test suites that are widely used for benchmarking using a low computational budget of 1000 function evaluations.
  arXiv  Detail & Related papers  (2022-01-18T03:31:11Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations. We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
  arXiv  Detail & Related papers  (2021-10-13T19:36:50Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Decomposition in Decision and Objective Space for Multi-Modal Multi-Objective Optimization [15.681236469530397]
  Multi-modal multi-objective optimization problems (MMMOPs) have multiple subsets within the Pareto-optimal Set. Prevalent multi-objective evolutionary algorithms are not purely designed to search for multiple solution subsets, whereas, algorithms designed for MMMOPs demonstrate degraded performance in the objective space. This motivates the design of better algorithms for addressing MMMOPs.
  arXiv  Detail & Related papers  (2020-06-04T03:18:47Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.