- A generalized simplex method for integer problems given by verification oracles Sergei Chubanov (sergei.chubanovuni-siegen.de) Abstract: 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.$ Keywords: linear programming, duality, simplex algorithm, normal fan. Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Integer Programming Citation: Download: [PDF]Entry Submitted: 09/07/2016Entry Accepted: 09/07/2016Entry Last Modified: 03/29/2018Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.