Open AccessA Branch-and-bound algorithm for concave minimization problem with upper bounded variables
Author(s) -
Se Ho Oh
Publication year - 2018
Publication title -
international journal of engineering and technology
Language(s) - English
Resource type - Journals
ISSN - 2227-524X
DOI - 10.14419/ijet.v7i2.12.11318
Subject(s) - mathematics , bounded function , branch and bound , simplex , upper and lower bounds , bounding overwatch , mathematical optimization , minification , simplex algorithm , concave function , regular polygon , linear programming , combinatorics , algorithm , computer science , mathematical analysis , geometry , artificial intelligence
This paper presents a branch-and-bound algorithm for solving the concave minimization problems with upper bounded variables. The algorithm uses simplex to construct the branching and the bounding procedure. The linear convex envelope (the objective function of the subproblem) is uniquely determined on the candidate simplex which contains the subset of the local minimal points. The optimal solution of the subproblem is a local optimum of the original concave problem and used in reducing the list of active subproblems. The branching process splits the candidate simplex into two subsimplices by fixing the selected branching variable at value 0 or upper bound. Then the subsimplices are one less dimensional than the candidate. It means that the size of the subproblems gradually decreases. Further research needs to be focused on the efficient determination method of the simplex. The algorithm of this paper can be applied to solving the concave minimization problems under knapsack type constraints.