Higher-order necessary and sufficient conditions for strict local pareto minima in terms of Studniarski's derivatives

In this article, we establish higher-order necessary and sufficient conditions for strict local Pareto minima of nonsmooth multiobjective programing problems in terms of Studniarski's derivatives of higher order.     

Algorithms for Pareto optimal exchange with bounded exchange cycles

We consider exchange markets with single-unit endowments and demands where there is a bound on the size of the exchange cycles. The computational problem we study is that of computing a Pareto optimal and individually rational allocation. We present polynomial-time algorithms to compute a Pareto optimal and individually rational allocation when preferences are strict, the exchange bound is two, or when Pareto optimality is replaced with weak Pareto optimality.     

Generalized Homotopy Approach to Multiobjective Optimization

This paper proposes a new generalized homotopy algorithm for the solution of multiobjective optimization problems with equality constraints. We consider the set of Pareto candidates as a differentiable manifold and construct a local chart which is fitted to the local geometry of this Pareto manifold. New Pareto candidates are generated by evaluating the local chart numerically. The method is capable of solving multiobjective optimization problems with an arbitrary number k of objectives, makes it possible to generate all types of Pareto optimal solutions, and is able to produce a homogeneous discretization of the Pareto set. The paper gives a necessary and sufficient condition for the set of Pareto candidates to form a (k-1)-dimensional differentiable manifold, provides the numerical details of the proposed algorithm, and applies the method to two multiobjective sample problems.     

Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies

Pareto local search (PLS) methods are local search algorithms for multi-objective combinatorial optimization problems based on the Pareto dominance criterion. PLS explores the Pareto neighbourhood of a set of non-dominated solutions until it reaches a local optimal Pareto front. In this paper, we discuss and analyse three different Pareto neighbourhood exploration strategies: best, first, and neutral improvement. Furthermore, we introduce a deactivation mechanism that restarts PLS from an archive of solutions rather than from a single solution in order to avoid the exploration of already explored regions. To escape from a local optimal solution set we apply stochastic perturbation strategies, leading to stochastic Pareto local search algorithms (SPLS). We consider two perturbation strategies: mutation and path-guided mutation. While the former is unbiased, the latter is biased towards preserving common substructures between 2 solutions. We apply SPLS on a set of large, correlated bi-objective quadratic assignment problems (bQAPs) and observe that SPLS significantly outperforms multi-start PLS. We investigate the reason of this performance gain by studying the fitness landscape structure of the bQAPs using random walks. The best performing method uses the stochastic perturbation algorithms, the first improvement Pareto neigborhood exploration and the deactivation technique.     

Selling to the “Newsvendor” with a forecast update: Analysis of a dual purchase contract

We consider a supply chain in which a manufacturer sells to a procure-to-stock retailer facing a newsvendor problem with a forecast update. Under a wholesale price contract, the retailer waits as long as she can and optimally places her order after observing the forecast update. We show that the retailer’s wait-and-decide strategy, induced by the wholesale price contract, hinders the manufacturer’s ability to (1) set the wholesale price and maximize his profit, (2) hedge against excess inventory risk, and (3) reduce his profit uncertainty. To mitigate the adverse effect of wholesale price contract, we propose the dual purchase contract, through which the manufacturer provides a discount for orders placed before the forecast update. We characterize how and when a dual purchase contract creates strict Pareto improvement over a wholesale price contract. To do so, we establish the retailer’s optimal ordering policy and the manufacturer’s optimal pricing and production policies. We show how the dual purchase contract reduces profit variability and how it can be used as a risk hedging tool for a risk averse manufacturer. Through a numerical study, we provide additional managerial insights and show, for example, that market uncertainty is a key factor that defines when the dual purchase contract provides strict Pareto improvement over the wholesale price contract.     

Strategy-proofness and the strict core in a market with indivisibilities

We show that, in markets with indivisibilities (typified by the Shapley-Scarf housing market), the strict core mechanism is categorically determined by three assumptions: individual rationality, Pareto optimality and strategy-proofness.     

Characterization of the core in full domain marriage problems

In this paper, we study the core of two-sided, one-to-one matching problems. First, in a model in which agents have strict preferences over their potential mates and are allowed to remain single, we characterize the core as the unique solution that satisfies individual rationality, Pareto optimality, gender fairness, consistency, and converse consistency. Next, in a model that relaxes the constraint that agents have strict preferences over their potential mates, we show that no solution exists that satisfies Pareto optimality, anonymity, and converse consistency. In this full domain, we characterize the core by individual rationality, weak Pareto optimality, monotonicity, gender fairness, consistency, and converse consistency.     

Variable and large neighborhood search to solve the multiobjective set covering problem

In this paper, we study the multiobjective version of the set covering problem. To our knowledge, this problem has only been addressed in two papers before, and with two objectives and heuristic methods. We propose a new heuristic, based on the two-phase Pareto local search, with the aim of generating a good approximation of the Pareto efficient solutions. In the first phase of this method, the supported efficient solutions or a good approximation of these solutions is generated. Then, a neighborhood embedded in the Pareto local search is applied to generate non-supported efficient solutions. In order to get high quality results, two elaborate local search techniques are considered: a large neighborhood search and a variable neighborhood search. We intensively study the parameters of these two techniques. We compare our results with state-of-the-art results and we show that with our method, better results are obtained for different indicators.     

Non-Contradictory Aggregation of Strict Order Relations

We study the problem of collective choice. The profile of individual preferences of experts is defined by relations of strict order. A non-contradictory aggregate preference relation is based on the weighted majority graph that characterizes the degree of superiority of one alternative over another. The aggregate relation also defines a strict order and satisfies requirements to group decisions, namely, the monotony, the preservation of the Pareto relation, the minimality of the distance to expert preferences.     

阿罗不可能性定理的几个等价形式

在这篇短中。给出了关于社会福利函数F的防止策略性操纵的概念,并且证明了如果备选对象至少有三个。则下面结论是相互等价的：(1)F满足Pareto与IIA性质;(2)F满足Pareto与RID性质;(3)F是独裁的;(4)F是满的、正向响应的;(5)F是防止策略操纵的且F是满的。     

Probabilistic clustering via Pareto solutions and significance tests

The present paper proposes a new strategy for probabilistic (often called model-based) clustering. It is well known that local maxima of mixture likelihoods can be used to partition an underlying data set. However, local maxima are rarely unique. Therefore, it remains to select the reasonable solutions, and in particular the desired one. Credible partitions are usually recognized by separation (and cohesion) of their clusters. We use here the p values provided by the classical tests of Wilks, Hotelling, and Behrens–Fisher to single out those solutions that are well separated by location. It has been shown that reasonable solutions to a clustering problem are related to Pareto points in a plot of scale balance vs. model fit of all local maxima. We briefly review this theory and propose as solutions all well-fitting Pareto points in the set of local maxima separated by location in the above sense. We also design a new iterative, parameter-free cutting plane algorithm for the multivariate Behrens–Fisher problem.     

A goodness-of-fit statistic for Pareto-type behaviour

The fit of a statistical model can be visually assessed by inspection of a quantile–quantile or QQ plot. For the strict Pareto distribution, since log-transformed Pareto random variables are exponentially distributed, it is natural to consider an exponential quantile plot based on the log-transformed data. In case the data originate from a Pareto-type distribution, the Pareto quantile plot will be linear but only in some of the largest observations. In this paper we modify the Jackson statistic, originally proposed as a goodness-of-fit statistic for testing exponentiality, in such a way that it measures the linearity of the k largest observations on the Pareto quantile plot. Further, by taking the second-order tail behaviour of a Pareto-type model into account we construct a bias-corrected Jackson statistic. For both statistics the limiting distribution is derived. Next to these asymptotic results we also evaluate the small sample behaviour on the basis of a simulation study. The method is illustrated on two practical case studies.     

Inconsistency indices for pairwise comparisons and the Pareto dominance principle

We consider the problem of quantifying inconsistency in pairwise comparisons and valued-preferences. A wide range of indices have been proposed in the literature to perform this task, and two sets of conditions have been introduced to validate such indices. We summarize some criticisms from the literature and we add more evidence to show that neither of the two systems is adequate in its current formulation. Thanks to the widely accepted concept of weak Pareto dominance, we formulate a new property. We argue that a simple regularity condition and this new property can overcome the shortcomings of the two axiomatic systems, and represents a significantly simpler framework. Finally, we claim that, if we had resorted to strict Pareto dominance, we would have needed just one axiom.     

Target aiming Pareto search and its application to the vehicle routing problem with route balancing

In this paper, we present a solution method for a bi-objective vehicle routing problem, called the vehicle routing problem with route balancing (VRPRB), in which the total length and balance of the route lengths are the objectives under consideration. The method, called Target Aiming Pareto Search, is defined to hybridize a multi-objective genetic algorithm for the VRPRB using local searches. The method is based on repeated local searches with their own appropriate goals. We also propose an implementation of the Target Aiming Pareto Search using tabu searches, which are efficient meta-heuristics for the vehicle routing problem. Assessments with standard metrics on classical benchmarks demonstrate the importance of hybridization as well as the efficiency of the Target Aiming Pareto Search.     

Pareto optimal matchings with lower quotas

We consider the problem of allocating applicants to courses, where each applicant has a capacity, possibly greater than 1, and a subset of acceptable courses that she ranks in a strict order of preference. Each course has a lower and an upper quota, indicating that if it is assigned some applicants then their number has to be between these two bounds. We further suppose that applicants extend their preferences over courses to preferences over bundles of courses lexicographically.In this setting we present several algorithmic results concerned with the computation of Pareto optimal matchings (POMs). Firstly, we extend the Serial Dictatorship with Project Closures mechanism to the case when an applicant can be assigned more than one course. We show that unlike in the one-to-many case no mechanism is strategy-proof against dropping manipulations and that this mechanism is strategy-proof against reordering strategies only for some picking sequences. We further show the intractability of the following problems: deciding about the Pareto optimality of a given matching, computation of a POM with maximum cardinality and computation of a POM in case of indifferences.     

Multiobjective Problems: Enhanced Necessary Conditions and New Constraint Qualifications through Convexificators

In this paper, we study necessary optimality conditions for local Pareto and weak Pareto solutions of multiobjective problems involving inequality and equality constraints in terms of convexificators. We develop the enhanced Karush–Kuhn–Tucker conditions and introduce the associated pseudonormality and quasinormality conditions. We also introduce several other new constraint qualifications which entirely depend on the feasible set. Then a connecting link between these constraint qualifications is presented. Moreover, we provide several examples that clarify the interrelations between the different results that we have established.     

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.     

Necessary and sufficient conditions for local Pareto optimality on time scales

We study a multiobjective variational problem on time scales. For this problem, necessary and sufficient conditions for weak local Pareto optimality are given. We also prove a necessary optimality condition for the isoperimetric problem with multiple constraints on time scales.