Loosely speaking, an integer program (IP) becomes simpler if we relax some of the constraints that enforce variables be integer-valued. In this talk, we analyze IPs using mixed integer relaxations (MIPs). For integer linear programs, we consider structural questions such as ‘When can an IP be recast as an MIP with fewer integer variables?’ and ‘What is the distance between solutions to an IP and solutions to a linear program (LP)?’ If time permits, we will also consider how to extend the algorithmic principles of gradient descent, which is a convex optimization algorithm, to an algorithm for convex integer programs.
RSVP here.