Title:

In this talk, we deal with Branch-and-Bound (BB) algorithms for linearly constrained, separable concave minimization problems. Our discussion is based on the generic BB algorithm of Lawler and Wood (1966), and Ibaraki (1976). Linearly constrained, separable concave minimization problems have two important properties: the global minima is taken in a vertex and it is NP-complete problem (see for instance Murty and Kabadi, (1987)). Usual way to deal with linearly constrained, separable concave minimization problem is to solve linear programming relaxations on subsets of the feasible solution set which have been obtained by using BB strategies. The linear programming relaxation is tighter on smaller subsets, but the running time of the algorithm depends on the number of relaxed linear programming problems need to be solved. Therefore, one of the important issues, in organizing a BB algorithm, is to decrease the number of subproblems before global optimal solution is reached. A new branching strategy, based on sensitivity analysis of the relaxed linear programming problems is introduced. Finiteness of our BB algorithm is proved. We compared our algorithm with Falk and Soland's (1969), and Shectman and Sahinidis' (1998) methods on some test problems known from literature. Further testing of our algorithm has been done on randomly generated PNS (Process Network Synthesis) problems (200 of each size) of sizes n=40 and n=60. Our implementation come favorably with other algorithm find in the literature.