Length-Lex Bounds Consistency for Knapsack Constraints.pdf.pdf' (193.73 kB)
Download fileLength-Lex Bounds Consistency for Knapsack Constraints
journal contribution
posted on 1962-11-01, 00:00 authored by Yuri Malitsky, Meinoff Sellmann, Willem-Jan Van HoeveWillem-Jan Van HoeveRecently, a new domain store for set-variables has been proposed
which totally orders all values in the domain of a set-variable based on cardinality
and lexicography. Traditionally, knapsack constraints have been studied with
respect to the required and possible set domain representation. For this domainstore
efficient filtering algorithms achieving relaxed and approximated consistency
are known. In this work, we study the complexity of achieving length-lex
and approximated length-lex bounds consistency. We show that these strengthened
levels of consistency can still be achieved in (pseudo-)polynomial time. In
addition, we devise heuristic algorithms that work efficiently in practice.