Source-linked AI summary
NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions
Rindranirina Ramamonjison, Timothy T. Yu, Raymond Li, Haley Li, Giuseppe Carenini, Bissan Ghaddar, Shiqi He, Mahdi Mostajabdaveh, Amin Banitalebi-Dehkordi, Zirui Zhou, Yong Zhang
TL;DR
NL4Opt addresses the challenge of translating natural-language optimization descriptions into solver-usable formulations, aiming to make optimization tools more accessible. It introduces entity recognition and meaning-representation generation tasks, compares competition systems with ChatGPT, and reports improvements over baselines alongside a scope limitation concerning problem complexity and generalizability.
Problem
Formulating real-world optimization problems from natural language is iterative and strenuous, while optimization-formulation extraction remains under-explored and involves ambiguous, variable, domain-specific inputs.
Method
The competition constructs LP word-problem tasks for recognizing optimization entities and generating canonical meaning representations, then evaluates winning systems and ChatGPT.
Results
Winning solutions improved over the baseline by up to 3.3% for sub-task 1 and 29% for sub-task 2, while ChatGPT achieved a 2.8% improvement over the top-performing sub-task 2 submission.
Takeaways & Limitations
The competition provides a dataset and benchmark for developing natural-language interfaces that could make commercial optimization solvers more accessible to non-experts.
Takeaways & Limitations
Because the competition datasets are less complex than real-world problems, ChatGPT's performance on more realistic and challenging descriptions remains unclear.
Abstract
from arXiv · showhide
The Natural Language for Optimization (NL4Opt) Competition was created to investigate methods of extracting the meaning and formulation of an optimization problem based on its text description. Specifically, the goal of the competition is to increase the accessibility and usability of optimization solvers by allowing non-experts to interface with them using natural language. We separate this challenging goal into two sub-tasks: (1) recognize and label the semantic entities that correspond to the components of the optimization problem; (2) generate a meaning representation (i.e., a logical form) of the problem from its detected problem entities. The first task aims to reduce ambiguity by detecting and tagging the entities of the optimization problems. The second task creates an intermediate representation of the linear programming (LP) problem that is converted into a format that can be used by commercial solvers. In this report, we present the LP word problem dataset and shared tasks for the NeurIPS 2022 competition. Furthermore, we investigate and compare the performance of the ChatGPT large language model against the winning solutions. Through this competition, we hope to bring interest towards the development of novel machine learning applications and datasets for optimization modeling.
1. Introduction
Optimization solvers can address real-world decisions, but translating natural-language problem descriptions into solver-ready formulations remains difficult and under-explored. NL4Opt frames this translation as a learning-based natural-language interface problem.
- Motivation: Operations research tools model and solve real-world decision-making problems using standard optimization algorithms.Applications include supply chains, production planning, transportation, wastewater systems, and pricing.
- Motivation: Formulating a solver-ready optimization model requires extracting decision variables, objectives, and constraints from an expert description and rewriting them algebraically.The process is described as iterative and strenuous.
- Research gap: NL4Opt investigates learning-based natural-language interfaces for optimization solvers through partial automation of problem formulation.The competition treats semantic parsing as the extraction of machine-interpretable meaning from natural-language descriptions.
- Research gap: Unlike math-word-problem research focused on solving elementary algebraic problems, NL4Opt converts optimization descriptions into forms that solvers can process.The paper identifies optimization-formulation extraction as under-explored relative to established semantic-parsing applications.
- Research gap: The competition extends related entity-extraction challenges by detecting complex optimization entities and generating an equivalent formulation.This combines recognition with generation rather than limiting the task to extracting measurements or entities.
2. The NL4Opt Competition
NL4Opt explores natural-language interfaces that translate optimization descriptions into mathematical formulations. The competition targets improved access to optimization solvers by enabling non-experts to use them for problems from various industries.
- Impact: NL4Opt aims to improve the accessibility and usability of optimization solvers for non-experts.The stated application is allowing users to solve important problems across industries through natural-language input.
- Competition goal: The competition explores converting natural-language optimization descriptions into mathematical formulations through two inter-related sub-tasks.The supplied text identifies the overall conversion goal but does not detail both sub-tasks here.
1. Recognition of optimization problem entities,
The competition separates optimization understanding into entity recognition and formulation generation, while evaluating recognition with micro-averaged F1 and generation with declaration-level mapping accuracy. Its design addresses ambiguity, alignment, data scarcity, and domain transfer.
- Recognition of optimization problem entities: Sub-task 1 detects and labels constraint directions, limits, objective directions and names, parameters, and variables in problem descriptions.The task identifies text spans corresponding to optimization-model components to reduce ambiguity.
- Generation of problem formulation: Sub-task 2 generates a precise meaning representation from the problem description and recognized entities, then converts it to a canonical form for evaluation.The formulation represents objective and constraint declarations and can be converted into solver-compatible formats.
- Challenges: Unstructured multi-sentence inputs create compositionality and ambiguity because linguistic patterns, domains, and problem structures vary.This variability makes recognition and formulation more difficult than processing a fixed template.
- Challenges: The formulation output abstracts away contextual information from the description, making input-output alignment difficult and increasing the importance of the intermediate representation.Semantically equivalent representations can have syntactically different forms and produce different performance.
- Challenges: The tasks require learning from small numbers of expert-annotated examples and generalizing across disparate application domains.Specialized expertise raises dataset-creation costs, while OR applications span areas such as forestry, transportation, and medicine.
- Evaluation: Recognition is evaluated with micro-averaged F1, while generation uses declaration-level mapping accuracy based on matched predicted and ground-truth declarations.Generation comparisons use the canonical representation, with false positives and false negatives contributing to the metric.
3. The NL4Opt Dataset
The NL4Opt dataset contains annotated linear-programming word problems designed for two related tasks: entity recognition and semantic parsing.
- The dataset contains 1,101 annotated LP word problems from six domains, split into 713 training, 99 development, and 289 test samples.
- Sub-task 1 maps problem descriptions to labeled entities representing optimization-model components.
- Sub-task 2 maps problem descriptions, problem entities, and variable-mention order to canonical meaning representations of objectives and constraints.
- Twenty AI engineers and operations-research experts spent three months creating and annotating an initial dataset of 600 problems.
- The dataset was released under the MIT License, and existing third-party datasets were not used.
4. Baseline Models
The competition provides baseline models and starter code for both sub-tasks, with XLM-R-base for entity recognition and BART-based generation for meaning representations.
- The competition code base was available to participants, who commonly built upon the pilot-study implementation.
- The sub-task 1 baseline uses XLM-RoBERTa-base fine-tuned by minimizing log-likelihood loss.
- The sub-task 1 baseline achieved an F1 score of 0.906 on the test split.
- The sub-task 2 baseline uses a BART encoder-decoder with prompt-guided generation and a copy mechanism.
5. Solutions
Table 2 is identified as the presentation of sub-task 1 winning results.
- Table 2 presents sub-task 1 winning results.
- The table is part of the competition’s solutions section.
- The supplied passage identifies the table but does not provide its result values.
5.1 Sub-task 1
Sub-task 1 winning approaches generally combine ensemble learning with augmentation or adversarial training, achieving test-set F1 scores from 0.929 to 0.939 among the listed teams.
- 0.939 F1 was achieved by Infrrd AI Lab using an ensemble of five transformer-BiLSTM-CRF models with four augmentation techniques.
- 0.933 F1 was achieved by team mcmc using nine DeBERTa-large-CRF variations trained with FGM adversarial attacks and majority voting.
- 0.932 F1 was achieved by PingAn-zhiniao using XLM-R-large with global-pointer and multi-head decoders, without ensemble learning.
- 0.931 F1 was achieved by team Long using XLM-R, adversarial training, augmentation, and post-processing.
- 0.929 F1 was achieved by VTCC-NLP using an ensemble of XLMR, DeBERTaV3, and BART.
5.2 Sub-task 2
Winning submissions for sub-task 2 improved formulation generation through tagged inputs, prompt redesign, preprocessing, augmentation, and adversarial training. Team UIUC-NLP achieved the highest reported accuracy, while other teams used varied architectures and training strategies.
- Team UIUC-NLP: 0.899 accuracy was achieved by Team UIUC-NLP using BART-large, XML-like entity tagging, and a decode-all-at-once generation strategy.Ablations favored combining input tagging with simultaneous generation of objective and constraint declarations.
- Team Sjang: 0.878 accuracy was achieved by Team Sjang using scaled entity-tag embeddings and augmentation that reversed constraint directions.The team reported gains from BART-large, tag-embedding scaling, and constraint augmentation relative to its baseline.
- Team Long: 0.867 accuracy was achieved by Team Long through prompt redesign, data augmentation, adversarial training, and XML-like entity tags.The method used BART-base with a copy mechanism and FGM during fine-tuning.
- Team PingAn-zhiniao: 0.866 accuracy was achieved by Team PingAn-zhiniao using entity tags, preprocessing, and hyperparameter tuning.The largest reported improvement came when the BERT dropout hyperparameter was set to 0.5.
- Team Infrrd AI Lab: 0.780 accuracy was achieved by Team Infrrd AI Lab using T5, entity markup, sample splitting, and multitask training.Each sample could be separated into multiple declaration-specific samples during preprocessing.
5.3 Experiments with large language models
The authors evaluated ChatGPT as a black-box system that directly converts LP word-problem descriptions into formulations, combining the competition’s two subtasks. Using structured prompts and expert verification, ChatGPT achieved 0.927 accuracy on the reserved test set.
- Experimental setup: The experiments combined entity recognition and formulation generation by asking ChatGPT to directly produce an optimization model from each LP word-problem description.Performance was evaluated on development and test datasets using declaration-level mapping accuracy.
- Prompt design: The prompts requested only the model, one-line explanations, unsimplified expressions, no LaTeX or code, and variables named x, y, and z.These instructions were designed to make ChatGPT outputs more consistent.
- Results: 0.927 accuracy was achieved on the reserved test set using gpt-3.5-turbo and per-declaration evaluation verified by OR experts.The model was trained on data available up to September 1, 2021.
6. Discussion
Discussion of the competition emphasizes strong gains from ensemble learning, preprocessing, augmentation, and prompt design, while ChatGPT slightly exceeded the best sub-task 2 submission. The authors also identify computational, transparency, error, and generalizability concerns.
- Sub-task 1: 2.3 to 3.3% increases in F1 over baseline were reported for sub-task 1, with Team Infrrd AI Lab reaching 0.939.Four of the top five teams used ensembles, but the resulting systems were more computationally expensive and less transparent.
- Sub-task 2: 17 to 29% increases in declaration-level accuracy over baseline were reported for sub-task 2, with Team UIUC-NLP reaching 0.899.The discussion attributes the main improvements primarily to preprocessing, data augmentation, and input prompt design.
- Limitations: The competition datasets were less complex than real-world problems, leaving ChatGPT’s performance on more realistic and challenging descriptions unclear.The authors call for further study of generalizability, trustworthiness, and robustness across problem descriptions with varying complexity and realism.
7. Conclusion
The NL4Opt Competition combined entity recognition and generation to convert linear-programming word problems into solver-interpretable representations. Its results improved benchmark performance and released a dataset for further research on natural-language optimization interfaces.
- Competition contribution: The competition combined NER and generation to tag optimization entities and produce canonical representations convertible into solver-interpretable formats.This pipeline targets linear programming word problems.
- Results: Winning methods improved over baseline by up to 3.3% for sub-task 1 and 29% for sub-task 2.The authors propose exploring these solutions for commercial solvers that accept natural-language problem descriptions.
- Future research: The released labelled dataset supports evaluation of multi-sentence inputs, low-resource learning, and generalizability to unseen domains.The authors encourage continued applications of the open-sourced dataset.