Bi-Objective Discrete Graphical Model Optimization - Unité de Mathématiques et Informatique Appliquées de Toulouse Accéder directement au contenu
Communication Dans Un Congrès Année : 2024

Bi-Objective Discrete Graphical Model Optimization

Résumé

Discrete Graphical Models (GMs) are widely used in Artificial Intelligence to describe complex systems through a joint function of interest. Probabilistic GMs such as Markov Random Fields (MRFs) define a joint non-normalized probability distribution while deterministic GMs such as Cost Function Networks (CFNs) define a joint cost function. A typical query on GMs consists in finding the joint state that optimizes this joint function, a problem denoted as the \textit{Maximum a Posteriori} or Weighted Constraint Satisfaction Problem respectively. In practice, more than one function of interest may need to be optimized at the same time. In this paper, we develop a two-phase scalarization method for solving bi-objective discrete graphical model optimization, with the aim of computing a set of non-dominated solutions --- the Pareto frontier --- representing different compromises between two GM-defined objectives. For this purpose, we introduce a dedicated higher-order constraint, which bounds the value of one GM-defined objective while minimizing another GM on the same variables. Discrete GM optimization is NP-hard, and its bi-objective variants are even harder. We show how existing GM global lower and upper bounds can be exploited to provide anytime bounds of the exact Pareto frontier. We benchmark it on various instances from Operations Research and Probabilistic Graphical Models.
Fichier principal
Vignette du fichier
CPAIOR24.pdf (750.42 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04556832 , version 1 (23-04-2024)

Identifiants

  • HAL Id : hal-04556832 , version 1

Citer

Samuel Buchet, David Allouche, Simon de Givry, Thomas Schiex. Bi-Objective Discrete Graphical Model Optimization. The 21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, May 2024, Uppsala (Suède), Sweden. ⟨hal-04556832⟩
1 Consultations
6 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More