Polyhedral analysis and branch and cut algorithms for some NP-hard spanning subgraph problems

Abstract

There is a widespread need to use a quantitative approach for the solution of decision problems that arise in many different areas of real life. The goal is to choose which decisions to take to manage a real system as efficiently as possible using mathematical tools. Operations Research provides a scientific basis to try to analyze and understand situations even with very complex structures and then use the gathered information to pre dict the behaviour of a system and improve the performance of the system itself. The analysis of a real problem occurs in two phases: the representation of the problem through a mathematical model and the development of efficient mathematical methods to determine an optimal solution of the problem or a good approximation of it. Therefore, the Operations Research is the science that deals with giving a unitary context to mathematical and computer science concepts and that starting from theoretical bases arrives at the construction of concrete models and their solution. .. [edited by the Author]