Skip to Main content Skip to Navigation
Conference papers

Focus: A Constraint for Concentrating High Costs

Thierry Petit 1
1 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 aggregated in an objective criterion. In this context, some constraints involving exclusively cost variables are often imposed. Such constraints are complementary to the objective function. They characterize the solutions which are acceptable in practice. This paper deals with the case where the set of costs is a sequence, in which high values should be concentrated in a few number of areas. Representing such a property through a 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 integer 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 propose a complete filtering algorithm in O(n) time complexity.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-00753598
Contributor : Thierry Petit <>
Submitted on : Monday, November 19, 2012 - 2:54:43 PM
Last modification on : Thursday, March 5, 2020 - 5:47:32 PM
Long-term archiving on: : Saturday, December 17, 2016 - 12:04:32 PM

File

unfair.pdf
Files produced by the author(s)

Identifiers

Citation

Thierry Petit. Focus: A Constraint for Concentrating High Costs. Principles and Practice of Constraint Programming CP2012, Oct 2012, Quebec city, Canada. pp.577-592, ⟨10.1007/978-3-642-33558-7_42⟩. ⟨hal-00753598⟩

Share

Metrics

Record views

412

Files downloads

464