A Branch-and-bound algorithm for concave minimization problem with upper bounded variables

  • Authors

    • Se Ho Oh
    2018-04-03
    https://doi.org/10.14419/ijet.v7i2.12.11318
  • Branch-and Bound Algorithm, Concave Minimization, Convex Envelope Simplex

  • Abstract

    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.

     

  • References

    1. [1] Benson HP. A Finite Algorithm for Concave Minimization over a Polyhedron. Naval Research Logistics Quarterly. 1985; 32, 165-177.

      [2] Benson HP. Deterministic Algorithms for Constrained Concave Minimization: A Unified Critical Survey. Naval Research Logistics Quarterly. 1996; 43, 756-795.

      [3] Benson HP, Erenguc SS. A Finite Algorithm for Concave Integer Minimization over a Polyhedron. Naval Research Logistics Quarterly. 1990; 37, 515-525.

      [4] Falk JE, Hoffman KR. A Successive Underestimation Method for Concave Minimization Problems. Mathematics of Operations Research. 1976; 1, 251-259.

      [5] falk JE, Hoffman KR. Concave Minimization via Collapsing Polytope. Operations Research. 1986 November-December; 34, 919-929.

      [6] Horst R. A General Class of Branch-and-Bound Methods in Global Optimization with Some New Approachs for Concave Minimization. Journal of Optimization Theory and Applications. 1986 November; 51, 271-291.

      [7] Kalantari B, Bagchi A. An Algorithm for Quadratic Zero-One Programs. Naval Research Logistics Quarterly. 1990; 37, 527-538.

      [8] Kalantari B, Rosen JB. An Algorithm for Global Minimizatiom of Linearly Constrained Concave Quadratic Functions. Mathematics of Operations Research. 1987; 12, 544-560.

      [9] More JJ, Vavasis SA. On the Solution of Concave Knapsack Problem. Mathematical Prgramming. 1991; 49, 397-411.

      [10] [10] Murty KG. Operations research: deterministic optimization models. Prentice-Hall, Inc.1995.

      [11] Rosen JB. Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain. Mathematics of Operations Research. 1983; 8, 215-230.

      [12] Soland RM. Optimal Facility Location with Concave Costs. Operations Research. 1974; 22, 373-382.

      [13] Sun XL, Wang Fl, Li L. Exact Algorithm for Concave Knapsack Problems: Linear Underestimation Method. Journal of Global Optimization. 2005 September; 33(Issue 1), 15-30.

      [14] Thieu TV. Convergent Algorithms for minimizing a Concave Function. Acta Mathematica Vietnamica. 1978; 5, 106-113.

      [15] Tui H. Concave Programming under Linear Constraints: Dok. Akad. Nauk SSSR. 159, 32-35. Translated 1964, in Soviet Math. Dokl. 1964; 4, 1437-1440.

  • Downloads

  • How to Cite

    Ho Oh, S. (2018). A Branch-and-bound algorithm for concave minimization problem with upper bounded variables. International Journal of Engineering & Technology, 7(2.12), 333-337. https://doi.org/10.14419/ijet.v7i2.12.11318

    Received date: 2018-04-09

    Accepted date: 2018-04-09

    Published date: 2018-04-03