Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

For the first half, I am going to give a background on all the tools we have for solving problems in the form max c^T x subject to Ax <= b where some x_i variables take integer values only and other x_i variables can take real values. This encoding can solve many famous problems such as the travelling salesman problem and set packing problems. These problems are also solved in assigning TA's to teach classes, production planning, job scheduling, data clustering, etc. Hence linear mixed integer optimization problems live in an extremely applied area of mathematics. In fact, SIAM in 2000 listed an algorithm used to solve these problems as one of the top 10 most important algorithms in the 20th Century! In the second half, I will focus on the special case when the matrix A only contains zeros and ones, and how this helps the general problem.