Comparação de desempenho entre diferentes solvers de otimização linear e inteira

Abstract

This work presents a comparative performance analysis between four open-source solvers for linear and integer optimization: GLPK (GNU Linear Programming Kit), CBC (COIN-OR Branch and Cut), HiGHS, and SCIP (Solving Constraint Integer Programs). The objective is to evaluate the computational efficiency of these solvers when integrated with the Pyomo modeling library in Python, considering execution time, solution quality, scalability, and stability. The methodology comprises two experimental stages: initial validation with classical small-scale problems; and performance evaluation across 36 larger instances, symmetrically organized into three structural types per problem and six increasing dimensions, ranging from 100 to 10000 variables. We used synthetic instances generated under controlled conditions for the Diet Problem (Linear Programming), and standardized instances from the literature for the Knapsack Problem (Integer Programming). Each solver was run 10 times per instance, with a time limit of 5 seconds per run, and the results were analyzed in terms of mean, standard deviation, and the rate of obtaining optimal solutions. The results indicate that there is no universally superior solver across all problem classes. For Linear Programming, GLPK and HiGHS performed consistently on sparse instances, while CBC stood out on denser instances. For Integer Programming, performance varied significantly according to the structure of the instances: GLPK was the fastest in uncorrelated and weakly correlated instances, but became the only solver unable to prove optimality in strongly correlated instances at a high scale – a case in which CBC proved to be the most robust. SCIP showed higher computational cost in purely linear problems, a behavior probably related to its Integer Programming oriented architecture.