A branch-and-bound algorithm for representative integer efficient solutions in multiple objective network programming problems. (English) Zbl 1269.90133
Summary: In many applications of multiple objective network programming (MONP) problems, only integer solutions are acceptable as the final optimal solution. Representative efficient solutions are usually obtained by sampling the efficient set through the solution of augmented weighted Tchebycheff network programs. Because such efficient solutions are usually not integer solutions, a branch-and-bound (BB) algorithm is developed to find integer efficient solutions. The purpose of the BB algorithm is to support interactive procedures by generating representative integer efficient solutions. To be computationally efficient, the algorithm takes advantage of the network structure as much as possible. An algorithm, used in the BB algorithm and performed on the key tree, is developed to construct feasible solutions from infeasible solutions and basic solutions from nonbasic solutions when bounds on branching variables change. The BB algorithm finds basic and nonbasic or supported and unsupported integer efficient solutions as long as they are optimal. Details of the algorithm are presented, an example is provided and computational results are reported. Computational results show that the BB algorithm performs well. Although the BB algorithm is developed for the purpose of generating integer efficient solutions for MONP problems, it can also solve more general integer network flow problems with linear side constraints.
Keywords:
network flow algorithms; multiple objective programming; multiple criteria decision making; integer programming; branch-and-bound; network flow problems with side constraintsReferences:
| [1] | R.K.Ahuja, T.L.Magnanti, and J.B.Orlin, Network flows, Prentice Hall, Upper Saddle River, NJ, 1993. · Zbl 1201.90001 |
| [2] | M.S.Bazaraa, J.J.Jarvis, and H.D.Sherali, Linear programming and network flows, 2nd edition, Wiley, New York, NY, 1990. · Zbl 0722.90042 |
| [3] | J.Brumbaugh‐Smithand D.Shier, An empirical investigation of some bicriterion shortest path algorithms, Eur J Oper Res43( 1989), 216-224. · Zbl 0681.90081 |
| [4] | S.Chenand R.Saigal, A primal algorithm for solving a capacitated network flow problem with additional linear constraints, Networks7( 1977), 59-79. · Zbl 0363.90107 |
| [5] | J.Currentand M.Marsh, Multiobjective transportation network design and routing problems: Taxonomy and annotation, Eur J Oper Res65( 1993), 4-19. · Zbl 0775.90150 |
| [6] | J.Currentand H.Min, Multiobjective design of transportation networks: Taxonomy and annotation, Eur J Oper Res26( 1986), 187-201. |
| [7] | D.Drinka, M.Sun, and B.Murray, A multiple objective embedded network model for human resource planning and an implementation of the Tchebycheff method, Decis Sci27( 1996), 319-341. |
| [8] | M.Ehrgottand X.Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum22( 2000), 425-460. · Zbl 1017.90096 |
| [9] | A.Eusèbioand J.R.Figueira, On the computation of all supported efficient solutions in multiobjective integer network flow problems, Eur J Oper Res199( 2009), 68-76. · Zbl 1176.90535 |
| [10] | A.Eusébioand J.R.Figueira, Finding non‐dominated solutions in bi‐objective integer network flow problems, Comput Oper Res36( 2009), 2554-2564. · Zbl 1179.90049 |
| [11] | A.M.Geoffrionand R.E.Marsten, Integer programming algorithms: A framework and state‐of‐the‐art survey, Manage Sci18( 1972), 465-491. · Zbl 0238.90043 |
| [12] | F.Glover, D.Klingman, and N.V.Phillips, Network models in optimization and their applications in practice, Wiley, New York, NY, 1992. |
| [13] | H.W.Hamacher, C.R.Pedersen, and S.Ruzika, Multiple objective minimum cost flow problems: A review, Eur J Oper Res176( 2007), 1404-1422. · Zbl 1102.90059 |
| [14] | H.Isermann, The enumeration of the set of all efficient solutions for a linear multiple objective program, Oper Res Q28( 1977), 711-725. · Zbl 0372.90086 |
| [15] | H.Isermann, Operating manual for the EFFACET multiple objective linear programming package, Fakultät für Wirtschaftswissenschaften, Universität Bielefeld, Germany, 1984. |
| [16] | J.L.Kenningtonand R.V.Helgason, Algorithms for network programming, Wiley, New York, NY, 1980. · Zbl 0502.90056 |
| [17] | D.Klingman, A.Napier, and J.Stutz, NETGEN—a program for generating large scale (un)capacitated assignment, transportation and minimum cost network problems, Manage Sci20( 1974), 814-822. · Zbl 0303.90042 |
| [18] | H.Leeand P.S.Pulat, Bicriteria network flow problems: Integer case, Eur J Oper Res66( 1993), 148-157. · Zbl 0780.90040 |
| [19] | K.G.Murty, Network programming, Prentice Hall, Englewood Cliffs, NJ, 1992. |
| [20] | A.Mustafaand M.Goh, Finding integer efficient solutions for bicriteria and tricriteria network flow problems using DINAS, Comput Oper Res25( 1998), 139-157. · Zbl 0907.90133 |
| [21] | G.L.Nemhauserand L.A.Wolsey, Integer and combinatorial optimization, Wiley, New York, NY, 1988. · Zbl 0652.90067 |
| [22] | W.Ogryczak, Reference point method with importance weighted partial achievements, J Telecommun Inf Technol4( 2008), 17-25. |
| [23] | W.Ogryczakand B.Kozlowski, Reference point method with importance weighted ordered partial achievements, Top19( 2011), 380-401. · Zbl 1262.90073 |
| [24] | W.Ogryczak, K.Studziński, and K.Zorychta, A solver for the multi‐objective transshipment problem with facility location, Eur J Oper Res43( 1989), 53-64. · Zbl 0681.90035 |
| [25] | W.Ogryczak, K.Studziński, and K.Zorychta, DINAS: A computer‐assisted analysis system for multiobjective transshipment problems with facility location, Comput Oper Res19( 1992), 637-647. |
| [26] | M.Özlenand M.Azizoǧlu, Multi‐objective integer programming: A general approach for generating all non‐dominated solutions, Eur J Oper Res199( 2009), 25-35. · Zbl 1176.90554 |
| [27] | A.Przybylski, X.Gandibleux, and M.Ehrgott, The biobjective integer minimum cost flow problem‐incorrectness of Sedeño‐Noda and González‐Martín’s algorithm, Comput Oper Res33( 2006), 1459-1463. · Zbl 1126.90071 |
| [28] | A.Przybylski, X.Gandibleux, and M.Ehrgott, A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme, INFORMS J Comput22( 2010), 371-386. · Zbl 1243.90203 |
| [29] | P.S.Pulat, F.Huarng, and H.Lee, Efficient solutions for the bicriteria network flow problem, Eur J Oper Res19( 1992), 649-655. · Zbl 0758.90030 |
| [30] | A.Raithand M.Ehrgott, A two‐phase algorithm for the biobjective integer minimum cost flow problem, Comput Oper Res36( 2009), 1945-1954. · Zbl 1179.90303 |
| [31] | G.Ruhe, Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh, Zeitschrift für, Oper Res32( 1988), 9-27. · Zbl 0641.90037 |
| [32] | A.Sedeño‐Nodaand C.González‐Martín, The biobjective minimum cost flow problem, Eur J Oper Res124( 2000), 591-600. · Zbl 0969.90020 |
| [33] | A.Sedeño‐Nodaand C.González‐Martín, An algorithm for the biobjective integer minimum cost flow problem, Comput Oper Res28( 2001), 139-156. · Zbl 0990.90122 |
| [34] | A.Sedeño‐Nodaand C.González‐Martín, An alternative method to solve the biobjective minimum cost flow problem, Asia‐Pacific J Oper Res20( 2003), 241-260. · Zbl 1165.90663 |
| [35] | R.E.Steuer, Multiple criteria optimization: Theory, computation, and application, Wiley, New York, 1986. · Zbl 0663.90085 |
| [36] | R.E.Steuer, ADBASE: A multiple objective linear programming solver for all efficient extreme points and all unbounded efficient edges, Terry College of Business, University of Georgia, Athens, GA, 2003. |
| [37] | R.E.Steuerand E.‐U.Choo, An interactive weighted Tchebycheff procedure for multiple objective programming, Math Program26( 1983), 326-344. · Zbl 0506.90075 |
| [38] | R.E.Steuerand C.Piercy, Difficulties in solving network multiple objective linear programming problems, Vol. 10, K.D.Lawrence (ed.), G.R.Reeves (ed.), and R.K.Klimberg (ed.), editors, Emerald Group, Bingley, UK, 2000, pp. 217-231. |
| [39] | R.E.Steuerand C.A.Piercy, A regression study of the number of efficient extreme points in multiple objective linear programming, Eur J Oper Res162( 2005), 484-496. · Zbl 1176.90558 |
| [40] | R.E.Steuer, J.Silverman, and A.W.Whisman, A combined Tchebycheff/aspiration criterion vector interactive multiobjective programming procedure, Manage Sci39( 1993), 1255-1260. · Zbl 0799.90103 |
| [41] | M.Sun, Procedures for finding nondominated solutions for multiple objective network programming problems, Transport Sci37( 2003), 139-152. |
| [42] | M.Sun, Warm‐start routines for solving augmented weighted Tchebycheff programs in multiple objective network programming, INFORMS J Comput17( 2005), 422-437. · Zbl 1241.90165 |
| [43] | M.Sun, Some issues in measuring and reporting solution quality of interactive multiple objective programming procedures, Eur J Oper Res162( 2005), 468-483. · Zbl 1071.90566 |
| [44] | M.Sun, Finding integer efficient solutions for multiple objective network programming problems, Networks57( 2011), 362-375. · Zbl 1223.90060 |
| [45] | M.Sun, A.Stam, and R.E.Steuer, Solving multiple objective programming problems using feed‐forward artificial neural networks: The interactive FFANN procedure, Manage Sci42( 1996), 835-849. · Zbl 0880.90120 |
| [46] | M.Sun, A.Stam, and R.E.Steuer, Interactive multiple objective programming using Tchebycheff programs and artificial neural networks, Comput Oper Res27( 2000), 601-620. · Zbl 0961.90102 |
| [47] | A.P.Wierzbicki, Reference point methods in vector optimization and decision support, Interim Report IR‐98‐017, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1998. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
