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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1619000
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact