The relaxed nonfeasible-basis cutting plane method for an integer programming problem

The cutting plane method is an iterative method which is used to solve an integer linear programming problem. It starts by solving the LP relaxation which an integer condition is dropped, and then the cuts are added to refine the continuous feasible region for finding the optimal integer solution. However, the additional cuts lead to enlarge a problem size and a long computational time. In this thesis, we propose two novel methods to improve the cutting plane method for solving an integer programming problem. The proposed methods are the integration of the cutting plane method and the Nonfeasible Basis Method which is solved the LP relaxation without using artificial variables. The first method uses both techniques directly, and it is named the Nonfeasible- Basis Cutting Plane Method (NBC). The second method is the slight modification of NBC with relaxing some constraints, and it is named the Relaxed Nonfeasible-Basis Cutting Plane Method (RNBC). It starts by solving the relaxation problem with the NBC method. The computational results show that NBC and RNBC can reduce the computational time comparing with the traditional method since NBC and RNBC do not involve the artificial variables and are performed on the condensed tableau.