Carnegie Mellon University
Browse

Two Set-Constraints for Modeling and Efficiency

Download (181.5 kB)
journal contribution
posted on 2008-01-30, 00:00 authored by Willem-Jan Van HoeveWillem-Jan Van Hoeve, Ashish Sabharwal
Set variables provide convenient modeling shorthands for many combinatorial problems. However, it is often challenging to efficiently handle set constraints when solving the problem. We present efficient filtering algorithms, establishing bounds consistency, for two such constraints: the sum-free constraint, and the atmost1 constraint on pairs of set variables with known cardinality. The filtering algorithm for the sum-free constraint achieves the same pruning as the corresponding collection of constraints on the binary representation, but it does so more efficiently and without running into memory bottlenecks. For the atmost1 constraint on pairs of set variables, the additional time spent on pruning more values pays off well in terms of overall efficiency. Our results show that set constraints can not only ease modeling the problem, they can also decrease the solution time and memory requirements.

History

Publisher Statement

All Rights Reserved

Date

2008-01-30

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC