CMUC

Multi-Objective Network Optimization. The multiobjective shortest path problem (MSPP) - an extension of the shortest path problem - is defined on network where a k-uple cost is assigned to each arc. In a MSPP, one tries to determine origin-destination non-dominated paths. The study of algorithmic performances for MSPPs is related to the number (called v) of these non-dominated paths. However, v is very dependent on the problem instance being considered and can assume a wide range of values, even within the same class of networks.

We have conducted intensive computational experience [5] for statistical analysis on v, relatively to changes in the type of network, varying its size (nodes, arcs, and costs) and the number of criteria. More specifically, we have collected experimental evidence on how the average and standard deviation of the number of non-dominated paths in a network vary as a function of the these network parameters.

One of the consequences of our computational study is the development of a representative set of MSPPs for algorithmic benchmarking, as an addition to [1].

Bicriteria Knapsack Problem. The purpose of our study in [2] is to implement a new algorithm for the bicriteria 0-1 knapsack problem - which has applications in capital budgeting problems and transportation investments. After converting the knapsack model into a bicriteria path problem over an acyclic network, the methodology proposes the use of a very efficient labeling algorithm. The major advantage of our approach is the ability to compute non-dominated solutions for bicriteria 0-1 knapsack problems faster than other approaches, as shown by the computational results in [2].

Ranking Shortest Path Problem. The ranking of shortest paths is a classical network optimization problem, whose goal is to determine K shortest paths between a given pair of nodes of a network by non-decreasing order of their costs [4]. The K shortest loopless paths problem is a constrained K shortest paths problem where all the paths have to be loopless, that is, each path can not have repeated nodes [3]. A new algorithm for the ranking of loopless paths problem has been developed, which is valid for directed and undirected networks. The proposed algorithm seems to perform well in practice as our comparative computational experiments allows us to conclude. This conclusion is reinforced with some results obtained with large networks.


		Large Scale Network Problems
	Problem Description	Network optimization models appear in many real life applications, such as those involving highway systems, rail and airline services, crew scheduling, and manufacturing and distribution systems.
	Modelling & Computational Challenges	Given the dimension and complexity of the problem data, most of these models involve large scale networks. In a number of instances, given the need to optimize some desired goals, one is faced with the solution of a single-objective or a multi-objective network optimization problem, depending on the number of goals. It is therefore crucial the development of efficient algorithms to solve network optimization problems. A proper comparison between the different algorithms is also essential. For this purpose, a collection of problems containing a variety of large networks has been developed in the literature [1].
	Research at LCM	Multi-Objective Network Optimization. The multiobjective shortest path problem (MSPP) - an extension of the shortest path problem - is defined on network where a k-uple cost is assigned to each arc. In a MSPP, one tries to determine origin-destination non-dominated paths. The study of algorithmic performances for MSPPs is related to the number (called v) of these non-dominated paths. However, v is very dependent on the problem instance being considered and can assume a wide range of values, even within the same class of networks. We have conducted intensive computational experience [5] for statistical analysis on v, relatively to changes in the type of network, varying its size (nodes, arcs, and costs) and the number of criteria. More specifically, we have collected experimental evidence on how the average and standard deviation of the number of non-dominated paths in a network vary as a function of the these network parameters. One of the consequences of our computational study is the development of a representative set of MSPPs for algorithmic benchmarking, as an addition to [1]. Bicriteria Knapsack Problem. The purpose of our study in [2] is to implement a new algorithm for the bicriteria 0-1 knapsack problem - which has applications in capital budgeting problems and transportation investments. After converting the knapsack model into a bicriteria path problem over an acyclic network, the methodology proposes the use of a very efficient labeling algorithm. The major advantage of our approach is the ability to compute non-dominated solutions for bicriteria 0-1 knapsack problems faster than other approaches, as shown by the computational results in [2]. Ranking Shortest Path Problem. The ranking of shortest paths is a classical network optimization problem, whose goal is to determine K shortest paths between a given pair of nodes of a network by non-decreasing order of their costs [4]. The K shortest loopless paths problem is a constrained K shortest paths problem where all the paths have to be loopless, that is, each path can not have repeated nodes [3]. A new algorithm for the ranking of loopless paths problem has been developed, which is valid for directed and undirected networks. The proposed algorithm seems to perform well in practice as our comparative computational experiments allows us to conclude. This conclusion is reinforced with some results obtained with large networks.
	Papers & Reports	[1] J.E. Beasley, OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41 (1990) 1069-1072 (updated here). [2] M.E. Captivo, J.N. Clímaco, J.R. Figueira, E.Q. Martins, and J.L. Santos, Solving bicriteria 0-1 knapsack problems using a labeling algorithm, Computers & Operations Research, 30 (2003) 1865-1886. [3] E.Q. Martins, M.M. Pascoal, and J.L. Santos, Deviation algorithms for ranking shortest paths, International Journal of Foundations of Computer Science, 10 (1999) 247-261. [4] E.Q. Martins, M.M. Pascoal, and J.L. Santos, A new improvement for a k shortest paths algorithm, Investigação Operacional, 21 (2001) 47-60. [5] J.L. Santos, Optimização Vectorial em Redes, PhD Thesis, Department of Mathematics, University of Coimbra, 2003.
	Software	[1] Multiobjective shortest path problem - algorithms and problem collection (C code) - available. [2] Solving bicriteria 0-1 knapsack problems using a labeling algorithm (C code) - available under request. [3] Ranking shortest and loopless shortest paths (C code) - available under request.
	Project Team	José Pinto Paixão, CIO, FCUL Mário Rosa, LCM-CMUC José Luis Santos, LCM-CMUC M.E. Captivo, CIO, FCUL J.N. Clímaco, School of Economics, University of Coimbra J.R. Figueira, School of Economics, University of Coimbra M. Pascoal, Department of Mathematics, FCTUC & CISUC