Solving fuzzy queueing decision problems via a parametric mixed integer nonlinear programming method

This paper proposes a mathematical programming method to construct the membership functions of the fuzzy objective value of the cost-based queueing decision problem with the cost coefficients and the arrival rate being fuzzy numbers. On the basis of Zadeh’s extension principle, three pairs of mixed integer nonlinear programs (MINLP) parameterized by the possibility level α are formulated to calculate the lower and upper bounds of the minimal expected total cost per unit time at α, through which the membership function of the minimal expected total cost per unit time of the fuzzy objective value is constructed. To provide a suitable optimal service rate for designing queueing systems, the Yager’s ranking index method is adopted. Two numerical examples are solved successfully to demonstrate the validity of the proposed method. Since the objective value is completely expressed by a membership function rather than by a crisp value, it conserves the fuzziness of the input information, thus more information is provided for designing queueing systems. The successful extension of queueing decision models to fuzzy environments permits queueing decision models to have wider applications in practice.     

An interactive method for multiple-objective mathematical programming problems

An interactive method is developed for solving the general nonlinear multiple objective mathematical programming problems. The method asks the decision maker to provide partial information (local tradeoff ratios) about his utility (preference) function at each iteration. Using the information, the method generates an efficient solution and presents it to the decision maker. In so doing, the best compromise solution is sought in a finite number of iterations. This method differs from the existing feasible direction methods in that (i) it allows the decision maker to consider only efficient solutions throughout, (ii) the requirement of line search is optional, and (iii) it solves the problems with linear objective functions and linear utility function in one iteration. Using various problems selected from the literature, five line search variations of the method are tested and compared to one another. The nonexisting decision maker is simulated using three different recognition levels, and their impact on the method is also investigated.     

On optimality conditions for multiobjective optimization problems in topological vector space

In this paper, we are concerned with a differentiable multiobjective programming problem in topological vector spaces. An alternative theorem for generalized K subconvexlike mappings is given. This permits the establishment of optimality conditions in this context: several generalized Fritz John conditions, in line to those in Hu and Ling [Y. Hu, C. Ling, The generalized optimality conditions of multiobjective programming problem in topological vector space, J. Math. Anal. Appl. 290 (2004) 363-372] are obtained and, in the presence of the generalized Slater's constraint qualification, the Karush-Kuhn-Tucker necessary optimality conditions.     

A dynamic gradient approach to Pareto optimization with nonsmooth convex objective functions

In a general Hilbert framework, we consider continuous gradient-like dynamical systems for constrained multiobjective optimization involving nonsmooth convex objective functions. Based on the Yosida regularization of the subdifferential operators involved in the system, we obtain the existence of strong global trajectories. We prove a descent property for each objective function, and the convergence of trajectories to weak Pareto minima. This approach provides a dynamical endogenous weighting of the objective functions, a key property for applications in cooperative games, inverse problems, and numerical multiobjective optimization.     

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.     

Solving generalized convex multiobjective programming problems by a normal direction method

We use normal directions of the outcome set to develop a method of outer approximation for solving generalized convex multiobjective programming problems. We prove the convergence of the method and report some computational experiments. As an application, we obtain an algorithm to solve an associated multiplicative problem over a convex constraint set.     

Solving Fuzzy Variational Inequalities

This paper studies the variational inequality problem over a fuzzy domain and variational inequalities for fuzzy mappings over a fuzzy domain. It is shown that such problems can be reduced to bilevel programming problems. A penalty function algorithm is introduced with a convergence proof. Numerical examples are also included to illustrate the solution procedure.     

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.     

Solving nonlinear principal-agent problems using bilevel programming

While significant progress has been made, analytic research on principal-agent problems that seek closed-form solutions faces limitations due to tractability issues that arise because of the mathematical complexity of the problem. The principal must maximize expected utility subject to the agent’s participation and incentive compatibility constraints. Linearity of performance measures is often assumed and the Linear, Exponential, Normal (LEN) model is often used to deal with this complexity. These assumptions may be too restrictive for researchers to explore the variety of relationships between compensation contracts offered by the principal and the effort of the agent. In this paper we show how to numerically solve principal-agent problems with nonlinear contracts. In our procedure, we deal directly with the agent’s incentive compatibility constraint. We illustrate our solution procedure with numerical examples and use optimization methods to make the problem tractable without using the simplifying assumptions of a LEN model. We also show that using linear contracts to approximate nonlinear contracts leads to solutions that are far from the optimal solutions obtained using nonlinear contracts. A principal-agent problem is a special instance of a bilevel nonlinear programming problem. We show how to solve principal-agent problems by solving bilevel programming problems using the ellipsoid algorithm. The approach we present can give researchers new insights into the relationships between nonlinear compensation schemes and employee effort.     

Bucket elimination for multiobjective optimization problems

Multiobjective optimization deals with problems involving multiple measures of performance that should be optimized simultaneously. In this paper we extend bucket elimination (BE), a well known dynamic programming generic algorithm, from mono-objective to multiobjective optimization. We show that the resulting algorithm, MO-BE, can be applied to true multi-objective problems as well as mono-objective problems with knapsack (or related) global constraints. We also extend mini-bucket elimination (MBE), the approximation form of BE, to multiobjective optimization. The new algorithm MO-MBE can be used to obtain good quality multi-objective lower bounds or it can be integrated into multi-objective branch and bound in order to increase its pruning efficiency. Its accuracy is empirically evaluated in real scheduling problems, as well as in Max-SAT-ONE and biobjective weighted minimum vertex cover problems.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

Discrete dynamic programming with outcomes in random variable structures

Multiobjective approach is the common way of generalization single-criterion dynamic programming models. Another way is to consider partially ordered criteria structures. That approach is rather rare. The aim of the paper is to present such a model. Generalization of Bellman’s principle of optimality is employed to create a forward procedure to find the set of all maximal elements. As this set is usual large, the second problem under consideration is to find its subsets. To reduce the number of solutions presented to decision maker we propose to apply a family of narrowing relations. That approach is similar to scalarization in multiobjective programming. Ordered structures of random variables based on mean–variance, stochastic dominance and inverse stochastic dominance are considered. Numerical illustration is given at the end of the paper.     

Decision making in multiobjective optimization aided by the multicriteria tournament decision method

This paper proposes a new method for multicriteria analysis, named Multicriteria Tournament Decision (MTD). It provides the ranking of alternatives from best to worst, according to the preferences of a human decision-maker (DM). It has some positive aspects such as: it has a simple algorithm with intuitive appeal; it involves few input parameters (just the importance weight of each criterion).The helpfulness of MTD is demonstrated by using it to select the final solution of multiobjective optimization problems in an a posteriori decision making approach. Having at hand a discrete approximation of the Pareto front (provided by a multiobjective evolutionary search algorithm), the choice of the preferred Pareto-optimal solution is performed using MTD.A simple method, named Gain Analysis method (GAM), for verifying the existence of a better solution (a solution associated to higher marginal rates of return) than the one originally chosen by the DM, is also introduced here. The usefulness of MTD and GAM methods is confirmed by the suitable results shown in this paper.     

一类大系统模糊随机多目标决策的建模与求解方法

本文提出和建立了一类大系统模糊随机多目标决策（ＦＳＭＯＤＭ）模型，讨论了模糊事件的模糊概率的若干基本性质．在此基础上，将ＦＳＭＯＤＭ模型转化为清晰的多目标决策模型，并给出了递阶分解协调求解方法．把该模型应用到大连市水资源与经济发展规划研究中取得了令人满意的结果．     

Analysis of multiobjective decision problems by the indifference band approach

A new approach, based on indifference band, for analyzing problems with multiple objectives is described. The relations of this approach to some previous results are given. Methods for generating nondominated solutions are supplied.     

Solving the linear multiple choice knapsack problem with two objectives: profit and equity

In this paper, we study an extension of the Linear Multiple Choice Knapsack (LMCK) Problem that considers two objectives. The problem can be used to find the optimal allocation of an available resource to a group of disjoint sets of activities, while also ensuring that a certain balance on the resource amounts allocated to the activity sets is attained. The first objective maximizes the profit incurred by the implementation of the considered activities. The second objective minimizes the maximum difference between the resource amounts allocated to any two sets of activities. We present the mathematical formulation and explore the fundamental properties of the problem. Based on these properties, we develop an efficient algorithm that obtains the entire nondominated frontier. The algorithm is more efficient than the application of the general theory of multiple objective linear programming (MOLP), although there is a close underlying relationship between the two. We present theoretical findings which provide insight into the behavior of the algorithm, and report computational results which demonstrate its efficiency for randomly generated problems. Electronic Supplementary Material  The online version of this article () contains supplementary material, which is available to authorized users.     

A discussion of scalarization techniques for multiple objective integer programming

In this paper we consider solution methods for multiobjective integer programming (MOIP) problems based on scalarization. We define the MOIP, discuss some common scalarizations, and provide a general formulation that encompasses most scalarizations that have been applied in the MOIP context as special cases. We show that these methods suffer some drawbacks by either only being able to find supported efficient solutions or introducing constraints that can make the computational effort to solve the scalarization prohibitive. We show that Lagrangian duality applied to the general scalarization does not remedy the situation. We also introduce a new scalarization technique, the method of elastic constraints, which is shown to be able to find all efficient solutions and overcome the computational burden of the scalarizations that use constraints on objective values. Finally, we present some results from an application in airline crew scheduling as evidence. This research is partially supported by University of Auckland grant 3602178/9275 and by the Deutsche Forschungsgemeinschaft grant Ka 477/27-1.     

Asymptotic convergence of a simulated annealing algorithm for multiobjective optimization problems

In this paper we consider a simulated annealing algorithm for multiobjective optimization problems. With a suitable choice of the acceptance probabilities, the algorithm is shown to converge asymptotically, that is, the Markov chain that describes the algorithm converges with probability one to the Pareto optimal set.     

Approximation Methods in Multiobjective Programming

Approaches to approximate the efficient set and Pareto set of multiobjective programs are reviewed. Special attention is given to approximating structures, methods generating Pareto points, and approximation quality. The survey covers more than 50 articles published since 1975.His work was supported by Deutsche Forschungsgemeinschaft, Grant HA 1795/7-2.Her work was done while on a sabbatical leave at the University of Kaiserslautern with support of Deutsche Forschungsgemeinschaft, Grant Ka 477/24-1.     

PROMISE: A DSS for multiple objective stochastic linear programming problems

Most of the multiple objective linear programming (MOLP) methods which have been proposed in the last fifteen years suppose deterministic contexts, but because many real problems imply uncertainty, some methods have been recently developed to deal with MOLP problems in stochastic contexts. In order to help the decision maker (DM) who is placed before such stochastic MOLP problems, we have built a Decision Support System called PROMISE. On the one hand, our DSS enables the DM to identify many current stochastic contexts: risky situations and also situations of partial uncertainty. On the other hand, according to the nature of the uncertainty, our DSS enables the DM to choose the most appropriate interactive stochastic MOLP method among the available methods, if such a method exists, and to solve his problem via the chosen method.