×

The linear convolution of criteria in the bicriteria traveling salesman problem. (English. Russian original) Zbl 0947.90074

Comput. Math. Math. Phys. 37, No. 8, 902-905 (1997); translation from Zh. Vychisl. Mat. Mat. Fiz. 37, No. 8, 933-936 (1997).
It is known that the method of linear convolution (parametrization) of criteria in the problem of multicriteria optimization is often considered as a practical method for finding solutions that are optimal in one sense or another. The computational experiment in solving the MINSUM-MINMAX bicriteria assignment, covering trees, and 1-trees problems performed in these papers has shown that the fraction of solutions that can be found by using the linear convolution of Pareto optimal solutions is rather small and decreases monotonically as the dimension of the problem increases. The similar result is obtained for the NP-hard problems.

MSC:

90C10 Integer programming
90C29 Multi-objective and goal programming
49K40 Sensitivity, stability, well-posedness
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite