Constraint Detection in Natural Language Problem Descriptions

Zeynep Kiziltan, Marco Lippi, Paolo TorroniIJCAI 2016

Introduction: The Modeling Bottleneck

In Constraint Programming (CP), solvers are highly efficient at solving complex optimization tasks, yet a significant "modeling bottleneck" persists. While humans typically describe problems in informal natural language (NL), solvers require rigid, formal specifications. Bridging this gap usually necessitates a human expert proficient in both the application domain and discrete mathematics. This research addresses the first critical step in automating this transition: Constraint Detection. The objective is to automatically identify specific phrases within a text that represent constraints, distinguishing them from general context or input parameters.

The Constraint Detection Pipeline

The proposed system follows a structured pipeline to transform raw problem descriptions into labeled data suitable for automated modeling.

Overview of the constraint detection system pipeline.

The process begins with gathering resources from various problem catalogs, followed by manual labeling to create a gold-standard dataset. This dataset is then used to train a constraint detection system that takes a natural language description as input and outputs a labeled version highlighting the constraints.

Methodology: Sequence Labeling with SVM-HMM

Constraint detection is framed as a sequence labeling problem. Rather than analyzing words in isolation, the system evaluates whether a word belongs to a constraint based on its surrounding context.

The researchers employed a Structured Support Vector Machine (SVM-HMM). Unlike standard classifiers that treat data points as independent, SVM-HMM accounts for the sequential nature of language, enabling "collective classification." The model utilizes several key features:

  • Lexical Features: The original word, its stem, and its Part-of-Speech (POS) tag.
  • Contextual Windows: A "diameter" ($D$) of surrounding words to capture local context.
  • Trigrams: Sequences of three words or tags to identify common linguistic patterns (e.g., "at most a").
  • Mathematical Normalization: Formulas are converted into special tokens to improve generalization across different numeric expressions.

Dataset and Annotation

To evaluate the system, an original annotated corpus was constructed, consisting of 110 problem descriptions from sources such as CSPLib, the ESSENCE catalog, and MiniZinc benchmarks. The dataset includes 1,075 sentences and over 25,000 words. Three experts performed the annotation, using formal mathematical specifications as the "ground truth" to ensure that tagged text accurately reflected formal rules.

Key Results and Analysis

The system was evaluated using a Leave-One-Problem-Out (LOO) approach. Performance was measured using the Hit Rate ($H_T$), False Positive Rate ($H_F$), and Average Loss ($ALS$).

Performance metrics across different context window diameters (D).

As shown in the results table, performance significantly improves as the context window diameter ($D$) increases, peaking at $D=7$. At this optimal setting, the system achieves a hit rate of 80.1%, correctly identifying at least one word in the majority of constraints. While the false positive rate of 31.4% appears high, analysis reveals that many "hallucinated" constraints are actually input parameters (e.g., bin capacities), which are linguistically similar to constraints.

Conclusion and Future Directions

This work demonstrates that linguistic cues and contextual information are powerful indicators for identifying constraints in natural language. While the current system focuses solely on constraint detection, future work aims to incorporate the identification of abstract variables and objective functions. The ultimate goal is to move beyond highlighting text to automatically mapping these snippets into formal, executable code, effectively dissolving the modeling bottleneck.

Summary updated

BibTeX
@inproceedings{kiziltan2016constraint,
  author = {Zeynep Kiziltan and Marco Lippi and Paolo Torroni},
  title = {{Constraint Detection in Natural Language Problem Descriptions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure