Finding integer efficient solutions for multiple objective network programming problems. (English) Zbl 1223.90060
Summary: For many practical multiple objective network programming (MONP) problems, only integer solutions are meaningful and acceptable. Representative efficient solutions are usually generated by solving augmented weighted Tchebycheff network programs (AWTNPs), sub-problems derived from MONP problems. However, efficient solutions generated this way are usually not integer valued. In this study, two algorithms are developed to construct integer efficient solutions starting from fractional efficient solutions. One algorithm finds a single integer efficient solution in the neighborhood of the fractional efficient solution. The other enumerates all integer efficient solutions in the same neighborhood. Theory supporting the proposed algorithms is developed. Two detailed examples are presented to demonstrate the algorithms. Computational results are reported. The best integer efficient solution is very close, if not equal, to the integer optimal solution. The CPU time taken to find integer efficient solutions is negligible, when compared with that taken to solve AWTNPs.
MSC:
| 90C29 | Multi-objective and goal programming |
| 90C10 | Integer programming |
| 90C35 | Programming involving graphs or networks |
Keywords:
network flow algorithms; multiple objective programming; multiple criteria decision making; integer programmingReferences:
| [1] | Ahuja, Network flows (1993) |
| [2] | Bazaraa, Linear programming and network flows (1990) · Zbl 0722.90042 |
| [3] | Chen, A primal algorithm for solving a capacitated network flow problem with additional linear constraints, Networks 7 pp 59– (1977) · Zbl 0363.90107 · doi:10.1002/net.3230070105 |
| [4] | Current, Multiobjective transportation network design and routing problems: Taxonomy and annotation, Eur J Oper Res 65 pp 4– (1993) · Zbl 0775.90150 · doi:10.1016/0377-2217(93)90140-I |
| [5] | Current, Multiobjective design of transportation networks: Taxonomy and annotation, Eur J Oper Res 26 pp 187– (1986) · doi:10.1016/0377-2217(86)90180-3 |
| [6] | Drinka, A multiple objective embedded network model for human resource planning and an implementation of the Tchebycheff method, Decis Sci 27 pp 319– (1996) · doi:10.1111/j.1540-5915.1996.tb01720.x |
| [7] | Ehrgott, A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum 22 pp 425– (2000) · Zbl 1017.90096 · doi:10.1007/s002910000046 |
| [8] | Eusébio, Finding non-dominated solutions in bi-objective integer network flow problems, Comput Oper Res 36 pp 2554– (2009) · Zbl 1179.90049 · doi:10.1016/j.cor.2008.11.001 |
| [9] | Eusébio, On the computation of all supported efficient solutions in muti-objective integer network flow problems, Eur J Oper Res 199 pp 68– (2009) · Zbl 1176.90535 · doi:10.1016/j.ejor.2008.10.031 |
| [10] | Glover, Network models in optimization and their applications in practice (1992) · doi:10.1002/9781118033173 |
| [11] | Hamacher, Multiple objective minimum cost flow problems: A review, Eur J Oper Res 176 pp 1404– (2007) · Zbl 1102.90059 · doi:10.1016/j.ejor.2005.09.033 |
| [12] | Kennington, Algorithms for network programming (1980) |
| [13] | Lee, Bicriteria network flow problems: Integer case, Eur J Oper Res 66 pp 148– (1993) · Zbl 0780.90040 · doi:10.1016/0377-2217(93)90213-7 |
| [14] | Murty, Network programming (1992) |
| [15] | Mustafa, Finding integer efficient solutions for bicriteria and tricriteria network flow problems using DINAS, Comput Oper Res 25 pp 139– (1998) · Zbl 0907.90133 · doi:10.1016/S0305-0548(97)00027-0 |
| [16] | Nemhauser, Integer and combinatorial optimization (1988) · doi:10.1002/9781118627372 |
| [17] | Ogryczak, A solver for the multi-objective transshipment problem with facility location, Eur J Oper Res 43 pp 53– (1989) · Zbl 0681.90035 · doi:10.1016/0377-2217(89)90409-8 |
| [18] | Ogryczak, DINAS: A computer-assisted analysis system for multiobjective transshipment problems with facility location, Comput Oper Res 19 pp 637– (1992) · doi:10.1016/0305-0548(92)90033-2 |
| [19] | Özlen, Multi-objective integer programming: A general approach for generating all non-dominated solutions, Eur J Oper Res 199 pp 25– (2009) · Zbl 1176.90554 · doi:10.1016/j.ejor.2008.10.023 |
| [20] | Przybylski, The biobjective integer minimum cost flow problem-incorrectness of Sedeño-Noda and González-martín’s Algorithm, Comput Oper Res 33 pp 1459– (2006) · Zbl 1126.90071 · doi:10.1016/j.cor.2004.11.001 |
| [21] | Raith, A two-phase algorithm for the biobjective integer minimum cost flow problem, Comput Oper Res 36 pp 1945– (2009) · Zbl 1179.90303 · doi:10.1016/j.cor.2008.06.008 |
| [22] | Steuer, Multiple criteria optimization: Theory, computation, and application (1986) · Zbl 0663.90085 |
| [23] | R.E. Steuer Difficulties in solving multicriteria networks: A combined weighted sum/Tchebycheff/aspiration criterion vector interactive procedure 1995 |
| [24] | Steuer, An interactive weighted Tchebycheff procedure for multiple objective programming, Math Program 26 pp 326– (1983) · Zbl 0506.90075 · doi:10.1007/BF02591870 |
| [25] | Steuer, Multi-criteria applications, applications of management science 10 pp 217– (2000) |
| [26] | Steuer, A combined Tchebycheff/aspiration criterion vector interactive multiobjective programming procedure, Manage Sci 39 pp 1255– (1993) · Zbl 0799.90103 · doi:10.1287/mnsc.39.10.1255 |
| [27] | Sun, Procedures for finding nondominated solutions for multiple objective network programming problems, Transport Sci 37 pp 139– (2003) · doi:10.1287/trsc.37.2.139.15249 |
| [28] | Sun, Warm-start routines for solving augmented weighted Tchebycheff network programs in multiple-objective network programming, INFORMS J Comput 17 pp 422– (2005) · Zbl 1241.90165 · doi:10.1287/ijoc.1050.0140 |
| [29] | Sun, Some issues in measuring and reporting solution quality of interactive multiple objective programming procedures, Eur J Oper Res 162 pp 468– (2005) · Zbl 1071.90566 · doi:10.1016/j.ejor.2003.08.058 |
| [30] | Sun, A branch-and-bound algorithm for integer efficient solutions in multiple objective network programming problems (2009) |
| [31] | Sun, Solving multiple objective programming problems using feed-forward artificial neural networks: The interactive FFANN procedure, Manage Sci 42 pp 835– (1996) · Zbl 0880.90120 · doi:10.1287/mnsc.42.6.835 |
| [32] | Sun, Interactive multiple objective programming using Tchebycheff programs and artificial neural networks, Comput Oper Res 27 pp 601– (2000) · Zbl 0961.90102 · doi:10.1016/S0305-0548(99)00108-2 |
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.
