A GENERALIZED SIMPLEX METHOD FOR INTEGER PROBLEMS GIVEN BY VERIFICATION ORACLES

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.

Automated summary

This paper discusses a linear problem over a finite set of integer vectors and proposes an algorithm to find the optimal solution. The algorithm constructs a path from the initial solution to the optimal solution in the 1-skeleton of the convex hull of feasible solutions, with the length of the path bounded by the sum of distinct component values minus the problem dimension. In the case of binary vectors, the path length is bounded by the number of variables, regardless of the objective function.