Content area
The main objectives of this thesis are (i) to develop primal-dual interior point algorithms for solving Nonlinear Programming (NLP) problems (ii) to develop a branch and cut algorithm for solving 0-1 Mixed Integer Nonlinear Programming (MINLP) problems and (iii) the application of the interior point algorithms to solve the NLP problems arising during the solution process of a 0-1 MINLP problem. Two primal-dual interior point algorithms are developed for solving NLP problems with both equality and inequality constraints. In the first algorithm the perturbed optimality conditions of the initial problem are solved by using a quasi- Newton method. The descent property of the search direction is established for a penalty-barrier merit function, based on an approximation of Fletcher's exact and differentiable penalty function. In the second algorithm, an equivalent problem is formulated with the equality constraints incorporated into the objective by means of the quadratic penalty function. The inequality constraints are also included into the objective by means of the logarithmic barrier function. The optimality conditions of the transformed problem are solved by using a quasi-Newton method. The descent property of the search direction is ensured for a merit function, using an adaptive strategy to determine the penalty parameter. Global convergence of both interior point algorithms is achieved through line search procedures that ensure the monotonic decrease of the corresponding merit function. Numerical results demonstrate the efficient performance of both algorithms for a variety of test problems. A branch and cut algorithm is also developed for solving 0-1 MINLP problems. The algorithm integrates Branch and Bound, Outer Approximation and Gomory Cutting Planes. Only the initial Mixed Integer Linear Programming (MILP) master problem is considered. At integer solutions NLP problems are solved, using the primal-dual interior point algorithms mentioned above. The objective and constraints are linearized at the optimum solution of those NLP problems and the linearizations are added to all the unsolved nodes of the enumerations tree. Also, Gomory cutting planes, which are valid throughout the tree, are generated at selected nodes. These cuts help the algorithm to locate integer solutions quickly and consequently improve the linear approximation of the objective and constraints, held at the unsolved nodes of the tree. Numerical results show that the addition of Gomory cuts can reduce the number of nodes in the enumeration tree.