Carnegie Mellon University
Browse
Length-Lex Bounds Consistency for Knapsack Constraints.pdf.pdf' (193.73 kB)

Length-Lex Bounds Consistency for Knapsack Constraints

Download (193.73 kB)
journal contribution
posted on 1962-11-01, 00:00 authored by Yuri Malitsky, Meinoff Sellmann, Willem-Jan Van HoeveWillem-Jan Van Hoeve
Recently, 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.

History

Date

1962-11-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC