Matthias Schymura

Efficient MIP Techniques for Computing the Relaxation Complexity

  • Gennadiy Averkov
  • Christopher Hojny
  • Matthias Schymura
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We … Read more

    Computational Aspects of Relaxation Complexity: Possibilities and Limitation

  • Gennadiy Averkov
  • Christopher Hojny
  • Matthias Schymura
    • Categories (Mixed) Integer Linear Programming Tags ,

    The relaxation complexity $\mathrm{rc}(X)$ of the 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 a useful tool to investigate the existence of compact linear descriptions of $X$. In this article, we derive … Read more