1 citations · 1 across the 5 of their papers we have counts for
9 papers · 1 filter
The Graphical Traveling Salesperson Problem has no Integer Programming Formulation in the Original Space
Matthias Walter
The Graphical Traveling Salesperson Problem (GTSP) is the problem of assigning, for a given weighted graph, a nonnegative number each edge such that the induced multi-sub…
Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs
Matthias Walter
Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they…
Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials
Christopher Hojny, Marc E. Pfetsch, Matthias Walter
Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given pol…
Persistency of Linear Programming Relaxations for the Stable Set Problem
Elisabeth Rodríguez-Heck, Karl Stickler, Matthias Walter +1
The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: f…
The Almost-Disjoint 2-Path Decomposition Problem
Annika Thome, Matthias Walter
We consider the problem of decomposing a given (di)graph into paths of length 2 with the additional restriction that no two such paths may have more than one vertex in common. We e…
Extended Formulations for Radial Cones
Matthias Walter, Stefan Weltge
This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron at a vertex is the polyhedron defined by…