Holy Grail 2.0: From Natural Language to Constraint Models

Twenty-seven years ago, E. Freuder highlighted that "Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it".

“However, there is still a gap between a natural formulation of the problem (in Natural Language) and a CP model. The user is still responsible for transforming the problem at hand as an optimization model, to model it as a set of variables with their domains, a set of constraints, and an objective function. This is not always trivial and requires quite some expertise, and it is considered a bottleneck for the wider adoption of CP.

Today, with the astonishing recent advances in Large Language Models (LLMs), isn’t it the time to think ahead, toward the holy grail 2.0, where the user could use natural language to define a problem, and the system would be able to understand and automatically extract the formal model required by the solvers?”

Our framework will be highly using LLMs, being also capable to use specialized tools to tackle some subtasks, like for the NER4OPT task [3] Multiple LLMs will be tested such as GPT variations or LLAMA. Prompt engineering (also known as in-context learning), which is the task of carefully designing prompts to better leverage LLMs capabilities, has been shown to significantly boost performance on several tasks [17]. There are many different ways to use prompt engineering for a task on hand. We mainly experimented and included in our system the following:

Roles and goals [18]. One efficient way to get better results using prompt engineering is to specify the role the LLM has to play and the goal to achieve. The intent of this technique is to localize the training of the LLM for the specific task on hand, selecting what types of output to generate and what details to focus on. Some LLMs have also specific internal tools that can help to achieve that in a better way. For example, for the GPT models, we can make use of the system/user prompt duality. The system prompt allows us to set up the role and goals, i.e., we can give a statement such as "Assume you are a combinatorial optimization expert and you need to model a combinatorial problem as an optimization problem". Then the user prompts are used to converse with it.

Few-shot learning [2] will be very useful to boost the performance of LLMs, by giving examples of the task on hand in each step and how to solve it. In addition, it can be used for specifying the formatting we require for the output when formulating the formal model, for example. For instance, the extractions from pre-trained Ner4Opt models can be used to automate the few-shot example generation for in-context learning.

Chain-of-thought [21] prompting techniques take prompting one step further, allowing models to decompose multi-step problems into intermediate steps. This means that additional computation can be allocated to problems that require more reasoning steps than simple input-process-output scenarios. It has been shown that even zero-shot Chain-of-thought prompts can be very efficient, especially in symbolic tasks.

Tree of Thoughts [11, 23] techniques are inspired by the human mind’s approach to solving complex reasoning tasks through trial and error. In this process, the system explores the solution space through a tree-like process, using backtracking when needed. This helps to generate alternative outputs for a given prompt, choosing the best one, in order to ensure better results.

Plan-and-Solve [20]. Despite the remarkable success of Zero-shot Chain of Thoughts in solving multi-step reasoning tasks, there are still many cases where Intermediate reasoning step(s) are missed, leading to worse performance. This happens especially when there are many steps involved in the task on hand. Plan-and-Solve was proposed to alleviate this issue. This method consists of 2 different steps: First, the system is asked to focus on devising a plan dividing the entire task, without the need to solve the problem. Then, in a separate step, it is asked to carry out the subtasks according to the plan.”