Theory Lunch Seminar March 27, 2024 12:00pm — 1:00pm Location: 8102 - Gates and Hillman Centers Speaker: SIDDHARTH PRASAD , Ph.D. Student, Computer Science Department, Carnegie Mellon University https://sid-prasad.github.io/ New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets Sequence-independent lifting is a procedure for strengthening valid inequalities of an integer program. We generalize the sequence-independent lifting method of Gu, Nemhauser, and Savelsbergh (GNS lifting) for cover inequalities and correct an error in their proposed generalization. We obtain a new sequence-independent lifting technique — piecewise-constant (PC) lifting — with a number of interesting properties. We derive a broad set of sufficient conditions under which PC lifting is facet defining. To our knowledge, this is the first characterization of facet-defining sequence-independent liftings that are efficiently computable from the underlying cover. Finally, we demonstrate via experiments that PC lifting can be a useful alternative to GNS lifting. We test our new lifting techniques atop a number of novel cover cut generation routines, which prove to be effective in experiments with CPLEX. CMU Theory Youtube channel Event Website: https://www.cs.cmu.edu/~theorylunch/ For More Information: In Person Add event to Google Add event to iCal
