The forbidden-vertices problem aims to optimize a linear function over the vertices of a polytope that remains after prohibiting a given subset of them. We present extended formulations for this problem for some classes of 0 −1 polytopes. The sizes of the formulations are smaller than the known bounds for these polytopes. We also compare this formulation on the Prize collecting TSP with other approaches that describe the same integer set, but generate different polytopes.
Forbidden Vertices for some classes of 0 - 1 polytopes / Salgado, Esteban; Angulo, Gustavo. - (2020).
Forbidden Vertices for some classes of 0 - 1 polytopes
Salgado, Esteban;
2020
Abstract
The forbidden-vertices problem aims to optimize a linear function over the vertices of a polytope that remains after prohibiting a given subset of them. We present extended formulations for this problem for some classes of 0 −1 polytopes. The sizes of the formulations are smaller than the known bounds for these polytopes. We also compare this formulation on the Prize collecting TSP with other approaches that describe the same integer set, but generate different polytopes.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
