Adjacency of the best and second best valued solutions in combinatorial optimization problems (Q1314336)

Let \(P\) be a polytope. Given a weight vector \(w\) the \(K\)-best extreme point-problem is to find \(K\) different extreme points \(x_ 1,\dots,x_ k\) of \(P\) such that \(w(x_ 1)\leq\cdots\leq w(x_{k-1})\leq w(x_ k)\) and \(w(x_ k)\leq w(x)\) for all extreme points \(x\neq x_ 1,\dots,x_ k\). A \(K\)-best valued extreme point is an extreme point \(x_ k\) of \(P\) for which there exist extreme points \(x_ 1,\dots,x_{k-1}\) satisfying \(w(x_ 1)<\cdots< w(x_{k-1})< w(x_ k)\) and \(w(x_ k)< w(x)\) for all extreme points \(x\) with \(w(x)\neq w(x_ 1),\dots,w(x_ k)\). A polytope \(P\) is said to satisfy the strong adjacency property if for any weight vector \(w\) every best valued extreme point is adjacent to some second best valued extreme point of \(P\). It is shown that polytopes satisfying the following property \((P_ 1)\) share the strong adjacency property: \((P_ 1)\): for each ordered pair \((x,y)\) of extreme points of \(P\) which are not adjacent there exist other extreme points \(x^ 1,\dots, x^ n\) and positive integers \(\lambda_ 1,\dots,\lambda_ n\) such that \(y- x= \lambda_ 1(x^ 1- x)+\cdots+ \lambda_ n(x^ n- x)\). Combinatorial polytopes (with examples such as perfect matching, binary \(b\)-matching, set partitioning-polytopes or base-polytopes of matroids) are shown to share \((P_ 1)\) and thus the strong adjacency property. Finally, monotone 0-1 polytopes such as matching, stable set or set packing polytopes are also shown to share the strong adjacency property.