Primal-Dual Simplex Method for Multiobjective Linear Programming

We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research. The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121. We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.     

Thep-facility ordered median problem on networks

In this paper we deal with the ordered median problem: a family of location problems that allows us to deal with a large number of real situations which does not fit into the standard models of location analysis. Moreover, this family includes as particular instances many of the classical location models. Here, we analyze thep-facility version of this problem on networks and our goal is to study the structure of the set of candidate points to be optimal solutions. The research of the authors is partially financed by Spanish research grants BFM2001-2378, BFM2001-4028, BFM2004-0909 and HA2003-0121.     

Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier

New hybrid methods for approximating the Pareto frontier of the feasible set of criteria vectors in nonlinear multicriteria optimization problems with nonconvex Pareto frontiers are considered. Since the approximation of the Pareto frontier is an ill-posed problem, the methods are based on approximating the Edgeworth-Pareto hull (EPH), i.e., the maximum set having the same Pareto frontier as the original feasible set of criteria vectors. The EPH approximation also makes it possible to visualize the Pareto frontier and to estimate the quality of the approximation. In the methods proposed, the statistical estimation of the quality of the current EPH approximation is combined with its improvement based on a combination of random search, local optimization, adaptive compression of the search region, and genetic algorithms.     

Multicriteria identification sets method

A multicriteria identification and prediction method for mathematical models of simulation type in the case of several identification criteria (error functions) is proposed. The necessity of the multicriteria formulation arises, for example, when one needs to take into account errors of completely different origins (not reducible to a single characteristic) or when there is no information on the class of noise in the data to be analyzed. An identification sets method is described based on the approximation and visualization of the multidimensional graph of the identification error function and sets of suboptimal parameters. This method allows for additional advantages of the multicriteria approach, namely, the construction and visual analysis of the frontier and the effective identification set (frontier and the Pareto set for identification criteria), various representations of the sets of Pareto effective and subeffective parameter combinations, and the corresponding predictive trajectory tubes. The approximation is based on the deep holes method, which yields metric ε-coverings with nearly optimal properties, and on multiphase approximation methods for the Edgeworth–Pareto hull. The visualization relies on the approach of interactive decision maps. With the use of the multicriteria method, multiple-choice solutions of identification and prediction problems can be produced and justified by analyzing the stability of the optimal solution not only with respect to the parameters (robustness with respect to data) but also with respect to the chosen set of identification criteria (robustness with respect to the given collection of functionals).     

Generalized Maximin Solutions in Multicriteria Bargaining

In this paper we address bargaining games where the agents have to take into account different criteria to value the decisions. We propose the class of generalized maximin solutions, as the natural extension for these games of the maximin solutions in conventional bargaining. In order to refine this solution concept, we define a multicriteria lexicographic partial ordering and present the class of generalized leximin solutions as those that are nondominated with respect to this relation. We establish some properties of these solutions and characterize them as solutions of multicriteria problems. The research of the authors is partially supported by the Spanish Ministry of Science and Technology projects BFM2002-11282-E and BEC2003-03111.     

The multicriteria p-facility median location problem on networks

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.     

Decomposition of generalized vector variational inequalities

A multicriteria optimization problem is called Pareto reducible if its weakly efficient solutions actually are efficient solutions for the problem itself or for at least one subproblem obtained from it by selecting certain criteria. The aim of this paper is to investigate a similar property within a special class of generalized vector variational inequalities, under appropriate generalized convexity assumptions.     

鲁棒优化中的Pareto有效性

对于一般的不确定优化问题, 研究了鲁棒解的~Pareto 有效性. 首先, 证明了Pareto 鲁棒解集即是鲁棒解集的Pareto 有效集, 因此求Pareto 鲁棒解等价于求鲁棒解集的Pareto 有效元. 其次, 基于推广的epsilon-约束方法, 得到了Pareto 鲁棒解的生成方法.     

On the quasistability of trajectory problems of vector optimization

We consider quasistable multicriteria problems of discrete optimization on systems of subsets (trajectory problems). We single out the class of problems for which new Pareto optima can appear, while other optima for the problems do not disappear when the coefficients of the objective functions are slightly perturbed (in the Chebyshev metric). For the case of linear criteria (MINSUM), we obtain a formula for calculating the quasistability radius of the problem. Translated fromMatemalicheskie Zametki, Vol. 63, No. 1, pp. 21–27, January, 1998. This research was supported by the Belarus Foundation for Basic Research under grant No. F95-70.     

Efficiency and Optimality in Minisum,Minimax 0-1 Programming Problems

Inspired by an increasing interest in multicriteria 0-1 programming problems in general and by a recent result on the reducibility of minimax to minisum problems in particular, we consider properties of efficient and optimal solutions to two-criteria (minisum and minimax) 0-1 programming problems with any constraint set.A solution procedure is suggested for solving problems whose objective functions are a convex combination of these criteria. The solution properties are illustrated with examples mainly within the context of locational decision problems.     

On the cardinality of the Pareto set in bicriteria shortest path problems

Computing shortest paths with two or more conflicting optimization criteria is a fundamental problem in transportation and logistics. We study the problem of finding all Pareto-optimal solutions for the multi-criteria single-source shortest-path problem with nonnegative edge lengths. The standard approaches are generalizations of label-setting (Dijkstra) and label-correcting algorithms, in which the distance labels are multi-dimensional and more than one distance label is maintained for each node. The crucial parameter for the run time and space consumption is the total number of Pareto optima. In general, this value can be exponentially large in the input size. However, in various practical applications one can observe that the input data has certain characteristics, which may lead to a much smaller number—small enough to make the problem efficiently tractable from a practical viewpoint. For typical characteristics which occur in various applications we study in this paper whether we can bound the size of the Pareto set to a polynomial size or not. These characteristics are also evaluated (1) on a concrete application scenario (computing the set of best train connections in view of travel time, fare, and number of train changes) and (2) on a simplified randomized model. It will turn out that the number of Pareto optima on each visited node is restricted by a small constant in our concrete application, and that the size of the Pareto set is much smaller than our worst case bounds in the randomized model. A preliminary short version of this paper appeared in the Proceedings of the 5th Workshop on Algorithm Engineering (WAE 2001), LNCS 2141, Springer Verlag, pp. 185–197 (2001) under the title “Pareto shortest paths is often feasible in practice.”     

A multicriteria approach to the location of public facilities

We argue that practical problems involving the location of public facilities are really multicriteria problems, and ought to be modeled as much. The general criteria are those of cost and service, but there exist several distinct criteria in each of those two categories. For the first category, fixed investment cost, fixed operating cost, variable operating cost, total operating cost, and total discounted cost are all reasonable criteria to consider. In terms of service, both demand served and response time (or distance traveled) are appropriate criteria, either agglomerated or considered on the basis of the individual clients. In this paper we treat such multicriteria questions in the framework of a model for selecting a subset of M sites at which to establish public facilities in order to serve client groups located at N distinct points. We show that for some combinations of specific criteria, parametric solutions of a generalized assignment problem (GAP) will yield all efficient solution. In most other cases the efficient solutions can be found through parametric solution of a GAP with additional constraints of a type which can be incorporated into an existing algorithm for the GAP. Rather than attempting to find all efficient solutions, however, we advocate an interactive approach to the resolution of multicriteria location problems and elaborate on a specific interactive algorithm for multicriteria optimization which for the present model solves a finite sequence of GAP's or GAP-type problems. Finally, some similar aspects of private sector location problems are discussed.     

A new Pareto set generating method for multi-criteria optimization problems

This paper proposes a new classical method to capture the complete Pareto set of a multi-criteria optimization problem (MOP) even without having any prior information about the location of Pareto surface. The solutions obtained through the proposed method are globally Pareto optimal. Moreover, each and every global Pareto optimal point is within the attainable range. This paper also suggests a procedure to ensure the proper Pareto optimality of the outcomes if slight modifications are allowed in the constraint set of the MOP under consideration. Among the set of all outcomes, the proposed method can effectively detect the regions of unbounded trade-offs between the criteria, if they exist.     

A provably convergent heuristic for stochastic bicriteria integer programming

We propose a general-purpose algorithm APS (Adaptive Pareto-Sampling) for determining the set of Pareto-optimal solutions of bicriteria combinatorial optimization (CO) problems under uncertainty, where the objective functions are expectations of random variables depending on a decision from a finite feasible set. APS is iterative and population-based and combines random sampling with the solution of corresponding deterministic bicriteria CO problem instances. Special attention is given to the case where the corresponding deterministic bicriteria CO problem can be formulated as a bicriteria integer linear program (ILP). In this case, well-known solution techniques such as the algorithm by Chalmet et al. can be applied for solving the deterministic subproblem. If the execution of APS is terminated after a given number of iterations, only an approximate solution is obtained in general, such that APS must be considered a metaheuristic. Nevertheless, a strict mathematical result is shown that ensures, under rather mild conditions, convergence of the current solution set to the set of Pareto-optimal solutions. A modification replacing or supporting the bicriteria ILP solver by some metaheuristic for multicriteria CO problems is discussed. As an illustration, we outline the application of the method to stochastic bicriteria knapsack problems by specializing the general framework to this particular case and by providing computational examples.     

Uniform convergence and Pareto optimality

In this paper we consider the following problem: Is it possible to obtain a good approximation of the set of Pareto (Slater) solutions to a multicriteria optimization problem if the objective function is approximated by another sufficiently close function ?.     

Solvability of the vector problem by the linear criteria convolution algorithm

Conditions are found under which a multicriteria problem with a finite set of vector estimates is solvable by means of the linear criteria convolution (LCC) algorithm, that is, any Pareto optimum for the problem can be obtained as an optimum solution to a one-criterion problem with an aggregated criterion defined as an LCC. Also, an algorithm is suggested that is polynomial in dimension and reduces any problem with minimax and minimin criteria to an equivalent vector problem with the same Pareto set solvable by the LCC algorithm. Translated fromMatematicheskie Zametki, Vol. 62, No. 4, pp. 502–509, October, 1997. Translated by V. N. Dubrovsky     

Cone contraction and reference point methods for multi-criteria mixed integer optimization

Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).     

On a measure of quasistability of a certain vector linearly combinatorial Boolean problem

We consider a multicriteria problem of finding the Pareto set in the case when linear forms (functions) are minimized both on a set of permutations and on a set of Boolean vectors. We obtain a formula for the radius of that type of the problem stability (with respect to perturbations of parameters of the vector criterion) that guarantees the preservation of all Pareto optimal solutions of the initial problem and allows the occurrence of new ones.