CORMSIS Seminar Event
- Time:
- 16:00 - 17:00
- Date:
- 15 January 2015
- Venue:
- Room 02/3041
For more information regarding this event, please telephone Alain Zemkoho on +23863 or email A.B.Zemkoho@soton.ac.uk .
Event details
Natural Intersection Cuts for Mixed-Integer Linear Programs
Abstract: Intersection cuts are a family of cutting planes for pure and mixed integer linear programs, developed in the 1970s. Most papers on them consider only cuts that come from so-called maximal lattice-point-free polyhedra. We define a completely different family of intersection cuts, called “natural”. Their key property is that they can be generated very quickly and easily from a simplex tableau. In many cases, one can also easily strengthen them, using an idea of Balas and Jeroslow. We show that the strengthened cuts are a generalisation of Gomory mixed-integer cuts, and then show how to tailor the cuts to problems with special structure (such as packing, covering and partitioning problems, or problems with complementarity constraints).
Speaker information
Trivikram Dokka,University of Lancaster,Trivikram’ first degree is in engineering and has worked as Process Improvement and Optimization Engineer in industry for four years in India. He then did M.Phil. in Applied Mathematics at the University of Birmingham. Following that, he did his Ph.D. in Operations Research at Katholieke Universiteit Leuven, Belgium. His Ph.D. work focused on approximation algorithms and polyhedral results for multi-dimensional assignment problems. He is currently working as a Lecturer in Management Science department at Lancaster University Management School. His current work focuses on on cutting-planes for mixed-integer programs, polyhedral methods and approximation algorithms for multi-index assignment problems arising in different applications, bi-level optimization problems. His interests span combinatorial optimization, integer programming, exact and approximation algorithms for NP-hard problems.