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/2016
Entry Accepted: 09/07/2016
Entry Last Modified: 03/29/2018

Modify/Update this entry