A continuation approach for solving nonlinear optimization problems with discrete variables

A new approach to solving nonlinear optimization problems with discrete variables using continuation methods is described. Our focus is on pure integer nonlinear optimization problems with linear equality constraints (ILENP) but we show how the technique can be extended to more general classes of problems such as those involving linear inequality and mixed integer constraints.; We transform the ILENP into that of finding the global minimizer of a problem with continuous variables over the unit hypercube. To reduce the difficulties caused by the introduction of undesirable local minimizers, we employ a special class of continuation methods, called smoothing methods. These methods deform the original objective function into a function whose smoothness is controlled by a parameter. The success of the approach depends on finding a good smoothing function. We show that the logarithmic barrier function is ideal for the type of global optimization problem that arises from transforming discrete problems of interest.; The continuous problems arising from the smoothed function are solved by a modified Newton method. Since there are only linear equality constraints, we just need to solve the reduced Newton equations for each smoothing parameter. The conjugate gradient algorithm is applied to this set of equations to obtain a descent direction before applying linesearch procedures. When nonconvexity of the transformed objective function arises, it is necessary to obtain a good direction of negative curvature for the linesearch procedures. Issues related to the implementation of the algorithm, such as the termination criteria and the use of preconditioners, are also discussed.; We show the effectiveness of the approach by applying it to a number of real problems and also test problems taken from the literature. These include the binary unconstrained quadratic problem, the frequency assignment problem and the quadratic assignment problem. The results are compared to those from alternative methods, indicating that the new approach is able to produce good-quality solutions for diverse classes of nonlinear discrete optimization problems.