Browse Theses

Integer programming is an attractive field to be explored, spurred by the fact that its domain covers a wide range of important and challenging practical applications. However, given its practical applicability, we face computational difficulties in solving the large scale integer programming problems effectively.

This thesis addresses computational aspects of solving certain classes of nonlinear integer programming problems. The framework for the solution approach is provided by the MINOS large scale optimization software. The basic idea adopted is to release a nonbasic variable, found in the continuous optimal solution, from its bounds in such a way that will force a corresponding non-integer basic variable to take its neighbourhood integer value. The notion of superbasic as used in the MINOS code is exploited. The strategy for choosing the nonbasic variables in the integerizing process is based on minimizing the deterioration of the optimal continuous solution.

For a mixed integer linear programming problem, a ratio test is used in order to keep the integer results in the feasible region. In the nonlinear case, besides this ratio test, a feasibility check is used in a way to make sure the variables still satisfy the constraints of the problem.

Computational experience with this approach is described for solving seven classes of problems. The results show that the proposed integerizing strategy is promising in tackling certain classes of mixed integer programming problems.

In order to investigate more general problems, two problems belonging to the class of pure nonlinear integer programming problems are described. However, the integerizing procedure mentioned above, designed specifically for the mixed-integer case, cannot be used. Instead, we adopt the approach of examining a reduced problem in which most of the integer variables are held constant and only a small subset allowed to vary in discrete steps. This approach is carried out by marking all integer variables at their bounds at the continuous solution as nonbasic and solving the reduced problem with these maintained as nonbasic.

Successfully implementation of these algorithms was achieved on various test problems. The results compare favourably with other procedures in the literature.