Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is well-known that the feasible polytope for the vertex cover problem has the half-integrality property that all corners are $0$, $1/2$, or $1$. Are there any surveys that describe how the polytopes for e.g. set cover, traveling salesman, facility location, Steiner tree, are different from one another? (I realize of course that there could be many different polytopes depending on what formulation one chooses, but I hope this gets my idea across)
$\begingroup$
$\endgroup$
1
-
$\begingroup$ or.stackexchange.com $\endgroup$– Rodrigo de AzevedoCommented Jul 3, 2020 at 8:35
Add a comment
|