Skip to main content
SpringerLink
Log in

A Finite Algorithm for Global Minimization of Separable Concave Programs

  • Chapter
State of the Art in Global Optimization

Part of the book series: Nonconvex Optimization and Its Applications ((NOIA,volume 7))

Abstract

Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches nonlinear programming to be explored. This paper proposes a new finite algorithm for solving this problem. In addition to providing a proof of finiteness, the paper discusses a new way of designing branch-and-bound algorithms for concave programming that ensures finiteness. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 concave variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bazaraa, M.S. and Sherali, H.D. (1982), “On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem,” Journal Operational Society, 33, 991–1003.

    MathSciNet  MATH  Google Scholar 

  2. Ben Saad, S. and Jacobsen, S.E. (1990), “A Level Set Algorithm for a Class of Reverse Convex Programs,” Annals of Operations Research, 25, 19–42.

    Article  MathSciNet  MATH  Google Scholar 

  3. Benson, H.P. (1985), “A Finite Algorithm for Concave Minimization over a Polyhedron,” Naval Research Logistics Quarterly, 32, 165–177.

    Article  MathSciNet  MATH  Google Scholar 

  4. Benson, H.P. (1990), “Separable Concave Minimization Via Partial Outer Approximation and Branch and Bound,” Operations Research Letters, 9, 389–394.

    Article  MathSciNet  MATH  Google Scholar 

  5. Benson, H.P. (1994), “Concave Minimization: Theory, Applications and Algorithms,” in Handbook of Global Optimization, Pardalos, P.M. and Horst, R., eds., Kluwer Academic Publishers, Hingham, Massachusetts.

    Google Scholar 

  6. Benson, H.P. and Sayin, S. (1994), “A Finite Concave Minimization Algorithm Using Branch and Bound and Neighbor Generation,” Journal of Global Optimization, 5, 1–14.

    Article  MathSciNet  MATH  Google Scholar 

  7. Bomze, I.M. and Danninger, G. (1992), “A Finite Algorithm for Solving General Quadratic Problems,” Journal of Global Optimization, 4, 1–16.

    Article  MathSciNet  Google Scholar 

  8. Bomze, I.M. and Danninger, G. (1993), “A Global Optimization Algorithm for Concave Quadratic Programming Problems,” SIAM Journal of Optimization, 3, 826–842.

    Article  MathSciNet  MATH  Google Scholar 

  9. Bretthauer, K.M. and Cabot, A.V. (1994), “A Composite Branch and Bound, Cutting Plane Algorithm for Concave Minimization Over a Polyhedron,” Computers in Operations Research, 21 (7), 777–785.

    Article  MathSciNet  MATH  Google Scholar 

  10. Cabot, A.V. and Francis, R.L. (1970), “Solving Certain Nonconvex Quadratic Minimization Problems by Ranking the Extreme Points,” Operations Research, 18, 82–86.

    Article  MATH  Google Scholar 

  11. Carvajal-Moreno, R. (1972), “Minimization of Concave Functions Subject to Linear Constraints,” Operations Research Center, University of California, Berkeley, ORC 72–3.

    Google Scholar 

  12. Dorneich, M.C. and Sahinidis, N.V. (1995), “Global Optimization Algorithms for Chip Layout and Compaction,” to appear in Engineering Optimization.

    Google Scholar 

  13. Dyer, M.E. (1983), “The Complexity of Vertex Enumeration Methods,” Mathematics of Operations Research, 8, 381–402.

    Article  MathSciNet  MATH  Google Scholar 

  14. Dyer, M.E. and Proll, L.G. (1977), “An Algorithm for Determining All Extreme Points of a Convex Polytope,” Mathematical Programming, 12, 81–96.

    Article  MathSciNet  MATH  Google Scholar 

  15. Falk, J.E. (1973), “A Linear Max-Min Problem,”Mathematical Programming, 5, 169–188.

    Article  MathSciNet  MATH  Google Scholar 

  16. Falk, J.E. and Hoffman, K.R. (1976), “A Successive Underestimation Method for Concave Minimization Problems,” Mathematics of Operations Research, 1 (3), 1976.

    Article  Google Scholar 

  17. Falk, J.E. and Soland, R.M. (1969), “An Algorithm for Separable Nonconvex Programming Problems,” Management Science, 15 (9), 550–569.

    Article  MathSciNet  MATH  Google Scholar 

  18. Floudas, C.A. and Pardalos, P.M. (1990), A Collection of Test Problems for strained Global Optimization Algorithms, Lecture Notes in Computer Science, 268, Springer-Verlag, Berlin- Heidelberg.

    Google Scholar 

  19. Frieze, A.M. (1974), “A Bilinear Programming Formulation of the 3 Dimensional Assignment Problem,” Mathematical Programming, 7, 376–379.

    Article  MathSciNet  MATH  Google Scholar 

  20. Gianessi, F. and Niccolucci, F. (1976), “Connections Between Nonlinear and Integer Programming Problems,” in Symposia Mathematica Vol. XIX, Istituto Nazionale Di Alta Math., Academic Press, New York, 161–176.

    Google Scholar 

  21. Glover, F. (1973), “Convexity Cuts and Cut Search,” Operations Research, 21, 123–134.

    Article  MathSciNet  MATH  Google Scholar 

  22. Glover, F. and Klingman, D. (1973), “Concave Programming Applied to a Special Class of 0-1 Integer Programs,” Operations Research, 21, 135–140.

    Article  MathSciNet  MATH  Google Scholar 

  23. 23]Hansen, P, Jaumard, B, and Lu, S-H (1991), “An Analytical Approach to Global Optimization,” Mathematical Programming, Series B, 52, 227–254.

    Article  MathSciNet  MATH  Google Scholar 

  24. Hoffman, K.L. (1981), “A Method for Globally Minimizing Concave Functions Over Convex Sets,” Mathematical Programming, 22, 22–32.

    Article  Google Scholar 

  25. Horst, R. (1976), “An Algorithm for Nonconvex Programming Problems,” Mathematical Programming, 10, 312–321.

    Article  MathSciNet  MATH  Google Scholar 

  26. 26]Horst, R. (1984), “On the Global Minimization of Concave Functions— Introduction and Survey,” OR Spektrum, 6, 195–205.

    Article  MathSciNet  MATH  Google Scholar 

  27. Horst, R., and Tuy, H. (1993), Global Optimization: Deterministic Approaches, Springer-Verlag, 2nd ed., Berlin.

    Google Scholar 

  28. Kalantari, B. and Rosen, J.B. (1987), “An Algorithm for Global Minimization of Linearly Constrained Convex Quadratic Functions,” Mathematics of Operations Research, 12 (3), 544–561.

    Article  MathSciNet  MATH  Google Scholar 

  29. Krynski, S.L. (1979), Minimization of a Concave Function under Linear Constraints (Modification of Tuy’s Method), in Survey of Mathematical Programming, Proceedings of the Ninth International Mathematical Programming Symposium, Budapest, 1976, North-Holland, Amsterdam, 1, 479–493.

    Google Scholar 

  30. Lamar, B.W. (1993), “An Improved Branch and Bound Algorithm for Minimum Concave Cost Network Flow Problems,” Journal of Global Optimization, 3 (3), 261–287.

    Article  MathSciNet  MATH  Google Scholar 

  31. Lawler, E.L. (1963), “The Quadratic Assignment Problem,” Management Science, 9, 586–699.

    Article  MathSciNet  MATH  Google Scholar 

  32. Mangasarian, O.L. (1978), “Characterization of Linear Complementarity Problems as Linear Programs,” Mathematical Programming Study, 7, 74–87.

    MathSciNet  MATH  Google Scholar 

  33. Matheiss, T.H. (1973), “An Algorithm for Determining Unrelevant Constraints and All Vertices in Systems of Linear Inequalities,” Operations Research, 21, 247–260.

    Article  MathSciNet  Google Scholar 

  34. Matheiss, T.H. and Rubin, D.S. (1980), “A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets,” Mathematics of Operations Research, 5, 167–185.

    Article  MathSciNet  MATH  Google Scholar 

  35. McCormick, G.P. (1972), “Attempts to Calculate Global Solutions of Problems that May Have Local Minima,” in Numerical Methods for Non-Linear Optimization, Lootsma, F.A., Ed. Academic Press, New York, 209–221.

    Google Scholar 

  36. Moshirvaziri, K. (1994), “A Generalization of the Construction of Test Problems for Nonconvex Optimization,” Journal of Global Optimization, 5, 21–34.

    Article  MathSciNet  MATH  Google Scholar 

  37. Moshirvaziri, K. (1994), Personal Communication.

    Google Scholar 

  38. Mukhamediev, B.M. (1982), “Approximate Methods of Solving Concave Programming Problems”, USSR Computational Mathematics and Mathematical Physics, 22(3), 238–245.

    Article  MathSciNet  MATH  Google Scholar 

  39. Murty, K.G. and Kabadi, S.N. (1987), “Some A/T-Complete Problems in Quadratic and Nonlinear Programming,” Mathematical Programming, 39, 117–129.

    Article  MathSciNet  MATH  Google Scholar 

  40. Nourie, F.J. and Gder, F. (1994), “A Restricted-Entry Method for a Trans-portation Problem with Piecewise-Linear Concave Costs,” Computers in Operations Research, 21 (7), 723–733.

    Article  MATH  Google Scholar 

  41. Pardalos, P.M. (1985), “Integer and Separable Programming Techniques for Large-Scale Global Optimization Problems,” Ph.D. Thesis, Computer Science Department, University of Minnesota, Minneapolis.

    Google Scholar 

  42. Pardalos, P.M. and Rosen, J.B. (1986), “Methods for Global Concave Minimization: A Bibliographic Survey,” SIAM Review, 28, 367–379.

    Article  MathSciNet  MATH  Google Scholar 

  43. Pardalos, P.M. and Rosen, J.B. (1987), Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science, 268, Springer-Verlag, Berlin- Heidelberg.

    Google Scholar 

  44. Phillips, A.T. (1988), “Parallel Algorithms for Constrained Optimization, Ph.D. Dissertation”, University of Minnesota, Minneapolis, MN.

    Google Scholar 

  45. Phillips, A.T. and Rosen, J.B. (1987), “A Parallel Algorithm for Constrained Concave Quadratic Global Minimization, Technical Report 87–48,” Computer Science Department, Institute of Technology, University of Minnesota, Minneapolis.

    Google Scholar 

  46. Phillips, A.T. and Rosen, J.B. (1988), “A Parallel Algorithm for Constrained Concave Quadratic Global Minimization,” Mathematical Programming, 42, 421–448.

    Article  MathSciNet  MATH  Google Scholar 

  47. Phillips, A.T. and Rosen, J.B. (1990), “A Parallel Algorithm for Partially Separable Non-convex Global Minimization: Linear Constraints,” Annals of Operations Research, 25, 101–118.

    Article  MathSciNet  MATH  Google Scholar 

  48. Phillips, A.T. and Rosen, J.B. (1990), “Guaranteed ɛ-Approximate Solution for Indefinite Quadratic Global Minimization,” Naval Research Logistics, 37, 499–514.

    Article  MathSciNet  MATH  Google Scholar 

  49. Phillips, A.T. and Rosen, J.B. (1993), “Sufficient Conditions for Solving Linearly Constrained Separable Concave Global Minimization Problems,” Journal of Global Optimization, 3, 79–94.

    Article  MathSciNet  MATH  Google Scholar 

  50. Phillips, A.T. and Rosen, J.B. (1994), “Computational Comparison of Two Methods for Constrained Global Optimization,” Journal of Global Optimization, 5 (4), 325–332.

    Article  MathSciNet  MATH  Google Scholar 

  51. Raghavachari, M. (1969), “On Connections between Zero-One Integer Programming and Concave Programming Under Linear Constraints,” Operations Research, 17, 680–684.

    Article  MathSciNet  MATH  Google Scholar 

  52. Rosen, J.B. (1983), “Global Minimization of a Linearly Constrained Con¬cave Function by Partition of Feasible Domain,” Mathematics of Operations Research, 8 (2), 215–230.

    Article  MathSciNet  MATH  Google Scholar 

  53. Rosen, J.B. and Pardalos, P.M. (1986) “Global Minimization of Large- Scale Constrained Concave Quadratic Problems by Separable Programming,” Mathematical Programming, 34, 163–174.

    Article  MathSciNet  MATH  Google Scholar 

  54. Rosen, J.B. and van Vliet, M. (1987), “A Parallel Stochastic Method for the Constrained Concave Global Minimization Problem, Technical Report 87–31,” Computer Science Department, Institute of Technology, University of Minnesota, Minneapolis.

    Google Scholar 

  55. Ryoo, H.S. (1994), “Range Reduction as a Means of Performance Improvement in Global Optimization: A Branch-and-Reduce Global Optimization Algorithm,” Master’s Thesis, University of Illinois, Urbana.

    Google Scholar 

  56. Ryoo, H.S. and Sahinidis, N.V. (1994), “A Branch-and-Reduce Approach to Global Optimization,” Submitted to Journal of Global Optimization.

    Google Scholar 

  57. Ryoo, H.S. and Sahinidis, N.V. (1995), “Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design,” Computers & Chemical Engineering, 19 (5), 551–566.

    Google Scholar 

  58. Sahinidis, N.V. (1992), “Accelerating Branch-and-Bound in Continuous Optimization,” Research Report UILU ENG 92 - 4031, University of Illinois, Urbana.

    Google Scholar 

  59. Sherali, H.D. and Alameddine, A. (1990) “A New Reformulation- Linearization Technique for Bilinear Programming Problems,” Technical Report, Department of Industrial and Systems Engineering, Virginia Poly-technic Institute and State University, Blacksburg, Virginia.

    Google Scholar 

  60. Sherali, H.D. and Tuncbilek, C.H. (1994), “Tight Reformulation- Linearization Technique Representations for Solving Nonconvex Quadratic Programming Problems,” Technical Report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia.

    Google Scholar 

  61. Soland, R.M. (1974), “Optimal Facility Location with Concave Costs, Operations Research,” 22, 373–382.

    Article  MathSciNet  MATH  Google Scholar 

  62. Suhl, U.H. and Szymanski (1994), “Supemode Processing of Mixed-Integer Models,” Computational Optimization and Applications, 3, 317–331.

    Article  MathSciNet  MATH  Google Scholar 

  63. Thakur, N.V. (1990), “Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Function over a Polyhedron,” Mathematics of Operations Research, 16 (2), 390–407.

    Article  MathSciNet  Google Scholar 

  64. Thieu, T.V. (1980), “Relationship Between Bilinear Programming and Concave Programming,” Acta Mathematica Vietnamica, 2, 106–113.

    Google Scholar 

  65. Thoai, N.V. and Tuy, H. (1980), “Convergent Algorithms for Minimizing a Concave Function,” Mathematics of Operations Research, 5, 556–566.

    Article  MathSciNet  MATH  Google Scholar 

  66. Thoai, N.V. and Tuy, H. (1983), “Solving the Linear Complementarity Problem Through Concave Programming,” USSR Computational Mathematics and Mathematical Physics, 23 (3), 55–59.

    Article  MATH  Google Scholar 

  67. Tuy, H. (1964), “Concave Programming Under Linear Constraints,” Soviet Mathematics, 5, 1437–1440.

    Google Scholar 

  68. Tuy, H. (1991), “Effect of the Subdivision Strategy on Convergence and Efficiency of Some Global Optimization Algorithms,” Journal of Global 0ptimization, 1 (1), 23–36.

    Article  MathSciNet  MATH  Google Scholar 

  69. Tuy, H. and Horst, R. (1988), “Convergence and Restart in Branch-and- Bound Algorithms for Global Optimization. Application to Concave Minimization and D.C. Optimization Problems,” Mathematical Programming, 41, 161–183.

    Article  MathSciNet  MATH  Google Scholar 

  70. Tuy, H., Thieu, T.V., and Thai N.Q. (1985), “A Conical Algorithm for Globally Minimizing a Concave Function Over a Closed Convex Set,” Mathematics of Operations Research, 10, 498–514.

    Article  MathSciNet  MATH  Google Scholar 

  71. Visweswaran, V. and Floudas, C.A. (1993), “New Properties and Compu-tational Improvement of the GOP Algorithm for Problems with Quadratic Objective Functions and Constraints,” Journal of Global Optimization, 3, 439–462.

    Article  MathSciNet  MATH  Google Scholar 

  72. Zwart, P.B. (1971), “Computational Aspects on the Use of Cutting Planes in Global Optimization,” Proceedings of the 1971 Annual Conference of the ACM, 457–465.

    Google Scholar 

  73. Zwart, P.B. (1973), “Nonlinear Programming: Counterexamples to Global Optimization Algorithms,” Operations Research, 21, 1260–1266.

    Article  MathSciNet  MATH  Google Scholar 

  74. Zwart, P.B. (1974), “Global Maximization of a Convex Function with Linear Inequality Constraints,” Operations Research, 22, 602–609.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical & Industrial Engineering, The University of Illinois at Urbana-Champaign, 1206 West Green Street, Urbana, Illinois, 61801, USA

    J. Parker Shectman & Nikolaos V. Sahinidis

Authors
  1. J. Parker Shectman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nikolaos V. Sahinidis
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Princeton University, USA

    C. A. Floudas

  2. University of Florida, USA

    P. M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Kluwer Academic Publishers

About this chapter

Cite this chapter

Shectman, J.P., Sahinidis, N.V. (1996). A Finite Algorithm for Global Minimization of Separable Concave Programs. In: Floudas, C.A., Pardalos, P.M. (eds) State of the Art in Global Optimization. Nonconvex Optimization and Its Applications, vol 7. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-3437-8_20

Download citation

  • DOI: https://doi.org/10.1007/978-1-4613-3437-8_20

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4613-3439-2

  • Online ISBN: 978-1-4613-3437-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation