  


A generalized simplex method for integer problems given by verification oracles
Sergei Chubanov (sergei.chubanovunisiegen.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 Modify/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  