Implementation of branch and bound algorithm to solve binary integer optimization problems
2009
Zayed, A.
Integer programming is a widely investigated topic in combinatorial optimization problems, which are classified according to the type of integer value the associated variable takes. This study proposes a branch and bound algorithm to solve the significantly large issue of one of the integer programming problems called binary integer problems (BIPs).The aim of the proposed approach is not only to present the theoretical overview but also to construct an application to overcome the problem of high computational times. We employed the Sudoku puzzle and other small tests to implement the computational running and to measure the efficiency of our application, using different investigation strategies to explore the branch and bound tree. The application gives the optimal solution for the Sudoku puzzle and some different solutions for other tests depending on the exploration and branching strategies used. In conclusion, the application is designed to determine the optimal objective value for most of the binary integer problems. It aims to explore a sufficient number of nodes that satisfy the optimal solution, but not the minimum number of nodes because this can be set depending on each problem separately. This study shows that each problem has a special way of finding the optimal solution and this will be realized with experience and trial and error.
Afficher plus [+] Moins [-]Mots clés AGROVOC
Informations bibliographiques
Cette notice bibliographique a été fournie par Mediterranean Agronomic Institute of Chania
Découvrez la collection de ce fournisseur de données dans AGRIS