A note on adapting methods for continuous global optimization to the discrete case (Q2276877)

It is shown how branch and bound algorithms for solving continuous global optimization (GO) problems can be readily adapted to the discrete case. The modifications introduced take into account the discrete nature of the problems and consist of the use of rectangular partitions, which differ from the partitions used in nondiscrete GO, and special attention to the step-size of the algorithm when a rectangular element reduces to a singleton. Due to these modifications the algorithm is finite in the discrete case. In this way it is possible to obtain a variety of branch and bound algorithms for discrete concave optimization, optimization subject to reverse convex constraints, and Lipschitzian optimization). As an illustration an algorithm for minimizing a concave function over the integers contained in a compact polyhedron is presented. Results of preliminary computational experience are reported for a FORTRAN code executing this algorithm (on an IBM 3090 400 mainframe computer using vector processing).