A inserção de métodos no resolvedor CPLEX: Uma aplicação ao problema de emparelhamento de peso máximo com restrições de conflito

Abstract

Optimization methods seek to find good solutions or, if possible, the best one within a feasible set of possibilities in a reasonable time. In general, they require parameters adjustment and the use of different strategies to find increasingly efficient solutions while taking lesser computational effort. Some solvers, such as CPLEX, are available to handle various optimization problems that fall into the areas of Linear Programming, Integer Programming, Mixed Integer Programming and, to some extent, Quadratic Programming. In addition, they give us the possibility of incorporating our own methods into their tools, in order to further strengthen the solver to tackle the problem in focus. Given this circumstance, our work exemplifies, through the Maximum Weight Matching Problem with Conflict Constraints, how to implement techniques studied during our graduation course (in order to solve problems of integer linear programming), such as cutting planes, lagrangian relaxation, branch-and-cut, lagrangian heuristics. We show how to use, customize or incorporate these methods in the CPLEX solver environment, as well as we evaluate the effects on the solver performance due to different ways of use, parameterizations or applied changes