On Two New Algorithms for Solving Mixed Integer Linear Programming Problems and Their Applications

Taher Ahmed Jubbori

Computer Techniques Engineering Department, Al-Mustaqbal University, Babil, Iraq

Abstract:

The objective of this paper is to introduce two new algorithms for dealing with mixed integer linear programming problems, where the first method will be applied to get the efficient cut in the standard cutting plane procedure to obtain the same optimal solution. The second method will be applied with many special conditions to get the global solution instead of the local solution by using cutting-plane and other famous algorithms. On the other hand, we compare our results to the other obtained results by applying other algorithms.

Keywords: Numerical method; Linear programming; Cutting plane; Efficient cut

1. Introduction

The question of correct linear programming is a usual linear programming question on the condition that all or some of the decision variables are constrained and have an integer value, the methods of solving models with integers are based mainly on two principles:

The first principle: is that the correct models cope at the first stage using the simplified method in the solution.

The second principle: is to adopt the final results that represent the optimal solution as the basis for reaching the best solution that makes the values of the basic variables integer values (non-fractional). New additional constraints are then selected that share or provide valid values for the original variables in the model.

This research is focused: first: on our selection of new additional constraints and by adding these new constraints our new model is formed. Secondly: test the optimal solution for linear integer programming on the basis of that positional convergence or overall convergence of the solution.

Here it should be noted that the addition of new entries comes sequentially so that one entry is added to the model and then the calculations are performed as in the (simplified) method. When the solution is incomplete (i.e., the best solution is not found), another new constraint is added and so on until the correct values of the basic variables in the model are reached [2].