Some branch and bound techniques for nonlinear optimization

The range of nonlinear optimization problems which can be solved by Linear Programming and the Branch and Bound algorithm is extended by introducing Chains of Linked Ordered Sets and by allowing automatic interpolation of new variables. However this approach involves solving a succession of linear subproblems, whose solutions in general violate the logical requirements of the nonlinear formulation and may lie far from any local or global optimum. The paper describes techniques which are designed to improve the performance of the Branch and Bound algorithm on problems containing chains, and which also yield benefits in integer programming.Each linear subproblem is tightened towards the corresponding nonlinear problem by removing variables which must logically be nonbasic in any feasible solution. This is achieved by a presolve procedure, and also by post-optimal Lagrangian relaxation which tightens the bound on the objective function by assessing the cheapest way to satisfy any violated chain constraints. Frequently fewer subsequent branches are required to find a feasible solution or to prove infeasibility.Formerly of Scicon Ltd.