Generic Constraint-based Block Modeling using Constraint Programming

Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of artificial intelligence research 2021-02, Vol.70, p.597-630
Main Authors: Mattenet, Alex, Davidson, Ian, Nijssen, Siegfried, Schaus, Pierre
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Constraint modelling
Data analysis
Integer programming
Medical imaging
Mixed integer
Optimization
Searching
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings, for an exhaustive search and for a type of local search called Large Neighborhood Search. We show its use in the analysis of real datasets. Finally, we show an application of the CP framework for model selection using the Minimum Description Length principle.
ISSN:1076-9757
1076-9757
1943-5037
DOI:10.1613/jair.1.12280