Skip to main content
SpringerLink
Log in

Bilinear modeling solution approach for fixed charge network flow problems

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We present a continuous, bilinear formulation for the fixed charge network flow problem. This formulation is used to derive an exact algorithm for the fixed charge network flow problem converging in a finite number of steps. Some preliminary computational experiments are reported to show the performance of the algorithm.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)

    Google Scholar 

  2. Bomze I.M., Danninger G.: A global optimization algorithm for concave quadratic programming problems. SIAM J. Optim. 3(4), 826–842 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  3. Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113, 259–282 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  4. Cabot A., Erenguc S.: Some branch-and-bound procedures for fixed-cost transportation problems. Nav. Res. Log. Q. 31, 145–154 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chinchuluun A., Pardalos P.M., Enkhbat R.: Global minimization algorithms for concave quadratic programming problems. Optimization 54(6), 627–639 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  6. Costa A.M.: A survey on benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6), 1429–1450 (2005)

    Article  MathSciNet  Google Scholar 

  7. Diestel R.: Graph Theory. Electronic Edition. Springer, New-York (2000)

    Google Scholar 

  8. Eksioglu B., Duni-Eksioglu S., Pardalos P.M.: Equilibrium problems and variational models. In: Maugeri, A., Giannesi, F., Pardalos, P.M. (eds) Solving Large Scale Fixed Charge Network Flow Problems, Kluwer, Dordrecht (2001)

    Google Scholar 

  9. Floudas C., Visweswaran V.: Handbook of global optimization. In: Horst, R., Pardalos, P. (eds) Quadratic Optimization, pp. 217–269. Kluwer, Dordrecht (1995)

    Google Scholar 

  10. Fontes D.B.M.M., Goncalves J.: Heuristic solutions for general concave minimum cost network flow problems. Networks 50(1), 67–76 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  11. Fontes D.B., Hadjiconstantinou E., Christofides N.: A branch-and-bound algorithm for concave network flow problems. J. Glob. Optim. 34(1), 127–155 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  12. Fontes D.B.M.M., Hadjiconstantinou E., Christofides N.: A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems. Eur. J. Oper. Res. 174(2), 1205–1219 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  13. Guenes J., Pardalos P.M.: Supply Chain Optimization. Springer, Berlin (2005)

    Book  Google Scholar 

  14. Guisewite G.M., Pardalos P.M.: Minimum concave-cost network flow problems: applications, complexity, and algorithms. Ann. Oper. Res. 25, 75–100 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  15. Hirsch W., Dantzig G.: The fixed charge problem. Nav. Res. Log. Q. 15, 413–424 (1968)

    MATH  MathSciNet  Google Scholar 

  16. Kim D., Pardalos P.M.: A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure. Oper. Res. Lett. 24, 195–203 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  17. Kim D., Pardalos P.M.: Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems. Networks 35(3), 216–222 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  18. Kim D., Pan X., Pardalos P.M.: An enhanced dynamic slope scaling procedure with Tabu Scheme for fixed charge network flow problems. Comput. Econ. 2–3, 273–293 (2006)

    Article  Google Scholar 

  19. Konno H.: A cutting plane algorithm for solving bilinear programs. Math. Programm. 11, 14–27 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  20. Murty K.: Solving the fixed charge problem by ranking the extreme points. Oper. Res. 16, 268–279 (1968)

    Article  MATH  Google Scholar 

  21. Nahapetyan A., Pardalos P.M.: A bilinear relaxation based algorithm for concave piecewise linear network flow problem. J. Ind. Manage. Optim. 3, 71–85 (2007)

    MATH  MathSciNet  Google Scholar 

  22. Nahapetyan A., Pardalos P.M.: Adaptive dynamic cost updating procedure for solving fixed charge network flow problems. Comput. Optim. Appl. 39, 37–50 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  23. Ortega F., Wolsey L.A.: A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem. Networks 41(3), 143–158 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  24. Palekar U., Karwan M., Zionts S.: A branch-and-bound method for fixed charge transportation problem. Manag. Sci. 36, 1092–1105 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  25. Pardalos P.M.: Global optimization algorithms for linearly constrained indefinite quadratic problems. Comput. Math. Appl. 21(6-7), 87–97 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  26. Pardalos P.M., Vavasis S.A.: Quadratic programming with one negative eigenvalue is np-hard. J. Glob. Optim. 1, 15–22 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  27. Phillips A.T., Rosen J.B.: A parallel algorithm for constrained concave quadratic global minimization. Math. Program. 42(1–4), 421–448 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  28. Ryoo H.S., Sahinidis N.V.: Global optimization of non-convex NLPs and MINLPs with application in process design. Comput. Chem. Eng. 19(5), 551–566 (1995)

    Article  Google Scholar 

  29. Ryoo H.S., Sahinidis N.V.: A branch-and-reduce approach to global optimization. J. Glob. Optim. 8(2), 107–138 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  30. Sahinidis N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201–205 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  31. Tuy H.: Strong polynomial time solvability of minimum concave cost network flow problem. ACTA Math. Vietnam. 25(2), 209–218 (2000)

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Gainesville, FL, 32611, USA

    Steffen Rebennack & Panos M. Pardalos

  2. Innovative Scheduling Inc., Gainesville Technology Enterprise Center (GTEC), 2153 SE Hawthorne Road, Gainesville, FL, 32641, USA

    Artyom Nahapetyan

Authors
  1. Steffen Rebennack
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Artyom Nahapetyan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Steffen Rebennack.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rebennack, S., Nahapetyan, A. & Pardalos, P.M. Bilinear modeling solution approach for fixed charge network flow problems. Optim Lett 3, 347–355 (2009). https://doi.org/10.1007/s11590-009-0114-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-009-0114-0

Keywords

Search

Navigation