Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Solving linear mixed integer optimization problems Student-Run Applied & Math Seminar
|Speaker: ||Brandon Dutra, UC Davis|
|Location: ||2112 MSB|
|Start time: ||Wed, Dec 3 2014, 12:10PM|
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
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.