Asymptotic analysis for multi-objective sequential stochastic assignment problems

ABSTRACT

We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector and compare the convergence rates for three classes of Pareto optimal policies.     

Resource allocation model and double-sphere crowding distance for evolutionary multi-objective optimization

Convergence speed and diversity of nondominated solutions are two important performance indicators for Multi-Objective Evolutionary Algorithms (MOEAs). In this paper, we propose a Resource Allocation (RA) model based on Game Theory to accelerate the convergence speed of MOEAs, and a novel Double-Sphere Crowding Distance (DSCD) measure to improve the diversity of nondominated solutions. The mechanism of RA model is that the individuals in each group cooperate with each other to get maximum benefits for their group, and then individuals in the same group compete for private interests. The DSCD measure uses hyper-spheres consisting of nearest neighbors to estimate the crowding degree. Experimental results on convergence speed and diversity of nondominated solutions for benchmark problems and a real-world problem show the efficiency of these two proposed techniques.     

Robustness in deterministic multi-objective linear programming with respect to the relative interior and angle deviation

This paper deals with the robustness issue in deterministic multi-objective linear programming from two new standpoints. It is shown that a robustness notion recently reported in the literature is equivalent to strict efficiency. Corresponding to an efficient solution, a new quantity, robustness order (RO) is defined with respect to the interiority order of the cost matrix in the binding cone. A linear programming problem is provided to calculate the RO of a given efficient solution. The second part of the paper is devoted to investigating the robustness with respect to the eligible angle deviation of the cost matrix in the binding cone. Theoretical results are given to obtain the maximum eligible angle deviation. Finally, the relationship between two above-mentioned robustness standpoints is established. To have a better geometrical view, we prove the results for single-objective LP problems at first, and then we extend them to the multi-objective case. In addition to the theoretical results, some clarifying examples are given.     

Connectivity interdiction

We consider the problem of maximally decreasing the edge-connectivity of an edge-weighted graph by removing a limited set of edges. This problem, which we term connectivity interdiction, falls into a large family of so-called interdiction problems, which have been considered in a variety of contexts. Whereas little is known about the approximability of most interdiction problems, we show that connectivity interdiction admits a PTAS, and a natural special case of it can even be solved efficiently.     

Multi-objective optimal design of feedback controls for dynamical systems with hybrid simple cell mapping algorithm

This paper presents a study of multi-objective optimal design of full state feedback controls. The goal of the design is to minimize several conflicting performance objective functions at the same time. The simple cell mapping method with a hybrid algorithm is used to find the multi-objective optimal design solutions. The multi-objective optimal design comes in a set of gains representing various compromises of the control system. Examples of regulation and tracking controls are presented to validate the control design.     

Logic optimality for multi-objective optimization

Pareto dominance is one of the most basic concepts in multi-objective optimization. However, it is inefficient when the number of objectives is large because in this case it leads to an unmanageable number of Pareto solutions. In order to solve this problem, a new concept of logic dominance is defined by considering the number of improved objectives and the quantity of improvement simultaneously, where probabilistic logic is applied to measure the quantity of improvement. Based on logic dominance, the corresponding logic nondominated solution is defined as a feasible solution which is not dominated by other ones based on this new relationship, and it is proved that each logic nondominated solution is also a Pareto solution. Essentially, logic dominance is an extension of Pareto dominance. Since there are already several extensions for Pareto dominance, some comparisons are given in terms of numerical examples, which indicates that logic dominance is more efficient. As an application of logic dominance, a house choice problem with five objectives is considered.     

An effective solution for a real cutting stock problem in manufacturing plastic rolls

We confront a practical cutting stock problem from a production plant of plastic rolls. The problem is a variant of the well-known one dimensional cutting stock, with particular constraints and optimization criteria defined by the experts of the company. We start by giving a problem formulation in which optimization criteria have been considered in linear hierarchy according to expert preferences, and then propose a heuristic solution based on a GRASP algorithm. The generation phase of this algorithm solves a simplified version which is rather similar to the conventional one dimensional cutting stock. To do that, we propose a Sequential Heuristic Randomized Procedure (SHRP). Then in the repairing phase, the solution of the simplified problem is transformed into a solution to the real problem. For experimental study we have chosen a set of problem instances of com-mon use to compare SHRP with another recent approach. Also, we show by means of examples, how our approach works over instances taken from the real production process. All authors are supported by MEC-FEDER Grant TIN2007-67466-C02-01 and by contract CN-05-127 of the University of Oviedo and the company ERVISA, and by FICYT under grant BP04-021.     

Implementing an efficient fptas for the 0–1 multi-objective knapsack problem

In the present work, we are interested in the practical behavior of a new fully polynomial time approximation schemes (fptas) to solve the approximation version of the 0–1 multi-objective knapsack problem. The proposed methodology makes use of very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well.     

模糊多目标半定规划的最优性条件

将模糊集理论应用到多目标半定规划中来,提出了有约束的模糊多目标半定规划模型,并首次给出了其最优有效解的定义.通过构造确定的隶属度函数,将以矩阵为决策变量的模糊多目标半定规划转化为一种目标函数的某些分量由约束函数决定的确定性多目标半定规划,并证明了前者最优有效解与后者有效解的一致性.在此基础之上,讨论了二者的最优性条件.     

Multi-objective Bayesian Artificial Immune System: Empirical Evaluation and Comparative Analyses

Recently, we have proposed a Multi-Objective Bayesian Artificial Immune System (MOBAIS) to deal effectively with building blocks (high-quality partial solutions coded in the solution vector) in combinatorial multi-objective problems. By replacing the mutation and cloning operators with a probabilistic model, more specifically a Bayesian network representing the joint distribution of promising solutions, MOBAIS takes into account the relationships among the variables of the problem, avoiding the disruption of already obtained high-quality partial solutions. The preliminary results have indicated that our proposal is able to properly build the Pareto front. Motivated by this scenario, this paper better formalizes the proposal and investigates its usefulness on more challenging problems. In addition, an important enhancement regarding the Bayesian network learning was incorporated into the algorithm in order to speed up its execution. To conclude, we compare MOBAIS with state-of-the-art algorithms taking into account quantitative aspects of the Pareto front found by the algorithms. MOBAIS outperforms the contenders in terms of the quality of the obtained solutions and requires an amount of computational resource inferior or compatible with the contenders.