We consider a linear problem over a finite set of integer vectors

and assume that there is a verification oracle, which is an algorithm being

able to verify whether a given vector optimizes a given linear function over the

feasible set. Given an initial solution, the algorithm proposed in this paper

finds an optimal solution of the problem together with a path, in the 1-skeleton

of the convex hull of the feasible set, from the initial solution to the optimal

solution found. The length of this path is bounded by the sum of distinct

values which can be taken by the components of feasible solutions, minus the

dimension of the problem. In particular, in the case when the feasible set is

a set of binary vectors, the length of the constructed path is bounded by the

number of variables, independently of the objective function.

## Article

View A generalized simplex method for integer problems given by verification oracles