Computational Aspects of Relaxation Complexity

Abstract: The relaxation complexity rc(X) of a set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is an important tool to investigate the existence of compact linear descriptions of X. In this talk, I will address computational aspects of relaxation complexity such as finding computable upper bounds on rc(X) or the exact value of rc(X). For the latter, I will show generic algorithmic approaches and provide explicit formulas for rc(X) for specific classes of sets X.

This is joint work with Gennadiy Averkov and Matthias Schymura.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

---

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.

---