Master corner polyhedron: Vertices

We focus on the vertices of the master corner polyhedron (MCP), a fundamental object in the theory of integer linear programming. We introduce two combinatorial operations that transform vertices to their neighbors. This implies that each MCP can be defined by the initial vertices regarding these operations; we call them support vertices. We prove that the class of support vertices of all MCPs over a group is invariant under automorphisms of this group and describe MCP vertex bases. Among other results, we characterize its irreducible points, establish relations between a vertex and the nontrivial facets that pass through it, and prove that this polyhedron is of diameter 2.

► This paper focuses on vertices of the master corner polyhedron (MCP). ► We prove that two combinatorial operations transform vertices to adjacent vertices. ► We describe the MCP vertex structure and vertex bases. ► We characterize geometrically the irreducible points of the MCP. ► The MCP is proved to be of diameter 2.