Branch-and-price algorithm for fuzzy integer programming problems with block angular structure

By: Malihe Niksirat, S. Mehdi Hashemi, & Mehdi Ghatee

Published: Fuzzy Sets and Systems, Volume 296, 1 August 2016, Pages 70-96.


This paper deals with fuzzy integer linear programming problems with block angular structure in which the fuzzy constraints are simplified by using possibility and necessity relations. This main fuzzy problem is efficiently decomposed and is solved by a branch-and-price algorithm. In the nodes of the branch-and-price tree, the linear relaxation of the problem is solved by applying a column generation method. Also, the relationship between the optimal solutions of this problem under possibility and necessity relations is derived. To show the validation of the proposed algorithm, some results are proved. In addition, the application of this algorithm is illustrated on fuzzy multicommodity flow problem. For this case, a new branching scheme is proposed to preserve the network structure of the subproblems which are produced in the column generation method. Some examples are solved and their results are compared with the previous works. Also, the results of the proposed algorithm are reported on some large-scale benchmark instances.

Leave a comment

Your email address will not be published. Required fields are marked *