Optimization Online


A generalized simplex method for integer problems given by verification oracles

Sergei Chubanov (sergei.chubanov***at***uni-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


Download: [PDF]

Entry Submitted: 09/07/2016
Entry Accepted: 09/07/2016
Entry Last Modified: 03/29/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society