A weight space-based approach to fuzzy multiple-objective linear programming

In this paper, the effects of uncertainty on multiple-objective linear programming models are studied using the concepts of fuzzy set theory. The proposed interactive decision support system is based on the interactive exploration of the weight space. The comparative analysis of indifference regions on the various weight spaces (which vary according to intervals of values of the satisfaction degree of objective functions and constraints) enables to study the stability and evolution of the basis that correspond to the calculated efficient solutions with changes of some model parameters.     

A solution method for the linear static Stackelberg problem usingpenalty functions

A new solution technique is presented for the linear constrained static Stackelberg problem. For a given value of x, the leader's decision vector, the follower is at its rational reaction set when the duality gap of the second-level problem becomes zero. The outer problem is solved by appending to the leader's objective, a function that minimizes the duality gap of the follower's problem. This structure leads to the decomposition of the composite problem into a series of linear programs leading to an efficient algorithm. It is proved that optimality is reached for an exact penalty function, and the method is illustrated with some examples     

An interval programming approach for the bilevel linear programming problem under fuzzy random environments

In this paper, we address a class of bilevel linear programming problems with fuzzy random variable coefficients in objective functions. To deal with such problems, we apply an interval programming approach based on the $\alpha $ -level set to construct a pair of bilevel mathematical programming models called the best and worst optimal models. Through expectation optimization model, the best and worst optimal problems are transformed into the deterministic problems. By means of the Kth best algorithm, we obtain the best and worst optimal solutions as well as the corresponding range of the objective function values. In this way, more information can be provided to the decision makers under fuzzy random circumstances. Finally, experiments on two examples are carried out, and the comparisons with two existing approaches are made. The results indicate the proposed approaches can get not only the best optimal solution (ideal solution) but also the worst optimal solution, and is more reasonable than the existing approaches which can only get a single solution (ideal solution).     

An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem

In this paper, an improved two-stage simulated annealing algorithm is presented for the minimum linear arrangement problem for graphs. This algorithm integrates several distinguished features including an efficient heuristic to generate good quality initial solutions, a highly discriminating evaluation function, a special neighborhood function and an effective cooling schedule. The algorithm is evaluated on a set of 30 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of 17 previous best results.     

Determining the optimal decision delay parameter for a linear equalizer

1 Introduction Equalization techniques play an ever-increasing role in combating distortion and interference in mod- ern communication links[1,2]. It is well-known that the choice of equalizer decision delay parameter crit- ically determines achievable bit error rate (BER) performance[3,4]. We present a simple and e?ective method for determining an optimal decision delay pa- rameter that results in the best bit error rate perfor- mance for a linear equalizer. The proposed technique computes …     

On a type of stability of a multicriteria integer linear programming problem in the case of a monotone norm

A multicriteria integer linear programming problem with a finite number of admissible solutions is considered. The problem consists in finding the Pareto set. Lower and upper attainable estimates of the radius of strong stability of the problem are obtained in the case when the norm in the space of solutions is arbitrary, and the norm in the criteria space is monotone. Using the Minkowski-Mahler inequality, a formula for calculating this radius is derived in the case when the Pareto set consists of a single solution. Estimates of the radius are also found in the case of the Hölder norm in the specified spaces. A class of problems is distinguished for which the radius of strong stability is infinite. As corollaries, certain results known earlier are derived. Illustrative numerical examples are also presented.     

A population-based algorithm for solving linear assignment problems with two objectives

The paper presents a population-based algorithm for computing approximations of the efficient solution set for the linear assignment problem with two objectives. This is a multiobjective metaheuristic based on the intensive use of three operators – a local search, a crossover and a path-relinking – performed on a population composed only of elite solutions. The initial population is a set of feasible solutions, where each solution is one optimal assignment for an appropriate weighted sum of two objectives. Genetic information is derived from the elite solutions, providing a useful genetic heritage to be exploited by crossover operators. An upper bound set, defined in the objective space, provides one acceptable limit for performing a local search. Results reported using referenced data sets have shown that the heuristic is able to quickly find a very good approximation of the efficient frontier, even in situation of heterogeneity of objective functions. In addition, this heuristic has two main advantages. It is based on simple easy-to-implement principles, and it does not need a parameter tuning phase.     

大型群体多属性决策的目标函数线性回归法

在定义标准决策值的基础上,运用线性回归的方法建立了带有约束条件的大型群体多属性决策目标函数线性回归模型,证明了该模型解的存在性和唯一性.大型群体多属性决策目标函数线性回归法对各专家的标准决策值的信息进行了最优意义上的集结和协调.此外,对大型群体多属性决策目标函数线性回归模型进行了讨论,并获得了一整套可用Matlab软件求解该模型最优解的算法,具体应用算例验证了所提算法的有效性.     

Stability radius of a vector integer linear programming problem: case of a regular norm in the space of criteria

A multicriteria integer linear programming problem of finding a Pareto set is considered. The set of feasible solutions is supposed to be finite. The lower and upper achievable bounds for the radius of stability are obtained using a stability criterion and the Minkowski–Mahler inequality and assuming that the norm is arbitrary in the space of solutions and is monotone in the space of criteria. Bounds for the radius of stability in spaces with the Holder metric are given in corollaries.     

Dual contingency plans in optimal generalized linear designs

Traditional optimal linear design problems are formulated by linear programming with a single criterion (objective)and a single resource availability (right-hand side) level. This approach is to seek an optimal solution for a given design system. However, it fails to deal with optimal linear design problems with multi-criteria and multi-source availability levels. In this paper, we first sketch how to use the multi-criteria and multi-constraint levels (MC²) linear programming to formulate the optimal linear design problems and to find a set of potentially good designs (PGDs). Then we generate generalized good designs (GGDs) from given PGDs and show how to construct their related dual contingency plans under various decision situations, fn contrast to the known concept of PGDs, the GGDs go beyond the limitations of the design opportunities. In constructing the dual contingency plans for a given GGD, we adjust the unit contribution of selected design opportunities in the GGD to convert non-optimal solutions into optimal solutions. Based on theoretical results, an algorithm of effectively and systematically locating the optimal generalized designs and the corresponding optimal dual contingency plans under various decision situations is provided.     

On a construction of a hierarchy of best linear spline approximations using a finite element approach

We present a method for the hierarchical approximation of functions in one, two, or three variables based on the finite element method (Ritz approximation). Starting with a set of data sites with associated function, we first determine a smooth (scattered-data) interpolant. Next, we construct an initial triangulation by triangulating the region bounded by the minimal subset of data sites defining the convex hull of all sites. We insert only original data sites, thus reducing storage requirements. For each triangulation, we solve a minimization problem: computing the best linear spline approximation of the interpolant of all data, based on a functional involving function values and first derivatives. The error of a best linear spline approximation is computed in a Sobolev-like norm, leading to element-specific error values. We use these interval/triangle/tetrahedron-specific values to identify the element to subdivide next. The subdivision of an element with largest error value requires the recomputation of all spline coefficients due to the global nature of the problem. We improve efficiency by 1) subdividing multiple elements simultaneously and 2) by using a sparse-matrix representation and system solver.     

Extremist vs. centrist decision behavior: quasi-convex utility functions for interactive multi-objective linear programming problems

This paper presents the fundamental theory and algorithms for identifying the most preferred alternative for a decision maker (DM) having a non-centrist (or extremist) preferential behavior. The DM is requested to respond to a set of questions in the form of paired comparison of alternatives. The approach is different than other methods that consider the centrist preferential behavior.In this paper, an interactive approach is presented to solve the multiple objective linear programming (MOLP) problem. The DM's underlying preferential function is represented by a quasi-convex value (utility) function, which is to be maximized. The method presented in this paper solves MOLP problems with quasi-convex value (utility) functions by using paired comparison of alternatives in the objective space. From the mathematical point of view, maximizing a quasi-convex (or a convex) function over a convex set is considered a difficult problem to solve, while solutions for quasi-concave (or concave) functions are currently available. We prove that our proposed approach converges to the most preferred alternative.We demonstrate that the most preferred alternative is an extreme point of the MOLP problem, and we develop an interactive method that guarantees obtaining the global most preferred alternative for the MOLP problem. This method requires only a finite number of pivoting operations using a simplex-based method, and it asks only a limited number of paired comparison questions of alternatives in the objective space. We develop a branch and bound algorithm that extends a tree of solutions at each iteration until the MOLP problem is solved. At each iteration, the decision maker has to identify the most preferred alternatives from a given subset of efficient alternatives that are adjacent extreme points to the current basis. Through the branch and bound algorithm, without asking many questions from the decision maker, all branches of the tree are implicitly enumerated until the most preferred alternative is obtained. An example is provided to show the details of the algorithm. Some computational experiments are also presented.Scope and purposeThis paper presents the fundamental theory, algorithm, and examples for identifying the most preferred alternative (solution) for a decision maker (DM) having a non-centrist (or extremist) preferential behavior for Multiple Objective Linear Programming (MOLP) problems. The DM is requested to respond to a set of questions in the form of paired comparison of alternatives.Although widely applied, Linear Programming is limited to a single objective function. In many real world situations, DMs are faced with multiple objective problems in that several competing and conflicting objectives have to be considered. For these problems, there exist many alternatives that are feasible and acceptable. However, the DM is interested in finding “the most preferred alternative”. In the past three decades, many methods have been developed for solving MOLP problems.One class of these methods is called “interactive”, in which the DM responds to a set of questions interactively so that his/her most preferred alternative can be obtained. In most of these methods, the value (utility) function (that presents the DM's preference) is assumed to be linear or additive, concave, pseudo-concave, or quasi-concave. However, for MOLP problems, there has not been any effort to recognize and solve the quasi-convex utility functions, which are among the most difficult class of problems to solve. The quasi-convex class of utility functions represents an extremist preferential behavior, while the other aforementioned methods (such as quasi-concave) represent a conservative behavioral preference. It is shown that the method converges to the optimal (the most preferred) alternative. The approach is computationally feasible for moderately sized problems.     

PROJECT Method for Multiobjective Optimization Based on Gradient Projection and Reference Points

In this paper, we propose a new interactive method for multiobjective programming (MOP) called the PROJECT method. Interactive methods in MOP are techniques that can help the decision maker (DM) to generate the most preferred solution from a set of efficient solutions. An interactive method should be capable of capturing the preferences of the DM in a pragmatic and comprehensive way. In certain decision situations, it may be easier and more reliable for DMs to follow an interactive process for providing local tradeoffs than other kinds of preferential information like aspiration levels, objective function classification, etc. The proposed PROJECT method belongs to the class of interactive local tradeoff methods. It is based on the projection of utility function gradients onto the tangent hyperplane of an efficient set and on a new local search procedure that inherits the advantages of the reference-point method to search for the best compromise solution within a local region. Most of the interactive methods based on local tradeoffs assume convexity conditions in a MOP problem, which is too restrictive in many real-life applications. The use of a reference-point procedure makes it possible to generate any efficient solutions, even the nonsupported solutions or efficient solutions located in the nonconvex part of the efficient frontier of a nonconvex MOP problem. The convergence of the proposed method is investigated. A nonlinear example is examined using the new method, as well as a case study on efficiency analysis with value judgements. The proposed PROJECT method is coded in Microsoft Visual C++ and incorporated into the software PROMOIN (Interactive MOP).     

A new approach on designing l1 optimal regulator with minimum order for SISO linear systems

For a SISO linear discrete-time system with a specified input signal, a novel method to realize optimal l1 regulation control is presented. Utilizing the technique of converting a polynomial equation to its corresponding matrix equation, a linear programming problem to get an optimal l1 norm of the system output error map is developed which includes the first term and the last term of the map sequence in the objective function and the right vector of its constraint matrix equation, respectively. The adjustability for the width of the constraint matrix makes the trade-off between the order of the optimal regulator and the value of the minimum objective norm become possible, especially for achieving the optimal regulator with minimum order. By norm scaling rules for the constraint matrix equation, the optimal solution can be scaled directly or be obtained by solving a linear programming problem with l\ norm objective.     

A new approach on designing l_1 optimal regulator with minimum order for SISO linear systems

For a SISO linear discrete-time system with a specified input signal, a novel method to realize optimal l1 regulation control is presented. Utilizing the technique of converting a polynomial equation to its corresponding matrix equation, a linear programming problem to get an optimal l1 norm of the system output error map is developed which includes the first term and the last term of the map sequence in the objective function and the right vector of its constraint matrix equation, respectively. The adjustability for the width of the constraint matrix makes the trade-off between the order of the optimal regulator and the value of the minimum objective norm become possible, especially for achieving the optimal regulator with minimum order. By norm scaling rules for the constraint matrix equation, the optimal solution can be scaled directly or be obtained by solving a linear programming problem with l\ norm objective.     

An economical cognitive approach for bi-objective optimization using bliss points, visualization, and interaction

When an optimization problem encompasses multiple objectives, it is usually difficult to define a single optimal solution. The decision maker plays an important role when choosing the final single decision. Pareto-based evolutionary multiobjective optimization (EMO) methods are very informative for the decision making process since they provide the decision maker with a set of efficient solutions to choose from. Despite that the set of efficient solutions may not be the global efficient set, we show in this paper that the set can still be informative when used in an interactive session with the decision maker. We use a combination of EMO and single objective optimization methods to guide the decision maker in interactive sessions.     

The determination of a subset of efficient solutions via goal programming

A wide variety of models and methods have been proposed to solve the vectormaximum problem. Many of these approaches center their attention on linear programming with several objective functions and seek to obtain the set of efficient (Pareto optimal) solutions. Another approach to the same problem is to rank the objectives according to a priority structure and seek the lexicographic minimum of an ordered function of goal deviations. This latter approach, known as goal programming with preemptive priorities, has, in the literature, usually been treated as a separate topic. In this paper we show that the solution to the linear goal programming problem can be made to always be an efficient solution from which we may conduct a practical investigation of a subset of efficient solutions which form a useful compromise set. While perhaps lacking the elegance of the more esoteric approaches, this technique nonetheless has worked well in practice on actual problems.     

Objective function bounds for the inexact linear programming problem with generalized cost coefficients

This paper addresses the inexact linear programming problem in which the objective function coefficients are not fixed but lie in some predetermined set, C. Under certain convexity assumptions, standard mathematical programming techniques are employed to determine worst case and best case solutions. Simulation is then used to explore the properties of the general problem: max (cx: Ax ≦ b) for some c ? C. A wide range of configurations is examined and it is statistically demonstrated that the variance of objective function values is proportional to the size and shape of C. A number of examples are given to highlight the results.     

Linear programming with interval right hand sides

In this paper, we study general linear programs in which right hand sides are interval numbers. This model is relevant when uncertain and inaccurate factors make difficult the assignment of a single value to each right hand side. When objective function coefficients are interval numbers in a linear program, classical criteria coming from decision theory (like the worst case criterion) are usually applied to determine robust solutions. When the set of feasible solutions is uncertain, we identify a class of linear programs for which these classical approaches are no longer relevant. However, it is possible to compute the worst optimum solution. We study the complexity of this optimization problem when each right hand side is an interval number. Then, we exhibit some duality relationships between the worst optimum solution problem and the best optimum solution to the dual problem.     

OOESAlgorithm.jl: a julia package for optimizing a linear function over the set of efficient solutions for biobjective mixed integer linear programming

We present OOESAlgorithm.jl , a package for optimizing a linear function over the efficient set of biobjective mixed integer linear programs. The proposed package extends our recent study (see Sierra‐Altamiranda and Charkhgard [INFORMS Journal on Computing, https://doi.org/10.1287/ijoc.2018.0851]) by adding two main features: (a) in addition to CPLEX, the package allows employing any single‐objective solver supported by MathProgBase.jl , for example, GLPK, CPLEX, and SCIP; (b) the package supports execution on multiple processors and is compatible with the JuMP modeling language. An extensive computational study shows the efficacy of the package and its features.