An intelligent machine modelling assistant for combinatorial optimisation — Deakin University : Australian Research Council Discovery Project (DP220101925)
Summary
An intelligent machine modelling assistant for combinatorial optimisation. This project aims to discover key fundamental technologies for automating assistance to non-expert users in the formulation of mathematical models. Through automating the modelling of combinatorial optimization problems, this research will generate new knowledge to address the fundamental challenges of automatic mathematical modelling. This intelligent assistant will enable synthesis of new mathematical models through the utilisation of pioneering natural language processing components and novel custom-made machine-readable knowledge bases. The outcome of this research will broaden access to high-quality models by non-expert workforce and alleviate the shortage of expert mathematicians, bringing significant social and economic benefits.
National Interest Test Statement
Mathematical modelling has an important role in science, business, civic services, and government operations and is traditionally conducted by expert mathematicians. However, there is a shortage of trained expert mathematicians in Australia that has a direct impact on quality and timely mathematical modelling. Optimisation modelling is a prime example of mathematical modelling that has improved business processes by saving resources or increasing efficiency for optimal outcomes. This research will make it possible for non-mathematician users to develop models tailored to their requirements through interacting with a computer. Our prototype will assist non-experts in formulating optimisation models for a range of planning, scheduling, resource allocation, timetabling problems and will benefit businesses and not-for-profit organisations. In doing so, this project will utilise a natural language processing-based agent with knowledge bases and Artificial Intelligence solutions to deliver economic and societal benefits according to Australia’s Tech Future report 2018.
GitHub Repositories
Publications
📄 AgentMILO: A Knowledge-Based Framework for Complex MILP Modelling Conversations with LLMs
Published: March 2025 at ICCAE 2025, Perth, Australia
Authors: Jyotheesh Gaddam, Lele Zhang, Vicky Mak-Hau, John Yearwood, Bahadorreza Ofoghi, Diego Molla-Aliod
Abstract: This paper presents AgentMILO, an LLM-based conversational agent designed to assist non-expert users in modelling complex Mixed-Integer Linear Programming (MILP) problems, with a focus on production planning and single-traveller routing problem types. By incorporating expert designed knowledge graphs, AgentMILO improves the problem modelling process by guiding users through asking relevant questions to elicit problem specifications from users and formulation of precise MILP models. Through experiments with ten distinct auto-answering agents acting as users, we compared AgentMILO against a general LLM agent without knowledge graphs. The results show that AgentMILO consistently outperforms the general LLM model in clarity in guiding users, question quality, and ease of interaction, while also delivering more precise MILP formulations. In contrast, the general model struggled with inconsistent performance and frequent failures in guiding users effectively. AgentMILO's architecture allows for integration into various domains, with the potential to utilise expert knowledge to design new knowledge graphs tailored to specific scenarios.
📄 Investigating Answer Validation Using Noise Identification and Classification in Goal-Oriented Dialogues
Published: February 2025 at ICAART 2025, Porto, Portugal
Authors: Sara Mirabi, Bahadorreza Ofoghi, John Yearwood, Diego Molla-Aliod, Vicky Mak-Hau
Abstract: Goal-oriented conversational systems based on large language models (LLMs) provide the potential capability to gather the necessary requirements for solving tasks or developing solutions. However, in real-world scenarios, non-expert users may respond incorrectly to dialogue questions, which can impede the system’s effectiveness in eliciting accurate information. This paper presents a novel approach to detecting and categorizing noisy answers in goal-oriented conversations, with a focus on modeling linear programming problems. Using a current LLM, Gemini, we develop multi-agent synthetic conversations based on problem statements from the benchmark optimization modeling dataset NL4Opt to generate dialogues in the presence of noisy answers too. Our experiments show the LLM is not sufficiently equipped with the capabilities to detect noisy answers and hence, in almost 59% of the cases where there is a noisy answer, the LLM continues with the conversation without any attempts at resolving
📄 Synthetic Dialogue Dataset Generation using LLM Agents
Published: December 2023 at GEM Workshop (EMNLP 2023), Singapore
Authors: Yelaman Abdullin, Diego Molla-Aliod, Bahadorreza Ofoghi, John Yearwood, Qingyang Li
Abstract: Linear programming (LP) problems are pervasive in real-life applications. However, despite their apparent simplicity, an untrained user may find it difficult to determine the linear model of their specific problem. We envisage the creation of a goal-oriented conversational agent that will engage in conversation with the user to elicit all information required so that a subsequent agent can generate the linear model. In this paper, we present an approach for the generation of sample dialogues that can be used to develop and train such a conversational agent. Using prompt engineering, we develop two agents that "talk" to each other, one acting as the conversational agent, and the other acting as the user. Using a set of text descriptions of linear problems from NL4Opt available to the user only, the agent and the user engage in conversation until the agent has retrieved all key information from the original problem description. We also propose an extrinsic evaluation of the dialogues by assessing how well the summaries generated by the dialogues match the original problem descriptions. We conduct human and automatic evaluations, including an evaluation approach that uses GPT-4 to mimic the human evaluation metrics. The evaluation results show an overall good quality of the dialogues, though research is still needed to improve the quality of the GPT-4 evaluation metrics. The resulting dialogues, including the human annotations of a subset, are available to the research community. The conversational agent used for the generation of the dialogues can be used as a baseline.
📄 Synthesizing mixed-integer linear programming models from natural language descriptions
Published: November 2023 on arXiv, presented at INFORMS 2024 and OPTIMA-CON 2024
Authors: Qingyang Li, Lele Zhang, Vicky Mak-Hau
Abstract: Numerous real-world decision-making problems can be formulated and solved using Mixed-Integer Linear Programming (MILP) models. However, the transformation of these problems into MILP models heavily relies on expertise in operations research and mathematical optimization, which restricts non-experts' accessibility to MILP. To address this challenge, we propose a framework for automatically formulating MILP models from unstructured natural language descriptions of decision problems, which integrates Large Language Models (LLMs) and mathematical modeling techniques. This framework consists of three phases: i) identification of decision variables, ii) classification of objective and constraints, and iii) finally, generation of MILP models. In this study, we present a constraint classification scheme and a set of constraint templates that can guide the LLMs in synthesizing a complete MILP model. After fine-tuning LLMs, our approach can identify and synthesize logic constraints in addition to classic demand and resource constraints. The logic constraints have not been studied in existing work. To evaluate the performance of the proposed framework, we extend the NL4Opt dataset with more problem descriptions and constraint types, and with the new dataset, we compare our framework with one-step model generation methods offered by LLMs. The experimental results reveal that with respect to the accuracies of generating the correct model, objective, and constraints, our method which integrates constraint classification and templates with LLMs significantly outperforms the others. The prototype system that we developed has a great potential to capture more constraints for more complex MILPs. It opens up opportunities for developing training tools for operations research practitioners and has the potential to be a powerful tool for automatic decision problem modeling and solving in practice.
📄 Knowledge representation of mathematical optimization problems and constructs for modeling
Published: November 2023 in Knowledge-Based Systems (Elsevier)
Authors: Bahadorreza Ofoghi, John Yearwood
Abstract: We introduce two new knowledge bases that we have developed to categorize mixed-integer linear programming (MILP) problems and standardize the element definitions of MILP models. MILP is a commonly used mathematical programming technique for modeling and solving real-life scheduling, routing, planning, resource allocation, and timetabling optimization problems providing optimized business solutions for industry sectors such as manufacturing, agriculture, defense, healthcare, medicine, energy, finance, and transportation among others. Despite the numerous real-life combinatorial optimization problems (COPs) found and solved, and many yet to be discovered and formulated, the number of types of constraints (the building blocks of a MILP) is relatively small. In the search for a uniform categorization of MILP problems and a machine-readable knowledge representation structure for MILP models, we have developed an optimization modeling tree (OMT) and a MILP model ontology. The two knowledge structures can serve as a standardized, uniform representation in understanding MILP problems and developing MILP models for combinatorial business optimization problems. While there are several algebraic modeling languages (AMLs) for developing and solving MILP models, the semantic correctness of such models cannot be guaranteed using the syntactic grammar of such AMLs. The MILP model ontology will act as the main resource for semantic validation of MILP models through ontology instantiations and axiom assertions.
Key Events
DOI: 10.1109/ICCAE64891.2025.10980596
DOI: 10.5220/0013304000003890
DOI: aclanthology.org/2023.gem-1.16
DOI: arXiv:2311.15271v1
DOI: 10.1016/j.knosys.2023.110980
Chief Investigators
Prof Vicky Mak-Hau
Professor, Faculty of Science Engineering and Built Environment/School of Information Technology, Deakin University, Melbourne, Australia
Sr Lect Bahadorreza Ofoghi
Senior Lecturer, Information Technology, Faculty of Science Engineering and Built Environment/School of Information Technology, Deakin University, Melbourne, Australia
A/Prof Lele Zhang
Associate Professor, School of Mathematics and Statistics, The University of Melbourne, Melbourne, Australia
Sr Lect Diego Molla-Aliod
Senior Lecturer, School of Computing, Macquarie University, Sydney, Australia
Prof John Yearwood
Emeritus Professor, Faculty of Science Engineering and Built Environment/Office of the Executive Dean Science, Engineering and Built Environment, Deakin University, Melbourne, Australia
Post-Doctoral Fellow
Dr Jyotheesh Gaddam
Postdoctoral Research Fellow, Faculty of Science Engineering and Built Environment/School of Information Technology, Deakin University, Melbourne, Australia
PhD Students
Qingyang Li
Graduate Researcher, The University of Melbourne, Melbourne, Australia
Sara Mirabi
Graduate Researcher, Deakin University, Melbourne, Australia
Yelaman Abdullin
Graduate Researcher, Macquarie University, Sydney, Australia