- | ||||
|
![]()
|
A generalized simplex method for integer problems given by verification oracles
Sergei Chubanov (sergei.chubanov 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 | |
![]() |