A reference direction approach to multiple objective quadratic-linear programming

In this paper, we propose an interactive procedure for solving multiple criteria problems with one quadratic objective, several linear objectives, and a set of linear constraints. The procedure is based on the use of reference directions and weighted sums. Reference directions for the linear functions, and weighted sums for combining the quadratic function with the linear ones are used as parameters to implement the free search of nondominated solutions. The idea leads to the parametric linear complementarity problem formulation. An approach to deal with this type of problems is given as well. The approach is illustrated with a numerical example.     

A visual interactive method for solving the multiple criteria problem

This paper proposes a new method for solving multiple criteria mathematical programming problems. The method does not rely on explicit knowledge of the properties of the utility function. However, if the utility function is assumed to be pseudoconcave and differentiable when the procedure terminates, sufficient conditions for optimality can be established.The method has some features in common with the well-known GDF method of Geoffrion, Dyer and Feinberg (1972). However, our method operates solely in terms of efficient solutions contrary to the GDF method. Moreover, the original procedure of the GDF method for solving the direction-finding problem has been abandoned, since it has turned out that it is not very workable in practice. Instead, the idea of using reference goals or aspiration levels, originated by Wierzbicki, is utilized for determining a direction of improvement. The step-size problem is dealt with in a manner analogous to the GDF method. Computer graphics are used as an aid in solving the step-size problem.The method is easy to implement and convenient to use. Any standard LP package with a parametric optimization routine can be used. In addition, a graphical display device is required.     

A bound-improving approach to discrete programming problems

This note deals with the extension of the bound-improving sequence idea to general discrete programming problems.Corresponding author.     

A new approach to discrete stochastic optimization problems

Solving a discrete stochastic optimization problem involves two efforts: one is to sample and search the design space; and the other is to estimate the performance values of the sampled designs. When the amount of computational resources is limited, we need to know how to balance these two efforts in order to obtain the best result. In this paper, two performance measures which quantify the marginal contribution of the searching process as well as the performance evaluation process are proposed. Using these two measures, we recommend a framework that can dynamically allocate the computational resources to the search process and the performance evaluation process. Two algorithms based on the proposed framework are tested on several scenarios, and the results produced are very promising.     

Decision-aid for discrete multiple criteria decision making problems with imprecise data

We describe ways of aiding decision making with a discrete set of alternatives. In many decision situations, it is not possible to obtain explicit preference information from the decision makers. Instead, useful decision-aid can be provided to the decision makers by describing what kind of weighting of the criteria result in certain choices of the alternatives. The suggested treatment is based on the basic ideas of the ELECTRE III method. The modelling of the preferences by pseudo-criteria is especially helpful in case the data, that is, the criterion values are imprecise. Unlike ELECTRE III, no ranking of the alternatives is produced. Based on a minimum-procedure in the exploitation of the outranking relations, we provide information about the weights of the criteria that make a certain alternative the best. We also present an interactive searching procedure in the weighting space. The auxiliary optimization problems to be solved are nondifferentiable. Cases with both single and multiple decision makers are considered.     

A multiple criteria approach to data envelopment analysis

In this paper, we present a Multiple Criteria Data Envelopment Analysis (MCDEA) model which can be used to improve discriminating power of DEA methods and also effectively yield more reasonable input and output weights without a priori information about the weights. In the proposed model, several different efficiency measures, including classical DEA efficiency, are defined under the same constraints. Each measure serves as a criterion to be optimized. Efficiencies are then evaluated under the framework of multiple objective linear programming (MOLP). The method is illustrated through three examples in which data sets are taken from previous research on DEA's discriminating power and weight restriction.     

Regular-SAT: A many-valued approach to solving combinatorial problems

Regular-SAT is a constraint programming language between CSP and SAT that—by combining many of the good properties of each paradigm—offers a good compromise between performance and expressive power. Its similarity to SAT allows us to define a uniform encoding formalism, to extend existing SAT algorithms to Regular-SAT without incurring excessive overhead in terms of computational cost, and to identify phase transition phenomena in randomly generated instances. On the other hand, Regular-SAT inherits from CSP more compact and natural encodings that maintain more the structure of the original problem. Our experimental results—using a range of benchmark problems—provide evidence that Regular-SAT offers practical computational advantages for solving combinatorial problems.     

A visual interactive approach for multiple criteria decision making with monotone utility functions

We consider the problem of choosing the best of a set of alternatives where each alternative is evaluated on multiple criteria. We develop a visual interactive approach assuming that the decision maker (DM) has a general monotone utility function. The approach partitions the criteria space into nonoverlapping cells. The DM uses various graphical aids to move between cells and to further manipulate selected cells with the goal of creating cells that have ideal points less preferred than an alternative. When the DM identifies such cells, all alternatives in those cells are eliminated from further consideration. The DM may also compare pairs of alternatives. The approach terminates with the most preferred alternative of the DM.     

Guaranteeing approach to solving quantile optimization problems

This paper presents a numerical method for solving quantile optimization problems, i.e. stochastic programming problems in which the quantile of the distribution of an objective function is the criterion to be optimized.     

An approach to solving multiparameter algebraic problems

An approach to solving the following multiparameter algebraic problems is suggested: (1) spectral problems for singular matrices polynomially dependent on q≥2 spectral parameters, namely: the separation of the regular and singular parts of the spectrum, the computation of the discrete spectrum, and the construction of a basis that is free of a finite regular spectrum of the null-space of polynomial solutions of a multiparameter polynomial matrix; (2) the execution of certain operations over scalar and matrix multiparameter polynomials, including the computation of the GCD of a sequence of polynomials, the division of polynomials by their common divisor, and the computation of relative factorizations of polynomials; (3) the solution of systems of linear algebraic equations with multiparameter polynomial matrices and the construction of inverse and pseudoinverse matrices. This approach is based on the so-called ΔW-q factorizations of polynomial q-parameter matrices and extends the method for solving problems for one- and two-parameter polynomial matrices considered in [1–3] to an arbitrary q≥2. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 191–246. Translated by V. N. Kublanovskaya.     

A critical review of discrete filled function methods in solving nonlinear discrete optimization problems

Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison.     

InterQuad: An interactive quad tree based procedure for solving the discrete alternative multiple criteria problem

In this paper an interactive procedure based upon a data structure called a quad tree is developed for solving the discrete alternative multiple criteria problem. Called InterQuad, the procedure has been designed with large discrete alternative problems in mind. InterQuad takes advantage of the ability of a quad tree to identify, store, and retrieve nondominated criterion vectors. Then, the user interacts with the nondominated criterion vectors stored in the quad tree in a fashion similar to that of the Combined Tchebycheff/Aspiration Criterion Vector Procedure of Steuer, Silverman and Whisman.     

An extreme-distance approach to multiple criteria ranking

A distance approach based on extreme points, or predefined ideal and anti-ideal points, is proposed to improve on the TOPSIS (Technique for Order Performance [or Ordered Preference] by Similarity to Ideal Solution) method of multiple criteria ranking. Two case studies demonstrate how the analysis procedure works, and provide a basis for comparison of the proposed method to the original TOPSIS and similar methods. In applications, the new method produces results that are generally consistent with the original technique, but offers new features such as a clear interpretation of extreme points, more flexibility in setting extreme points, no normalization distortion, and the ability to handle non-monotonic criteria.     

A dual approach to solving nonlinear programming problems by unconstrained optimization

Several recent algorithms for solving nonlinear programming problems with equality constraints have made use of an augmented penalty Lagrangian function, where terms involving squares of the constraint functions are added to the ordinary Lagrangian. In this paper, the corresponding penalty Lagrangian for problems with inequality constraints is described, and its relationship with the theory of duality is examined. In the convex case, the modified dual problem consists of maximizing a differentiable concave function (indirectly defined) subject to no constraints at all. It is shown that any maximizing sequence for the dual can be made to yield, in a general way, an asymptotically minimizing sequence for the primal which typically converges at least as rapidly.Supported in part by the Air Force Office of Scientific Research under grant AF-AFOSR-72-2269.     

A new approach for solving repair limit problems

The usual approach to finding optimal repair limits on failure of a component is to use a finite state approximation Markov Decision Process (MDP). In this paper an alternative approach is introduced. Assuming a stochastically increasing repair cost, the optimum solution is shown to satisfy a certain two-point boundary condition, first order differential equation. An asymptotic formula for the optimal repair limit function is derived. Numerical solutions are obtained for some Weibull and Special Erlang distributed time to failure distributions. The structural form of the repair limit function results in a solution procedure which is several orders of magnitude faster than is achievable using previous methods.     

解可分离结构变分不等式的一种新的交替方向法

交替方向法是求解可分离结构变分不等式问题的经典方法之一, 它将一个大型的变分不等式问题分解成若干个小规模的变分不等式问题进行迭代求解. 但每步迭代过程中求解的子问题仍然摆脱不了求解变分不等式子问题的瓶颈. 从数值计算上来说, 求解一个变分不等式并不是一件容易的事情.因此, 本文提出一种新的交替方向法, 每步迭代只需要求解一个变分不等式子问题和一个强单调的非线性方程组子问题. 相对变分不等式问题而言, 我们更容易、且有更多的有效算法求解一个非线性方程组问题. 在与经典的交替方向法相同的假设条件下, 我们证明了新算法的全局收敛性. 进一步的数值试验也验证了新算法的有效性.     

A discrete Fourier method for solving strongly coupled mixed hyperbolic problems

This paper provides a discrete Fourier method for constructing stable numerical solutions of strongly coupled mixed hyperbolic problems. Using Crank-Nicholson scheme the exact solution of the discretized problem is found. Then the stability of the discrete solution is analyzed and illustrative examples are included.     

A WIN-WIN approach to multiple objective linear programming problems

Interactive decision making arose as a means to overcome the uncertainty concerning the decision maker's (DM) value function. So far the search is confined to nondominated alternatives, which assumes that a win–lose strategy is adopted. The purpose of this paper is to suggest a complementary interactive algorithm that uses an interior point method to solve multiple objective linear programming problems. As the algorithm proceeds, the DM has access to intermediate solutions. The sequence of intermediate solutions has a very interesting characteristic: all of the criteria are improved, that is, a solution Open image in new window , that follows another solution Open image in new window , has the values of all objectives greater than those of Open image in new window . This WIN-WIN feature allows the DM to reach a nondominated solution without making any trade-off among the objective functions. However, there is no impediment in proceeding with traditional multiobjective methods.     

Local elimination algorithms for solving sparse discrete problems

The class of local elimination algorithms is considered that make it possible to obtain global information about solutions of a problem using local information. The general structure of local elimination algorithms is described that use neighborhoods of elements and the structural graph describing the problem structure; an elimination algorithm is also described. This class of algorithms includes local decomposition algorithms for discrete optimization problems, nonserial dynamic programming algorithms, bucket elimination algorithms, and tree decomposition algorithms. It is shown that local elimination algorithms can be used for solving optimization problems.     

A new approach to variational problems with multiple scales

We introduce a new concept, the Young measure on micropatterns, to study singularly perturbed variational problems that lead to multiple small scales depending on a small parameter ε. This allows one to extract, in the limit ε → 0, the relevant information at the macroscopic scale as well as the coarsest microscopic scale (say ε^α) and to eliminate all finer scales. To achieve this we consider rescaled functions Rx (t) := x (s + ε^αt) viewed as maps of the macroscopic variable s ∈ Ω with values in a suitable function space. The limiting problem can then be formulated as a variational problem on the Young measures generated by R^εx. As an illustration, we study a one‐dimensional model that describes the competition between formation of microstructure and highest gradient regularization. We show that the unique minimizer of the limit problem is a Young measure supported on sawtooth functions with a given period. © 2001 John Wiley & Sons, Inc.