10 citations · 14 across the 14 of their papers we have counts for
14 papers · 1 filter
The Binary Linearization Complexity of Pseudo-Boolean Functions
Matthias Walter
We consider the problem of linearizing a pseudo-Boolean function by means of Boolean functions. Such a linearization yields an integer linear pro…
Recognizing Series-Parallel Matrices in Linear Time
Matthias Walter
A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are parallel to an existing row/column or have…
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…
A Polyhedral Study for the Cubic Formulation of the Unconstrained Traveling Tournament Problem
Marije Siemann, Matthias Walter
We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research…
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…
Parity Polytopes and Binarization
Dominik Ermel, Matthias Walter
We consider generalizations of parity polytopes whose variables, in addition to a parity constraint, satisfy certain ordering constraints. More precisely, the variable domain is pa…
A Note on Matchings Constructed during Edmonds' Weighted Perfect Matching Algorithm
Volker Kaibel, Matthias Walter
We reprove that all the matchings constructed during Edmonds' weighted perfect matching algorithm are optimal among those of the same cardinality (provided that certain mild restri…
Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs
Matthias Walter
We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of all matchings, extended by a binary entry indicating whether the matching contains two spe…
Extended Formulations for Independence Polytopes of Regular Matroids
Volker Kaibel, Jon Lee, Matthias Walter +1
The ancillary file Corrigendum.pdf contains an explanation why our proof does not work.
Subgraph Polytopes and Independence Polytopes of Count Matroids
Michele Conforti, Volker Kaibel, Matthias Walter +1
Given an undirected graph, the non-empty subgraph polytope is the convex hull of the characteristic vectors of pairs (F, S) where S is a non-empty subset of nodes and F is a subset…