Abstract

Ever since Kantorovich and Dantzig’s pioneering work in linear programming, solution methods for linear programs have evolved considerably. However, formulation of linear programs has remained largely manual, relying heavily on analysts’ expertise. This study aims to explore the possibility of automating problem formulation process using Large Language Models (LLMs). To test LLMs usefulness for linear programming problem formulation, we craft linear programming problem narratives such that we systematically vary problem sizes, problem complexity and linguistic complexity of the narratives. We perform these analyses for various types of optimization problems, including production planning problems, advertising problems, network flow problems, scheduling problems, blending problems and multi period investment problems. In doing so, we test LLMs ability to handle lower and upper bound constraints, flow balancing constraints, if-then logic constraints, blending (proportional) constraints, assignment constraints, and time dependency constraints. By varying linguistic complexity and problem sizes (number of decision variables and constraints) for the above-mentioned problems, we test each problem narrative across four LLMs: GPT-3.5, GPT-4.0, Gemini, and Gemini Advanced. Our results indicate LLMs are more likely to formulate production planning problems correctly, whereas they often fail to formulate scheduling and transportation problems. Our results also indicate that LLMs are more likely to produce a correct formulation when narrative’s linguistic complexity is low. For problem types where LLMs fail to provide correct formulations, we observed errors such as incorrect coefficient assignment, switched coefficient assignment, missing objective functions, missing constraints, and other.