A generalized simplex method for integer problems given by verification oracles

We consider a nonlinear integer problem given by a verification oracle, i.e., by an oracle which is able to verify whether a solution is optimal. The algorithm that we propose in this paper can be viewed as a variant of the simplex method applied to an associated linear problem over the convex hull $P$ of the image of the feasible set under some nonlinear mapping associated with the objective function. The algorithm runs in a number of iterations which is polynomial in the number of different values which can be taken by the components of the vertices of $P.$ At each iteration, the number of arithmetic operations and calls to the verification oracle is bounded by a polynomial in the size of the problem and in $\max\{\|v - w\|_\infty: v,w\in P\}.$ The algorithm can be viewed as a modification of the shadow vertex algorithm based on an analysis of the normal fan of $P.$

Article

Download

View A generalized simplex method for integer problems given by verification oracles