Combinatorial optimization: theory, formulations and applications

Abstract

In this project we propose the study of topics in combinatorial optimization including graph theory, integer programming and some applications. In particular, we are interested with linear programming formulations: Given a matrix A m by n, and vectors b, with m real components, and c, with n real components, we want to find an vector x, with n real non-negative components, which maximizes the product cx subject to Ax less or equal to b. This formulation is very versatile and the are various efficient tools available to solve this models like Gurobi and Cplex. Many combinatorial optimization problems have interesting applications. One example is the Traveling Salesman Problem, which may be applied in assembly lines, one famous case was Siemens printed board circuits, which had a reduction in production by 35%. Other interesting problems are the shortest path in a graph, the minimum cut spanning tree and the resource management problem.