Focus: A Constraint for Concentrating High Costs

Thierry Petit 1, 2
2 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : Many Constraint Programming models use integer cost variables ag- gregated in an objective criterion. In this context, some constraints involving exclusively cost variables are often imposed. Such constraints are complemen- tary to the objective function. They characterize the solutions which are accept- able in practice. This paper deals with the case where the set of costs is a se- quence, in which high values should be concentrated in a few number of areas. Representing such a property through an search heuristic may be complex and overall not precise enough. To solve this issue, we introduce a new constraint, FOCUS(X,yc,len, k), where X is a sequence of n integer variables, yc an in- teger variable, and len and k are two integers. To satisfy FOCUS, the minimum number of distinct sub-sequences of consecutive variables in X, of length at most len and that involve exclusively values strictly greater than k, should be less than or equal to yc. We present two examples of problems involving FOCUS. We pro- pose a complete filtering algorithm in O(n) time complexity.
Type de document :
Communication dans un congrès
Proc. First International Workshop on Search Strategies and Non-standard Objectives, (CPAIOR-SSNOW'12), May 2012, Nantes, France, France. 2012
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00753673
Contributeur : Thierry Petit <>
Soumis le : lundi 26 novembre 2012 - 14:51:08
Dernière modification le : vendredi 22 juin 2018 - 09:29:55
Document(s) archivé(s) le : mercredi 27 février 2013 - 03:41:43

Fichier

ssnoworkshop12_submission_1.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00753673, version 1

Citation

Thierry Petit. Focus: A Constraint for Concentrating High Costs. Proc. First International Workshop on Search Strategies and Non-standard Objectives, (CPAIOR-SSNOW'12), May 2012, Nantes, France, France. 2012. 〈hal-00753673〉

Partager

Métriques

Consultations de la notice

264

Téléchargements de fichiers

98