On a multicriteria shortest path problem

Multicriteria shortest path problems have not been treated intensively in the specialized literature, despite their potential applications. In fact, a single objective function may not be sufficient to characterize a practical problem completely. For instance, in a road network several parameters (as time, cost, distance, etc.) can be assigned to each arc. Clearly, the shortest path may be too expensive to be used. Nevertheless the decision-maker must be able to choose some solution, possibly not the best for all the criteria.In this paper we present two algorithms for this problem. One of them is an immediate generalization of the multiple labelling scheme algorithm of Hansen for the bicriteria case. Based on this algorithm, it is proved that any pair of nondominated paths can be connected by nondominated paths. This result is the support of an algorithm that can be viewed as a variant of the simplex method used in continuous linear multiobjective programming. A small example is presented for both algorithms.     

Algorithms for nonlinear integer bicriterion problems

Two algorithms to solve the nonlinear bicriterion integer mathematical programming (BIMP) problem are presented. One is a noninteractive procedure that generates the entire efficient set, and the second one is an interactive procedure that determines the best compromise solution of the decision maker (DM). A Tchebycheff norm related approach is used for generating the efficient points for the BIMP problem. An application of the interactive procedure for a quality control problem is also presented.This research was supported by the National Science Foundation Grant No. ECS-82-12076 with the University of Oklahoma.     

Solving combinatorial problems with combined Min-Max-Min-Sum objective and applications

The purpose of this paper is to introduce and study a new class of combinatorial optimization problems in which the objective function is the algebraic sum of a bottleneck cost function (Min-Max) and a linear cost function (Min-Sum). General algorithms for solving such problems are described and general complexity results are derived. A number of examples of application involving matchings, paths and cutsets, matroid bases, and matroid intersection problems are examined, and the general complexity results are specialized to each of them. The interest of these various problems comes in particular from their strong relation to other important and difficult combinatorial problems such as: weighted edge coloring of a graph; optimum weighted covering with matroid bases; optimum weighted partitioning with matroid intersections, etc. Another important area of application of the algorithms given in the paper is bicriterion analysis involving a Min-Max criterion and a Min-Sum one.     

An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems

In this paper an algorithm is presented for determining the K best paths that may contain cycles in a directed network.The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed.The proposed algorithm can be used not only for the classical K shortest paths problem but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists.Computational results are presented and comparisons with other approaches for the classical problem are made.     

Criss-cross methods: A fresh view on pivot algorithms

Criss-cross methods are pivot algorithms that solve linear programming problems in one phase starting with any basic solution. The first finite criss-cross method was invented by Chang, Terlaky and Wang independently. Unlike the simplex method that follows a monotonic edge path on the feasible region, the trace of a criss-cross method is neither monotonic (with respect to the objective function) nor feasibility preserving. The main purpose of this paper is to present mathematical ideas and proof techniques behind finite criss-cross pivot methods. A recent result on the existence of a short admissible pivot path to an optimal basis is given, indicating shortest pivot paths from any basis might be indeed short for criss-cross type algorithms. The origins and the history of criss-cross methods are also touched upon.     

Multiobjective shortest path problems with lexicographic goal-based preferences

Multiobjective shortest path problems are computationally harder than single objective ones. In particular, execution time is an important limiting factor in exact multiobjective search algorithms. This paper explores the possibility of improving search performance in those cases where the interesting portion of the Pareto front can be initially bounded. We introduce a new exact label-setting algorithm that returns the subset of Pareto optimal paths that satisfy a set of lexicographic goals, or the subset that minimizes deviation from goals if these cannot be fully satisfied. Formal proofs on the correctness of the algorithm are provided. We also show that the algorithm always explores a subset of the labels explored by a full Pareto search. The algorithm is evaluated over a set of problems with three objectives, showing a performance improvement of up to several orders of magnitude as goals become more restrictive.     

Interactive bicriterion solution method and its application to critical path method problems

An interactive solution method is developed for bicriterion mathematical programming (BCMP) problems. The new method, called the dichotomous bicriterion mathematical programming (DBCMP) method, combines Tchebycheff theory and the existing paired comparison method (PCM). The DBCMP method is then compared with the PCM method based on critical path method problems with two conflicting objectives: minimizing the total crashing cost and minimizing the total project completion time. The extension of the DBCMP method to BCMP problems with multiple decision makers is also discussed.     

Dynamic programming and minimum risk paths

This paper addresses the problem of computing minimum risk paths by taking as objective the expected accident cost. The computation is based on a dynamic programming formulation which can be considered an extension of usual dynamic programming models: path costs are recursively computed via functions which are assumed to be monotonic. A large part of the paper is devoted to analyze in detail this formulation and provide some new results. Based on the dynamic programming model a linear programming model is also presented to compute minimum risk paths. This formulation turns out to be useful in solving a biobjective version of the problem, in which also expected travel length is taken into consideration. This leads to define nondominated mixed strategies. Finally it is shown how to extend the basic updating device of dynamic programming in order to enumerate all nondominated paths.     

Cone convexity,cone extreme points,and nondominated solutions in decision problems with multiobjectives

Although there is no universally accepted solution concept for decision problems with multiple noncommensurable objectives, one would agree that agood solution must not be dominated by the other feasible alternatives. Here, we propose a structure of domination over the objective space and explore the geometry of the set of all nondominated solutions. Two methods for locating the set of all nondominated solutions through ordinary mathematical programming are introduced. In order to achieve our main results, we have introduced the new concepts of cone convexity and cone extreme point, and we have explored their main properties. Some relevant results on polar cones and polyhedral cones are also derived. Throughout the paper, we also pay attention to an important special case of nondominated solutions, that is, Pareto-optimal solutions. The geometry of the set of all Pareto solutions and methods for locating it are also studied. At the end, we provide an example to show how we can locate the set of all nondominated solutions through a derived decomposition theorem.     

A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems

Most real-life decision-making activities require more than one objective to be considered. Therefore, several studies have been presented in the literature that use multiple objectives in decision models. In a mathematical programming context, the majority of these studies deal with two objective functions known as bicriteria optimization, while few of them consider more than two objective functions. In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions. In this algorithm, the search is managed over (p − 1)-dimensional rectangles where p represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known ε-constraint scalarization and its contribution lies in the way rectangles are defined and tracked. The algorithm is compared with former studies on multiobjective knapsack and multiobjective assignment problem instances. The method is highly competitive in terms of solution time and the number of optimization models solved.     

Solving multiple criteria problems by interactive decomposition

An interactive decomposition method is developed for solving the multiple criteria (MC) problem. Based on nonlinear programming duality theory, the MC problem is decomposed into a series of subproblems and relaxed master problems. Each subproblem is a bicriterion problem, and each relaxed master problem is a standard linear program. The prime objective of the decomposition is to simplify and facilitate the process of making preference assessments and tradeoffs across many conflicting objectives. Therefore, the decision-maker's preference function is not assumed to be known explicitly; rather, the decision maker is required to make only limited local preference assessments in the context of feasible and nondominated alternatives. Also, the preference assessments are of the form of ordinal paired comparisons, and in most of them only two criteria are allowed to change their values simultaneously, while the remaining (l–2) criteria are held fixed at certain levels.     

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

Multiplicative programming problems (MPPs) are global optimization problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programmes (MOLPs) to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration, instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLPs, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our algorithms to a recent global optimization algorithm for linear MPPs from the literature as well as two general global optimization solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus, we demonstrate that the use of multi-objective optimization techniques can be beneficial to solve difficult single objective global optimization problems.     

An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

Bicriterion shortest hyperpaths in random time-dependent networks

In relevant application areas, such as transportation and telecommunications,there has recently been a growing focus on random time-dependentnetworks (RTDNs), where arc lengths are represented by time-dependentdiscrete random variables. In such networks, an optimal routingpolicy does not necessarily correspond to a path, but ratherto an adaptive strategy. Finding an optimal strategy reducesto a shortest hyperpath problem that can be solved quite efficiently. The bicriterion shortest path problem, i.e. the problem offinding the set of efficient paths, has been extensively studiedfor many years. Recently, extensions to RTDNs have been investigated.However, no attempt has been made to study bicriterion strategies.This is the aim of this paper. Here we model bicriterion strategy problems in terms of bicriterionshortest hyperpaths, and we devise an algorithm for enumeratingthe set of efficient hyperpaths. Since the computational effortrequired for a complete enumeration may be prohibitive, we proposesome heuristic methods to generate a subset of the efficientsolutions. Different criteria are considered, such as expectedor maximum travel time or cost; a computational experience isreported.     

Using aspiration levels in an interactive interior multiobjective linear programming algorithm

In this paper, we propose the use of an interior-point linear programming algorithm for multiple objective linear programming (MOLP) problems. At each iteration, a Decision Maker (DM) is asked to specify aspiration levels for the various objectives, and an achievement scalarizing function is applied to project aspiration levels onto the nondominated set. The interior-point algorithm is used to find an interior solution path from a starting solution to a nondominated solution corresponding to the optimum of the achievement scalarizing function. The proposed approach allows the DM to re-specify aspiration levels during the solution process and thus steer the interior solution path toward different areas in objective space. We illustrate the use of the approach with a numerical example.     

Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function

This paper presents a direct extension of the label setting algorithm proposed by Martins in 1984 for the shortest path problem with multiple objectives. This extended version computes all the efficient paths from a given source vertex, to all the other vertices of the network. The algorithm copes with problems in which the "cost values" associated with the network arcs are positive. The proposed extension can handle objective functions that are either of the "sum" type or of the "bottleneck" type. The main modifications to Martins' algorithm for multi-objective shortest path problems are linked to the dominance test and the procedure for identifying efficient paths. The algorithmic features are described and a didactic example is provided to illustrate the working principle. The results of numerical experiments concerning the number of efficient solutions produced and the CPU time consumed for several configurations of objectives, on a set of randomly generated networks, are also provided. Received: February 2005 / Revised version: June 2005 AMS classification: 90C29, 90C27, 05C38, 90B18, 68M12     

A reference direction approach to multiple objective quadratic-linear programming

In this paper, we propose an interactive procedure for solving multiple criteria problems with one quadratic objective, several linear objectives, and a set of linear constraints. The procedure is based on the use of reference directions and weighted sums. Reference directions for the linear functions, and weighted sums for combining the quadratic function with the linear ones are used as parameters to implement the free search of nondominated solutions. The idea leads to the parametric linear complementarity problem formulation. An approach to deal with this type of problems is given as well. The approach is illustrated with a numerical example.     

Finding a representative nondominated set for multi-objective mixed integer programs

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.     

Finding all nondominated points of multi-objective integer programs

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.     

Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function

In this paper, the stochastic shortest path problem of determining a path that maximizes the expected utility is considered. The nature of the utility function used to evaluate paths is of a decreasing deadline type. The principal contribution of this paper is the development of exact algorithms that use two types of pruning techniques that are incorporated in labeling procedures. One type of pruning makes use of the concept of local preference relations while the other type makes use of relaxations. Specifically two algorithms are developed, each containing the same preference relation, but two different relaxations. Our extensive computational testing indicate that both these algorithms are able to solve even large size problems quickly. More importantly, even for large problems, both the algorithms solved them by enumerating a very small percentage of all paths.