An interactive method of tackling uncertainty in interval multiple objective linear programming

Mathematical programming models for decision support must explicitly take account of the treatment of the uncertainty associated with the model coefficients along with multiple and conflicting objective functions. Interval programming just assumes that information about the variation range of some (or all) of the coefficients is available. In this paper, we propose an interactive approach for multiple objective linear programming problems with interval coefficients that deals with the uncertainty in all the coefficients of the model. The presented procedures provide a global view of the solutions in the best and worst case coefficient scenarios and allow performing the search for new solutions according to the achievement rates of the objective functions regarding both the upper and lower bounds. The main goal is to find solutions associated with the interval objective function values that are closer to their corresponding interval ideal solutions. It is also possible to find solutions with non-dominance relations regarding the achievement rates of the upper and lower bounds of the objective functions considering interval coefficients in the whole model.     

Interactive TOPSIS algorithms for solving multi-level non-linear multi-objective decision-making problems

This paper extended the concept of the technique for order preference by similarity to ideal solution (TOPSIS) to develop a methodology for solving multi-level non-linear multi-objective decision-making (MLN-MODM) problems of maximization-type. Also, two new interactive algorithms are presented for the proposed TOPSIS approach for solving these types of mathematical programming problems. The first proposed interactive TOPSIS algorithm includes the membership functions of the decision variables for each level except the lower level of the multi-level problem. These satisfactory decisions are evaluated separately by solving the corresponding single-level MODM problems. The second proposed interactive TOPSIS algorithm lexicographically solves the MODM problems of the MLN-MOLP problem by taking into consideration the decisions of the MODM problems for the upper levels. To demonstrate the proposed algorithms, a numerical example is solved and compared the solutions of proposed algorithms with the solution of the interactive algorithm of Osman et al. (2003) [4]. Also, an example of an application is presented to clarify the applicability of the proposed TOPSIS algorithms in solving real world multi-level multi-objective decision-making problems.     

Network reoptimization procedures for multiobjective network probelems

Network models are attractive because of their computational efficiency. Network applications can involve multiple objective analysis. Multiple objective analysis requires generating nondominated solutions in various forms. Two general methods exist to generate new solutions in continuous optimization: changing objective function weights and inserting objective bounds through constraints. In network flow problems, modifying weights is straightforward, allowing use of efficient network codes. Use of bounds on objective attainment levels can provide a more controlled generation of solutions reflecting tradeoffs among objectives. To constrain objective attainment, however, would require a side constrained network code, sacrificing some computational efficiency for greater model flexibility. We develop reoptimization procedures for the side constrained problem and use them in conjunction with simplex-based techniques. Our approach provides a useful tool for generating solutions allowing greater decision maker control over objective attainments, allowing multiobjective analysis of large-scale problems. Results are compared with solutions obtained from the computationally more attractive weighting technique. Reoptimization procedures are discussed as a means of more efficiently conducting multiple objective network analyses.     

Bounding MOLP objective functions: effect on efficient set size

In multiple objective linear programming (MOLP) problems the extraction of all the efficient extreme points becomes problematic as the size of the problem increases. One of the suggested actions, in order to keep the size of the efficient set to manageable limits, is the use of bounds on the values of the objective functions by the decision maker. The unacceptable efficient solutions are screened out from further investigation and the size of the efficient set is reduced. Although the bounding of the objective functions is widely used in practice, the effect of this action on the size of the efficient set has not been investigated. In this paper, we study the effect of individual and simultaneous bounding of the objective functions on the number of the generated efficient points. In order to estimate the underlying relationships, a computational experiment is designed, in which randomly generated multiple objective linear programming problems of various sizes are systematically examined.     

IMOST: Interactive Multiple Objective System Technique

An interactive multiple objective system technique (IMOST) is investigated to improve the flexibility and robustness of multiple objective decision making (MODM) methodologies. The interactive concept provides a learning process about the system, whereby the decision maker can learn to recognize good solutions, the relative importance of factors in the system, and then design a high-productivity and zero-buffer system instead of optimizing a given system. This interactive technique provides integration-oriented, adaptation and dynamic learning features by considering all possibilities of a specific domain of MODM problems which are integrated in logical order. It encompasses the decision-making processes of formulating problems, constructing a model, solving the model, testing/examining its solution, and improving/reshaping the model and its solution in a specific problem domain. Although IMOST deals with multiple objective programming problems, it also provides some valuable orientation of integrated system methodologies.     

Linear bilevel programs with multiple objectives at the upper level

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. Focus of the paper is on general bilevel optimization problems with multiple objectives at the upper level of decision making. When all objective functions are linear and constraints at both levels define polyhedra, it is proved that the set of efficient solutions is non-empty. Taking into account the properties of the feasible region of the bilevel problem, some methods of computing efficient solutions are given based on both weighted sum scalarization and scalarization techniques. All the methods result in solving linear bilevel problems with a single objective function at each level.     

Weighting method for bi-level linear fractional programming problems

In this paper we consider the solution of a bi-level linear fractional programming problem (BLLFPP) by weighting method. A non-dominated solution set is obtained by this method. In this article decision makers (DMs) provide their preference bounds to the decision variables that is the upper and lower bounds to the decision variables they control. We convert the hierarchical system into scalar optimization problem (SOP) by finding proper weights using the analytic hierarchy process (AHP) so that objective functions of both levels can be combined into one objective function. Here the relative weights represent the relative importance of the objective functions.     

On Efficient Solutions with Trade-Offs Bounded by Given Values

In this article, efficient solutions of multiple objective optimization problems with trade-offs, bounded by prespecified lower and upper bounds, are investigated. It is shown that one of the existing techniques to obtain these solutions does not work correctly. Furthermore, a new approach is given to approximate the set of such solutions. In addition to theoretical discussions, some clarifying examples are given.     

Global multi-parametric optimal value bounds and solution estimates for separable parametric programs

In this tutorial, a strategy is described for calculating parametric piecewise-linear optimal value bounds for nonconvex separable programs containing several parameters restricted to a specified convex set. The methodology is based on first fixing the value of the parameters, then constructing sequences of underestimating and overestimating convex programs whose optimal values respectively increase or decrease to the global optimal value of the original problem. Existing procedures are used for calculating parametric lower bounds on the optimal value of each underestimating problem and parametric upper bounds on the optimal value of each overestimating problem in the sequence, over the given set of parameters. Appropriate updating of the bounds leads to a nondecreasing sequence of lower bounds and a nonincreasing sequence of upper bounds, on the optimal value of the original problem, continuing until the bounds satisfy a specified tolerance at the value of the parameter that was fixed at the outset. If the bounds are also sufficiently tight over the entire set of parameters, according to criteria specified by the user, then the calculation is complete. Otherwise, another parameter value is selected and the procedure is repeated, until the specified criteria are satisfied over the entire set of parameters. A parametric piecewise-linear solution vector approximation is also obtained. Results are expected in the theory, computations, and practical applications. The general idea of developing results for general problems that are limits of results that hold for a sequence of well-behaved (e.g., convex) problems should be quite fruitful.     

Error analysis for convex separable programs: Bounds on optimal and dual optimal solutions

Computable lower and upper bounds on the optimal and dual optimal solutions of a nonlinear, convex separable program are obtained from its piecewise linear approximation. They provide traditional error and sensitivity measures and are shown to be attainable for some problems. In addition, the bounds on the solution can be used to develop an efficient solution approach for such programs, and the dual bounds enable us to determine a subdivision interval which insures the objective function accuracy of a prespecified level. A generalization of the bounds to certain separable, but nonconvex, programs is given and some numerical examples are included.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

Bounds on the value of information in uncertain decision problems II†

In most stochastic decision problems one has the opportunity to collect information that would partially or totally eliminate the inherent uncertainty. One wishes to compare the cost and value of such information in terms of the decision maker's preferences to determine an optimal information gathering plan. The calculation of the value of information generally involves oneor more stochastic recourse problems as well as one or more expected value distribution problems. The difficulty and costs of obtaining solutions to these problems has led to a focus on the development of upper and lower bounds on the various subproblems that yield bounds on the value of information. In this paper we discuss published and new bounds for static problems with linear and concave preference functions for partial and perfect information. We also provide numerical examples utilizing simple production and investment problems that illustrate the calculations involved in the computation of the various bounds and provide a setting for a comparison of the bounds that yields some tentative guidelines for their use. The bounds compared are the Jensen's Inequality bound,the Conditional Jensen's Inequality bound and the Generalized Jensen and Edmundson-Madansky bounds.     

Integrating heuristic information into exact methods: The case of the vertex p-centre problem

We solve the vertex p-centre problem optimally using an exact method that considers both upper and lower bounds as part of its search engine. Tight upper bounds are generated quickly via an efficient three-level heuristic, which are then used to derive potential ‘lower bounds’ accordingly. These two pieces of information when used together make our chosen exact method more efficient at obtaining optimal solutions relatively quickly. The proposed implementation produced excellent results when tested on the OR Library data set. This integrated approach can be adopted for those exact methods that consider both upper and lower bounds within their search engine and hence provide a wider spectrum of applicability in other hard combinatorial problems.     

Optimizing a linear function over an integer efficient set

In this paper, a method for optimizing a linear function over the integer Pareto-optimal set without having to determine all integer efficient solutions is presented. The proposed algorithm is based on a simple selection technique that improves the linear objective value at each iteration. Two types of cuts are performed successively until the optimal value is obtained and the current truncated region contains no integer feasible solution.     

An ideal column algorithm for integer programs with special ordered sets of variables

One of the most frequently occurring integer programming structures is the one which has special ordered sets of variables included in multiple choice constraints. For problems with this structure a set of ideal columns are defined from the linear programming relaxation of the integer program and a reduced integer program is formed by keeping only those columns within a specified distance from the ideal column. Conditions are established which guarantee when the optimal solution to the reduced problem is als optimal for the original problem. When these conditions are not satisfied, bounds on the optimal solution value are provided. Ideal columns are also used to establish weights for the special ordered set variables. This procedure has been implemented through a control program written by the authors for MPSX/370-MIP/370. Computational results are given.     

Interactive Sequential Goal Programming

This paper introduces a new solution method based on Goal Programming for Multiple Objective Decision Making (MODM) problems. The method, called Interactive Sequential Goal Programming (ISGP), combines and extends the attractive features of both Goal Programming and interactive solution approaches for MODM problems. ISGP is applicable to both linear and non-linear problems. It uses existing single objective optimization techniques and, hence, available computer codes utilizing these techniques can be adapted for use in ISGP. The non-dominance of the "best-compromise" solution is assured. The information required from the decision maker in each iteration is simple. The proposed method is illustrated by solving a nutrition problem.     

基于TOPSIS的模糊群体多属性决策方法

针对模糊群体多属性决策问题,给出一种基于理想点法(TOPSIS)的多属性决策方法.方法先用三角模糊数的形式表示专家评价值的模糊性和不确定性,而后考虑了专家在不同评价属性中的重要程度和意见的相似度,并将专家意见进行集结得到专家群体关于方案集的模糊决策矩阵,最后定义了三角模糊数形式的正负理想方案,通过计算各方案与正负理想方案的距离以及各方案与理想点的相对接近度,最终确定最优方案.通过实例分析说明了该方法的可行性和有效性.     

Optimization over the efficient set using an active constraint approach

In this work the problem of maximizing a nonlinear objective over the set of efficient solutions of a multicriteria linear program is considered. This is a nonlinear program with nonconvex constraints. The approach is to develop an active constraint algorithm which utilizes the fact that the efficient structure in decision space can be associated in a natural way with hyperplanes in the space of objective values. Examples and numerical experience are included.     

Interactive Polyhedral Outer Approximation (IPOA) strategy for general multiobjective optimization problems

We propose an interactive polyhedral outer approximation (IPOA) method to solve a broad class of multiobjective optimization problems (MOP) with, possibly, nonlinear and nondifferentiable objective and constraint functions, and with continuous or discrete decision variables. During the interactive optimization phase, the method progressively constructs a polyhedral approximation of the decision-maker’s (DM’s) unknown preference structure and a polyhedral outer-approximation of the feasible set of MOP. The piecewise linear approximation of the DM’s preferences also provides a mechanism for testing the consistency of the DM’s assessments and removing inconsistencies; it also allows post-optimality analysis. All the feasible trial solutions are non-dominated (efficient, or Pareto-optimal) so preference assessments are made in the context of non-dominated alternatives only. Upper and lower bounds on the yet unknown optimal value are produced at every iteration, allowing terminating the search prematurely at a good-enough solution and providing information about the closeness of this solution to the optimal solution. The IPOA method includes a preliminary phase in which a limited probe of the efficient set is conducted in order to find a good initial trial solution for the interactive phase. The computational requirements of the algorithm are relatively simple. The results of an extensive computational study are reported.     

Nonsmooth exclusion test for finding all solutions of nonlinear equations

A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex problem is established which motivates a method to generate automatically, starting points for a local Newton-type method. A damped-Newton method with natural level functions employing the restrictive monotonicity test is employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented, and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation.