Dominance and potential optimality in multiple criteria decision analysis with imprecise information

This paper discusses multiple criteria models of decision analysis with finite sets of alternatives. A weighted sum of criteria is used to evaluate the performance of alternatives. Information about the weights is assumed to be in the form of arbitrary linear constraints. Conditions for checking dominance and potential optimality of decision alternatives are presented. In the case of testing potential optimality, the proposed appoach leads to the consideration of a couple of mutually dual linear programming problems. The analysis of these problems gives valuable information for the decision maker. In particular, if a decision alternative is not potentially optimal, then a mixed alternative dominating it is defined by a solution to one of the LP problems. This statement generalizes similar results known for some special cases. The interpretation of the mixed alternative is discussed and compared to its analogue in a data envelopment analysis context.     

Characteristics of semi-convex frontier optimization

We study semi-convex frontier (SCF) optimization problems where objective functions can be semi-convex and constraint sets can be non-polyhedron, which stem from a growing range of optimization applications such as frontier analysis, multi-objective programming in economics. The new findings of this paper can be summarized as follows: (1) We characterize non-dominated points of a non-polyhedron optimal solution set of a semi-convex frontier program. (2) We obtain optimality conditions of a constant modulus SCF program, of which the objective function is semi-convex with a constant semiconvexity modulus. (3) We obtain a non-smooth Hölder stability of the optimal solutions of a semiconvex frontier program. (4) We use generalized differentiability to establish sensitivity analysis of the optimal value function of a semi-convex frontier program.     

A simulation-based test of stochastic multicriteria acceptability analysis using achievement functions

Stochastic multicriteria acceptability analysis using achievement functions (SMAA-A) is a preference model for discrete-choice decision making that inverts the traditional goal programming process by asking what combinations of aspirations are necessary to make each alternative the preferred one, rather than what alternative is preferred given a set of aspirations. In this paper, we test the ability of the model to discern good-performing alternatives from poorly-performing ones using a simulation study. Simulation results show that a suitably detailed construction of the acceptability index is particularly important, and that the resulting model can be fruitfully applied in the selection of a shortlist of alternatives from a larger set with only very limited decision maker involvement.     

Sensitivity analysis for choice problems with partial preference relations

In this paper we consider choice problems under the assumption that the preferences of the decision maker are expressed in the form of a parametric partial weak order without assuming the existence of any value function. We investigate both the sensitivity (stability) of each non-dominated solution with respect to the changes of parameters of this order, and the sensitivity of the set of non-dominated solutions as a whole to similar changes. We show that this type of sensitivity analysis can be performed by employing techniques of linear programming.     

A multi-objective mixed integer linear programming model for thesis defence scheduling

In this paper, we address the thesis defence scheduling problem, a critical academic scheduling management process, which has been overshadowed in the literature by its counterparts, course timetabling and exam scheduling. Specifically, we address the single defence assignment type of thesis defence scheduling problems, where each committee is assigned to a single defence, scheduled for a specific day, hour and room. We formulate a multi-objective mixed-integer linear programming model, which aims to be applicable to a broader set of cases than other single defence assignment models present in the literature, which have a focus on the characteristics of their universities. For such a purpose, we introduce a different decision variable, propose constraint formulations that are not regulation and policy specific, and cover and offer new takes on the more common objectives seen in the literature. We also include new objective functions based on our experience with the problem at our university and by applying knowledge from other academic scheduling problems. We also propose a two-stage solution approach. The first stage is employed to find the number of schedulable defences, enabling the optimisation of instances with unschedulable defences. The second stage is an implementation of the augmented $ϵ$-constraint method, which allows for the search of a set of different and non-dominated solutions while skipping redundant iterations. The methodology is tested for case-studies from our university, significantly outperforming the solutions found by human schedulers. A novel instance generator for thesis scheduling problems is presented. Its main benefit is the generation of the availability of committee members and rooms in availability and unavailability blocks, resembling their real-world counterparts. A set of 96 randomly generated instances of varying sizes is solved and analysed regarding their relative computational performance, the number of schedulable defences and the distribution of the considered types of iterations. The proposed method can find the optimal number of schedulable defences and present non-dominated solutions within the set time limits for every tested instance.     

Determining the Pareto set in a bicriteria two-echelon inventory/distribution system

This article concerns two-echelon inventory/distribution system, consisting of a warehouse and a retailer. We assume that the demand is deterministic and stockouts are not permitted. Two criteria are considered: to minimize the annual inventory cost and the annual total number of damaged items by improper shipment handling. The problem consists of determining the non-dominated inventory policies in such a way that the trade-off between both criteria is achieved. We present the characterization of the non-dominated optimal solution set and we use this result to correct the solution method previously proposed by other authors for a problem with identical cost structure. An efficient algorithm to calculate the non-dominated solution set is introduced. Computational results on several randomly generated problems are reported.     

Fuzzy Mathematical Programming: A Unified Approach Based On Fuzzy Relations

Fuzzy mathematical programming problems (FMP) form a subclass of decision - making problems where preferences between alternatives are described by means of objective function(s) defined on the set of alternatives. The formulation a FMP problem associated with the classical MP problem is presented. Then the concept of a feasible solution and optimal solution of FMP problem are defined. These concepts are based on generalized equality and inequality fuzzy relations. Among others we show that the class of all MP problems with (crisp) parameters can be naturally embedded into the class of FMP problems with fuzzy parameters. We also show that the feasible and optimal solutions being fuzzy sets are convex under some mild assumptions.     

The range of the efficient frontier in multiple objective linear programming

Because a rational decision maker should only select an efficient alternative in multiple criterion decision problems, the efficient frontier defined as the set of all efficient alternatives has become a central solution concept in multiple objective linear programming. Normally this set reduces the set of available alternatives of the underlying problem. There are several methods, mainly based on the simplex method, for computing the efficient frontier. This paper presents a quite different approach which uses a nonlinear parametric program, solved by Wolfe's algorithm, to determine the range of the efficient frontier.     

A global optimization algorithm for reliable network design

In this paper, we consider the problem of designing reliable networks that satisfy supply/demand, flow balance, and capacity constraints, while simultaneously allocating certain resources to mitigate the arc failure probabilities in such a manner as to minimize the total cost of network design and resource allocation. The resulting model formulation is a nonconvex mixed-integer 0-1 program, for which a tight linear programming relaxation is derived using RLT-based variable substitution strategies and a polyhedral outer-approximation technique. This LP relaxation is subsequently embedded within a specialized branch-and-bound procedure, and the proposed approach is proven to converge to a global optimum. Various alternative partitioning strategies that could potentially be employed in the context of this branch-and-bound framework, while preserving the theoretical convergence property, are also explored. Computational results are reported for a hypothetical scenario based on different parameter inputs and alternative branching strategies. Related optimization models that conform to the same class of problems are also briefly presented.     

How to determine basis stability in interval linear programming

Interval linear programming (ILP) was introduced in order to deal with linear programming problems with uncertainties that are modelled by ranges of admissible values. Basic tasks in ILP such as calculating the optimal value bounds or set of all possible solutions may be computationally very expensive. However, if some basis stability criterion holds true then the problems becomes much more easy to solve. In this paper, we propose a method for testing basis stability. Even though the method is exponential in the worst case (not surprisingly due to NP-hardness of the problem), it is fast in many cases.     

Approximation of convex bodies by multiple objective optimization and an application in reachable sets

In this paper, we focus on approximating convex compact bodies. For a convex body described as the feasible set in objective space of a multiple objective programme, we show that finding it is equivalent to finding the non-dominated set of a multiple objective programme. This equivalence implies that convex bodies can be approximated using multiple objective optimization algorithms. Therefore, we propose a revised outer approximation algorithm for convex multiple objective programming problems to approximate convex bodies. Finally, we apply the algorithm to solve reachable sets of control systems and use numerical examples to show the effectiveness of the algorithm.     

The application of optimal control methodology to nonlinear programming problems

Dynamic programming techniques have proven to be more successful than alternative nonlinear programming algorithms for solving many discrete-time optimal control problems. The reason for this is that, because of the stagewise decomposition which characterizes dynamic programming, the computational burden grows approximately linearly with the numbern of decision times, whereas the burden for other methods tends to grow faster (e.g.,n ³ for Newton's method). The idea motivating the present study is that the advantages of dynamic programming can be brought to bear on classical nonlinear programming problems if only they can somehow be rephrased as optimal control problems.As shown herein, it is indeed the case that many prominent problems in the nonlinear programming literature can be viewed as optimal control problems, and for these problems, modern dynamic programming methodology is competitive with respect to processing time. The mechanism behind this success is that such methodology achieves quadratic convergence without requiring solution of large systems of linear equations.     

Nonlinear Programming Analysis to Estimate Implicit Inventory Backorder Costs

In this paper, we use nonlinear programming to provide an alternative treatment of the economic order quantity problem with planned backorders. Many businesses, such as capital-goods firms that deal with expensive products and some service industries that cannot store their services, operate with substantial backlogs. In practical problems, it is usually very difficult to estimate accurately the values of the two types of backorder costs, i.e., the time-dependent unit backorder cost and the unit backorder cost. We redefine the original problem without including these backorder costs and construct a nonlinear programming problem with two service measure constraints which may be easier to specify than the backorder costs. We find that, with this different formulation of our new problem, we obtain results which give implicit estimates of the backorder costs. The alternative formulation provides an easier-to-use model and managerially meaningful results. Next, we show that, for a wide range of parameter values, it usually suffices to consider only one type of backorder cost, or equivalently, only one type of service measure constraint. Finally, we develop expressions which bracket the optimal values of the decision variables in a narrow range and provide a simple method for computing the optimal solution. In the most complicated case, this method requires finding the unique root of a polynomial.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

Evidential reasoning based preference programming for multiple attribute decision analysis under uncertainty

Multiple attribute decision analysis (MADA) problems having both quantitative and qualitative attributes under uncertainty can be modelled and analysed using the evidential reasoning (ER) approach. Several types of uncertainty such as ignorance and fuzziness can be consistently modelled in the ER framework. In this paper, both interval weight assignments and interval belief degrees are considered, which could be incurred in many decision situations such as group decision making. Based on the existing ER algorithm, several pairs of preference programming models are constructed to support global sensitivity analysis based on the interval values and to generate the upper and lower bounds of the combined belief degrees for distributed assessment and also the expected values for ranking of alternatives. A post-optimisation procedure is developed to identify non-dominated solutions, examine the robustness of the partial ranking orders generated, and provide guidance for the elicitation of additional information for generating more desirable assessment results. A car evaluation problem is examined to show the implementation process of the proposed approach.     

Pruned Pareto-optimal sets for the system redundancy allocation problem based on multiple prioritized objectives

In this paper, a new methodology is presented to solve different versions of multi-objective system redundancy allocation problems with prioritized objectives. Multi-objective problems are often solved by modifying them into equivalent single objective problems using pre-defined weights or utility functions. Then, a multi-objective problem is solved similar to a single objective problem returning a single solution. These methods can be problematic because assigning appropriate numerical values (i.e., weights) to an objective function can be challenging for many practitioners. On the other hand, methods such as genetic algorithms and tabu search often yield numerous non-dominated Pareto optimal solutions, which makes the selection of one single best solution very difficult. In this research, a tabu search meta-heuristic approach is used to initially find the entire Pareto-optimal front, and then, Monte-Carlo simulation provides a decision maker with a pruned and prioritized set of Pareto-optimal solutions based on user-defined objective function preferences. The purpose of this study is to create a bridge between Pareto optimality and single solution approaches.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

A Hybrid Meta-Heuristic for Multi-Objective Optimization: MOSATS

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of solutions, called the Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, the majority of problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. This paper presents a novel approach based on hybridizing Simulated Annealing and Tabu Search. Experiments on the Graph Partitioning Problem show that this new method is a better tool for approximating the efficient set than other strategies also based on these meta-heuristics.