Search

The paper presents results of CFD parametric study of centrifugal compressor stage vane diffusers in the Ansys CFX. The results obtained will be used to build a mathematical model of vane diffuser in optimization design system. Objects of research are vane diffusers with external relative diameter (relative to the diameter of the impeller) equal to 1.5; vane inlet angle of 20°; relative vane heights of 0.025, 0.034, 0.045, 0.06, and 0.08; and vane profile curvature angles of 10, 15, and 20 °. The characteristics of polytrophic efficiency, loss coefficient, recovery coefficient, ratio of inlet and outlet velocities, and flow deviation angle versus incidence angle are set. The analysis of the flow structure in the vane diffuser channels is presented. Unlike with a straight vane cascade, the deviation angle in the circular rows of vane diffusers tends to increase with increasing row density. This may be due to the complex nature of the interaction of the active part of the flow with separation zones. In rows with almost straight vanes at a lower density, the separation zone on the pressure side decreases and even shifts to the very end of the suction side. [ABSTRACT FROM AUTHOR]

This paper deals with multicriteria discrete-continuous problems of scheduling nonpreemptable jobs. The need for reusability and modularity leads us to build a “generic” optimisation and simulation framework, while the need to quickly generate good compromises between conflicting objectives requires the implementation of multicriteria scheduling models. This paper describes the practical possibilities of three hybrid models within this framework. The validation of the framework is presented in terms of its application to a real, highly constrained, discrete-continuous problem. The optimisation model is based on the hybridisation of a classical hill-climber meta-heuristic with the Promethee II multicriteria method. [ABSTRACT FROM AUTHOR]

Abstract??The paper considers the problem of finding a spanning arborescence on a directed network whose arc costs are partially known. It is assumed that each arc cost can take on values from a known interval defining a possible economic scenario. In this context, the problem of finding the spanning arborescence whichbetterapproaches to that of minimum overall cost under each possible scenario is studied. The minimax regret criterion is proposed in order to obtain such a robust solution of the problem. As it is shown, the bounds on the optimal value of the minimax regret optimization problem obtained in a previous paper, can be used here in a Branch and Bound algorithm in order to give an optimal solution. The computational behavior of the algorithm is tested through numerical experiments. [ABSTRACT FROM AUTHOR]

This paper presents a surrogate constraint tabu thresholding (SCTT) implementation for solving the frequency assignment problem. The frequency assignment problem is an important combinatorial optimisation problem that arises in telecommunications. The main objective is to assign radio frequencies to a number of communication links such that interference is minimised. Interference is minimised by satisfying a number of problem specific constraints. The surrogate constraint is created by taking a weighted sum of the constraints not satisfied. SCTT is compared with a tabu thresholding method from the literature on a set of simulated but realistic test problems with respect to quality of the solution in a given time period. Computational results show that SCTT is more efficient and effective for all the test problems. [ABSTRACT FROM AUTHOR]

In formulating a combinatorial optimisation problem (COP) using Discrete or Integer Programming (IP) modelling techniques, the modeller is restricted to use only certain predefined discrete variables and sets which are linked by sets of linear equality and inequality constraints. Definition of many COPs includes restrictions in which the use of dis-equality (DI) constraints in their mathematical representation is inevitable. To represent this type of constraint a number of binary variables and extra constraints are usually introduced, which lead to an increase in the size of the model in terms of variables and constraints. In this paper, we introduce a new class of discrete variables which enables the modeller to represent DI constraints more efficiently in the mathematical formulation of a combinatorial optimisation problem. We have also introduced a new branching scheme to the conventional simplex based Branch and Bound (B&B) algorithm in order to deal with this type of variables. To study the effect of these variables, we modelled and solved a set of five classic problems, first using conventional MP variables and second, exploiting the new proposed variables, and compared the results. The empirical results show a promising improvement on the performance of the B&B algorithm. The contribution of this paper is (1) the introduction of a new class of discrete variables which can help to build smaller models, and (2) new branching schemes on these variables that can improve the B&B performance. [ABSTRACT FROM AUTHOR]

This paper explores the use of simulated annealing (SA) for solving arbitrary combinatorial optimisation problems. It reviews an existing code called GPSIMAN for solving 0–1 problems, and evaluates it against a commercial branch-and-bound code, OSL. The problems tested include travelling salesman, graph colouring, bin packing, quadratic assignment and generalised assignment. The paper then describes a technique for representing these problems using arbitrary integer variables, and shows how a general simulated annealing algorithm can also be applied. This new code, INTSA, outperforms GPSIMAN and OSL on almost all of the problems tested. [ABSTRACT FROM AUTHOR]

This paper presents a special class of equilibria in finite strategy noncooperative games, which are extensions of the traditional Nash equilibrium solution. An underlying role in these equilibria play the assumed extended models of players' rationality principles which admit their non-myopic behaviour. The crucial idea is that players possessing some information about their opponents and the game itself can forecast the consequences of their choices by analyzing the ‘move-countermove’ possible sequences and accordingly predict the stability of game outcomes. The class of discussed equilibria besides the classical Nash equilibrium includes all the solutions considered in metagame and hypergame theories, and its determinants allow for a useful characterization of new potential equilibria concepts in modeled real-life conflicts. For specific equilibrium concepts, their individual properties are discussed and some analytical characterizations are provided. The paper concludes with the description of a computer-based procedure developed for calculating different kinds of generalized equilibrium points. Possible applications of this procedure within simulation and gaming are briefly discussed. [ABSTRACT FROM AUTHOR]

This paper proposes a mechanism to produce equivalent Lipschitz surrogates for zero-norm and rank optimization problems by means of the global exact penalty for their equivalent mathematical programs with an equilibrium constraint (MPECs). Specifically, we reformulate these combinatorial problems as equivalent MPECs by the variational characterization of the zero-norm and rank function, show that their penalized problems, yielded by moving the equilibrium constraint into the objective, are the global exact penalization, and obtain the equivalent Lipschitz surrogates by eliminating the dual variable in the global exact penalty. These surrogates, including the popular SCAD function in statistics, are also difference of two convex functions (D.C.) if the function and constraint set involved in zero-norm and rank optimization problems are convex. We illustrate an application by designing a multi-stage convex relaxation approach to the rank plus zero-norm regularized minimization problem. [ABSTRACT FROM AUTHOR]

In this paper, proper optimality concepts in vector optimization with variable ordering structures are introduced for the first time and characterization results via scalarizations are given. New type of scalarizing functionals are presented and their properties are discussed. The scalarization approach suggested in the paper does not require convexity and boundedness conditions. [ABSTRACT FROM AUTHOR]

In 1937, George Pólya wrote what is considered one of the most significant papers in 20th-century mathematics. The article contained one theorem and 100 pages of applications. It introduced a combinatorial method which led to unexpected applications to diverse problems in science like the enumeration of isomers of chemical compounds. Pólya's theory of enumeration was discussed in detail in [1] by Shriya Anand, a summer student of the author. In what follows, we briefly recall the theory and complement the earlier article by adding some other applications not discussed there. [ABSTRACT FROM AUTHOR]

This paper presents a convex mathematical programming model for the global optimization of recycle/reuse water networks. The model is based on a general superstructure that includes the major configurations of interest such as segregation, mixing, recycle, bypass, and treatment of streams needed to satisfy the process and environmental constraints. The basic idea of the model formulation is to consider component balances, treating as optimization variables the individual flowrates. This formulation avoids the bilinear terms that appear when the compositions and total flowrates are considered as optimization variables. The objective function consists in the minimization of the total annual cost including the fresh sources costs, the treatment units costs (which are reformulated as convex functions) and the piping costs. Four examples problems are solved to show the applicability of the proposed model. [ABSTRACT FROM AUTHOR]

The present paper studies the following constrained vector optimization problem: $$\mathop {\min }\limits_C f(x),g(x) \in - K,h(x) = 0$$, where f: ℝ n → ℝ m, g: ℝ n → ℝ p are locally Lipschitz functions, h: ℝ n → ℝ q is C1 function, and C ⊂ ℝ m and K ⊂ ℝ p are closed convex cones. Two types of solutions are important for the consideration, namely w-minimizers (weakly efficient points) and i-minimizers (isolated minimizers of order 1). In terms of the Dini directional derivative first-order necessary conditions for a point x0 to be a w-minimizer and first-order sufficient conditions for x0 to be an i-minimizer are obtained. Their effectiveness is illustrated on an example. A comparison with some known results is done. [ABSTRACT FROM AUTHOR]

This paper deals with downgrading the 1-median, i.e., changing values of parameters within certain bounds such that the optimal objective value of the location problem with respect to the new values is maximized. We suggest a game-theoretic view at this problem which leads to a characterization of an optimal solution. This approach is demonstrated by means of the Downgrading 1-median problem in the plane with Manhattan metric and implies an $\mathcal {O}(n\log^{2}n)$ time algorithm for this problem. [ABSTRACT FROM AUTHOR]

An optimization problem is defined by an objective function to be maximized with respect to a set of constraints. To overcome some theoretical and practical difficulties, the constraint-set is sometimes relaxed and “easier” problems are solved. This led us to study relaxations providing exactly the same set of optimal solutions. We give a complete characterization of these relaxations and present several examples. While the relaxations introduced in this paper are not always easy to solve, they may help to prove that some mathematical programs are equivalent in terms of optimal solutions. An example is given where some of the constraints of a linear program can be relaxed within a certain limit. [ABSTRACT FROM AUTHOR]

Given one instance of an $\mathcal{NP}$ -hard optimization problem, can we tell in advance whether it is exactly solvable or not? If it is not, can we predict which approximate algorithm is the best to solve it? Since the behavior of most approximate, randomized, and heuristic search algorithms for $\mathcal{NP}$ -hard problems is usually very difficult to characterize analytically, researchers have turned to experimental methods in order to answer these questions. In this paper we present a machine learning-based approach to address the above questions. Models induced from algorithmic performance data can represent the knowledge of how algorithmic performance depends on some easy-to-compute problem instance characteristics. Using these models, we can estimate approximately whether an input instance is exactly solvable or not. Furthermore, when it is classified as exactly unsolvable, we can select the best approximate algorithm for it among a list of candidates. In this paper we use the MPE (most probable explanation) problem in probabilistic inference as a case study to validate the proposed methodology. Our experimental results show that the machine learning-based algorithm selection system can integrate both exact and inexact algorithms and provide the best overall performance comparing to any single candidate algorithm. [ABSTRACT FROM AUTHOR]

Due to the large amounts of data required to be processed by the typical Grid job, it is conceivable that the use of optical transport networks in Grid deployment (hence the term “Lambda Grid”) will increase. The exact topology of the interconnecting network is obtained by solving a dimensioning problem, and the outcome of this strongly depends on both the expected workload characteristics and Grid scheduling policy. Solving this combined scheduling and dimensioning problem using straightforward ILP modelling is cumbersome; however, for steady-state Grid operation, Divisible Load Theory (DLT) can yield scalable formulations of this problem. In this paper, the on-line hierarchical scheduling on a lambda Grid of workload approaching the Grid’s capacity in a two-tier Grid mode of operation is studied. A number of these algorithms are goal-driven, in the sense that target per-resource goals are obtained from the off-line solution to the Divisible Load model. We compare these on-line multiresource scheduling policies for different workloads, Grid interconnection topologies and Grid parameters. We show that these algorithms perform well in the studied scenarios when compared to a fully centralized scheduling algorithm. [ABSTRACT FROM AUTHOR]

Abstract This paper proposes a new robust FIR equalizer for discrete time systems subject to parameter uncertainties in the matrices of the system state-space model from an H8 perspective. The uncertain parameters are supposed to belong to a given convex bounded polyhedral domain. The discrete algebraic Riccati inequality (DARI) and linear matrix inequality (LMI) provide an extremely superior methodology in the H8 control fields. By the H8 and robust methods in conjunction with the bounded real lemma, the robust FIR equalizer design is transformed into a standard LMI optimization problem. An example is given to illustrate the proposed methodology. [ABSTRACT FROM AUTHOR]

Conventional supervised learning in neural networks is carried out by performing unconstrained minimization of a suitably defined cost function. This approach has certain drawbacks, which can be overcome by incorporating additional knowledge in the training formalism. In this paper, two types of such additional knowledge are examined: Network specific knowledge (associated with the neural network irrespectively of the problem whose solution is sought) or problem specific knowledge (which helps to solve a specific learning task). A constrained optimization framework is introduced for incorporating these types of knowledge into the learning formalism. We present three examples of improvement in the learning behaviour of neural networks using additional knowledge in the context of our constrained optimization framework. The two network specific examples are designed to improve convergence and learning speed in the broad class of feedforward networks, while the third problem specific example is related to the efficient factorization of 2-D polynomials using suitably constructed sigma-pi networks. [ABSTRACT FROM AUTHOR]

This paper describes a novel approach for solving combinatorial optimisation problems called Simulated Jumping. It is based on ideas from spin-glasses, simulated annealing and self-organisation. We start from a low temperature, and the system is then subjected to a rapid heating and cooling process (a shaking process). This process is controlled by the system's energy in a self-organised manner. The heating and cooling process will continuously melt and freeze local regions; this process pushes the system out of local minima and hence minimises the energy function. Application of the Simulated Jumping method to the Quadratic Assignment and Asymmetric Travelling Salesman problems gives promising results. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with an algorithm which combines the generalized linear programming technique proposed by Dantzig and Wolfe with the stochastic quasi-gradient method in order to solve stochastic programs with recourse. In this way, we overcome the difficulties arising in finding the exact values of the objective function of recourse problems by replacing them with the statistical estimates of the function. We present the basic steps of the proposed algorithm focusing our attention on its implementation alternatives aimed at improving both the convergence and computational performances. The main application areas are mentioned and some computational experience in the validation of our approach is reported. Finally, we discuss the possibilities of parallelization of the proposed algorithmic schemes. [ABSTRACT FROM AUTHOR]

This paper considers the problem of finding minimal length tree networks on the unit sphere Φ of a given point set (V) where distance is measured along great circular arcs. The related problems of finding a Steiner Minimal Tree SMT (V) and of finding a Minimum Spanning Tree MST(V) are treated through a simplicial decomposition technique based on computing the Delaunay Triangulation DT (V) and the Voronoi Diagram VD(V) of the given point set. O (N log N) algorithms for computing DT(V), VD(V), and WST(V) as well as an O(N log N) heuristic for finding a sub-optimal SMT(V) solution are presented, together with experimental results for randomly distributed points on Φ. [ABSTRACT FROM AUTHOR]

Economists have found a need to model agents who behave in ways that are not consistent with the traditional notions of rational behavior under uncertainty but that are oriented in some looser manner toward achieving ‘good’ outcomes. Adaptation over time in a myopic manner, rather that forward-looking optimization, has been proposed as one such model of behavior that displays bounded rationality. This paper investigates the relationship between adaptation as a model of behavior and as an algorithmic approach that has been used in computing solutions to optimization problems. It describes a specific adaptive model of behavior in discrete choice problems, one that is closely related to adaptive algorithms for optimization, and shows that this model can be fruitfully applied in studying several economic issues. [ABSTRACT FROM AUTHOR]

Three possible approaches to stochastic programming problems defined in time (so that they contain random processes) are described in this paper: (1) an application of the extremal theory of random processes; (2) an exponential penalty model approach related to scenario analysis; (3) a modification of the entropic penalty approach. Explicit results are derived for some special cases. [ABSTRACT FROM AUTHOR]

The purpose of the paper is to give a survey of methods, partly derived by the author in joint work with other researchers, concerning the problem of constructing e-optimal strategies for partially observable MDPs. The methods basically consist in transforming the problem into one of approximation: Starting from the original problem a sequence of approximating problems is constructed such that: (i) For each approximating problem an optimal strategy can actually be computed, (ii) Given ϵ » 0, there exists an approximating problem such that the optimal strategy for the latter is ϵ-optimal for the original problem. [ABSTRACT FROM AUTHOR]

This paper concerns the problem of locating a central facility on a connected network N. The network, N, could be representative of a transport system, while the central facility takes the form of a connected subgraph of N. The problem is to locate a central facility of minimum length so that each of several demand points on N is covered by the central facility a demand point at vi in N is covered by the central facility if the shortest path distance between vi and the closest point in the central facility does not exceed a parameter ri. This location problem is NP-hard, but for certain special cases, efficient solution methods are available. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimizing a nonlinear objective function subject to a system of bipolar fuzzy relational equations with max- $T_{L}$ composition, where $T_{L}$ is the Łukasiewicz triangular norm. It shows that the feasible domain, i.e., the solution set of a system of bipolar fuzzy relational equations, can be reformulated as a system of 0-1 mixed integer inequalities. Consequently, such a type of optimization problems can be handled within the framework of 0-1 mixed integer optimization requiring no particular solving techniques. [ABSTRACT FROM AUTHOR]

In this paper, the concept of second order generalized α-type I univexity is introduced. Based on the new definitions, we derive weak, strong and strict converse duality results for two second order duals of a minmax fractional programming problem. [ABSTRACT FROM AUTHOR]

In this paper we propose a novel message-passing algorithm, the so-called Action-GDL, as an extension to the generalized distributive law (GDL) to efficiently solve DCOPs. Action-GDL provides a unifying perspective of several dynamic programming DCOP algorithms that are based on GDL, such as DPOP and DCPOP algorithms. We empirically show how Action-GDL using a novel distributed post-processing heuristic can outperform DCPOP, and by extension DPOP, even when the latter uses the best arrangement provided by multiple state-of-the-art heuristics. [ABSTRACT FROM AUTHOR]

With the advent use of sophisticated and high-cost machines coupled with higher labor costs, concurrent optimization of machining process parameters and tolerance allocation plays a vital role in producing the parts economically. In this paper, an effort is made to concurrently optimize the manufacturing cost of piston and cylinder components by optimizing the operating parameters of the machining processes. Design of experiments (DoE) is adopted to investigate systematically the machining process parameters that influence product quality. In addition, tolerance plays a vital role in assembly of parts in manufacturing industries. For the selected piston and cylinder component, improvements efforts are made to reduce the total manufacturing cost of the components. By making use of central composite rotatable design method, a module of DoE, a mathematical model is developed for predicting the standard deviation of the tolerance achieved by grinding process. This mathematical model, which gives 93.3% accuracy, is used to calculate the quality loss cost. The intent of concurrent optimization problem is to minimize total manufacturing cost and quality loss function. Genetic algorithm is followed for optimizing the parameters. The results prove that there is a considerable reduction in manufacturing cost without violating the required tolerance, cutting force, and power. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of solutions for multi-choice games which admit a potential, such as the potential associated with the extended Shapley value proposed by Hsiao and Raghavan (Int J Game Theory 21:301–302, 1992; Games Econ Behav 5:240–256, 1993). Several axiomatizations of the family of all solutions that admit a potential are offered and, as a main result, it is shown that each of these solutions can be obtained by applying the extended Shapley value to an appropriately modified game. In the framework of multi-choice games, we also provide an extension of the reduced game introduced by Hart and Mas-Colell (Econometrica 57:589–614, 1989). Different from the works of Hsiao and Raghavan (1992, 1993), we provide two types of axiomatizations, one is the analogue of Myerson’s (Int J Game Theory 9:169–182, 1980) axiomatization of the Shapley value based on the property of balanced contributions. The other axiomatization is obtained by means of the property of consistency. [ABSTRACT FROM AUTHOR]

In this paper, we derive some existence results for generalized variational inequalities associated with mappings satisfying the ( S)+ condition. The relation between the ( S)+ and ( S) conditions is discussed. As an application, we also consider multivalued complementarity problems associated with mappings satisfying the ( S)+ condition, and prove a theorem to characterize the solvability of such problems in terms of exceptional families of elements. [ABSTRACT FROM AUTHOR]

According to the characterization of eigenvalues of a real symmetric matrix A, the largest eigenvalue is given by the maximum of the quadratic form 〈 xA, x〉 over the unit sphere; the second largest eigenvalue of A is given by the maximum of this same quadratic form over the subset of the unit sphere consisting of vectors orthogonal to an eigenvector associated with the largest eigenvalue, etc. In this study, we weaken the conditions of orthogonality by permitting the vectors to have a common inner product r where 0 ≤ r < 1. This leads to the formulation of what appears—from the mathematical programming standpoint—to be a challenging problem: the maximization of a convex objective function subject to nonlinear equality constraints. A key feature of this paper is that we obtain a closed-form solution of the problem, which may prove useful in testing global optimization software. Computational experiments were carried out with a number of solvers. [ABSTRACT FROM AUTHOR]

Abstract  The aim of the paper is to obtain some theoretical and numerical properties of Saaty’s and Koczkodaj’s inconsistencies of pairwise comparison matrices (PRM). In the case of 3 ×  3 PRM, a differentiable one-to-one correspondence is given between Saaty’s inconsistency ratio and Koczkodaj’s inconsistency index based on the elements of PRM. In order to make a comparison of Saaty’s and Koczkodaj’s inconsistencies for 4  ×  4 pairwise comparison matrices, the average value of the maximal eigenvalues of randomly generated n ×  n PRM is formulated, the elements a ij (i j) of which were randomly chosen from the ratio scale $$\dfrac{1}{M}, \dfrac{1}{M-1}, \ldots , \dfrac{1}{2}, 1, 2, \ldots , M - 1, M,$$ with equal probability 1/(2M − 1) and a ji is defined as 1/a ij . By statistical analysis, the empirical distributions of the maximal eigenvalues of the PRM depending on the dimension number are obtained. As the dimension number increases, the shape of distributions gets similar to that of the normal ones. Finally, the inconsistency of asymmetry is dealt with, showing a different type of inconsistency. [ABSTRACT FROM AUTHOR]

Abstract  This paper describes a new multiobjective interactive memetic algorithm applied to dynamic location problems. The memetic algorithm integrates genetic procedures and local search. It is able to solve capacitated and uncapacitated multi-objective single or multi-level dynamic location problems. These problems are characterized by explicitly considering the possibility of a facility being open, closed and reopen more than once during the planning horizon. It is possible to distinguish the opening and reopening periods, assigning them different coefficient values in the objective functions. The algorithm is part of an interactive procedure that asks the decision maker to define interesting search areas by establishing limits to the objective function values or by indicating reference points. The procedure will be applied to some illustrative location problems. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we introduce a new combinatorial invariant called q-binomial moment for q-ary constant weight codes. We derive a lower bound on the q-binomial moments and introduce a new combinatorial structure called generalized (s, t)-designs which could achieve the lower bounds. Moreover, we employ the q-binomial moments to study the undetected error probability of q-ary constant weight codes. A lower bound on the undetected error probability for q-ary constant weight codes is obtained. This lower bound extends and unifies the related results of Abdel-Ghaffar for q-ary codes and Xia-Fu-Ling for binary constant weight codes. Finally, some q-ary constant weight codes which achieve the lower bounds are found. [ABSTRACT FROM AUTHOR]

In his 1976 book, Proofs and Refutations, Lakatos presents a collection of case studies to illustrate methods of mathematical discovery in the history of mathematics. In this paper, we reframe these methods in ways that we have found make them more amenable for use as a framework for research on learning and teaching mathematics. We present an episode from an undergraduate abstract algebra classroom to illustrate the guided reinvention of mathematics through processes that strongly parallel those described by Lakatos. Our analysis suggests that the constructs described by Lakatos can provide a useful framework for making sense of the mathematical activity in classrooms where students are actively engaged in the development of mathematical ideas and provide design heuristics for instructional approaches that support the learning of mathematics through the process of guided reinvention. [ABSTRACT FROM AUTHOR]

Abstract??In this paper, we consider Levitin?Polyak type well-posedness for a general constrained vector optimization problem. We introduce several types of (generalized) Levitin?Polyak well-posednesses. Criteria and characterizations for these types of well-posednesses are given. Relations among these types of well-posedness are investigated. Finally, we consider convergence of a class of penalty methods under the assumption of a type of generalized Levitin?Polyak well-posedness. [ABSTRACT FROM AUTHOR]

This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach. [ABSTRACT FROM AUTHOR]

Quasi-Newton equations play a central role in quasi-Newton methods for optimization and various quasi-Newton equations are available. This paper gives a survey on these quasi Newton equations and studies properties of quasi-Newton methods with updates satisfying different quasi-Newton equations. These include single-step quasi-Newton equations that use only gradient information and that use both gradient and function value information in one step, and multi-step quasi-Newton equations that use the gradient information in last m steps. Main properties of quasi-Newton methods with updates satisfying different quasi-Newton equations are studied. These properties include the finite termination property, invariance, heredity of positive definite updates, consistency of search directions, global convergence and local superlinear convergence properties. [ABSTRACT FROM AUTHOR]

An approach to the sensitivity analysis for discrete optimization problems with perturbed objective function is presented. The problem is stated in the following general form: min{ΣeϵYc(e):Y ϵ F}, where c = (c(e), e ϵ E) is a vector of weights for some finite set E, and F ⊂ 2e is a given family of feasible subsets. It is assumed that the set of feasible solutions F is fixed, but the coefficients of the vector c may vary. The main problem considered in this paper concerns the following question: How does the maximum relative error of a given feasible solution depend on inaccuracies of the problem data? Two particular perturbations of the vector c are considered: (i) it is assumed that c is in a closed ball with radius δ ≥ 0 and center c0 ≥ 0 or (ii) the relative deviation of c(e) from the value c0e) is not greater than δ for any e ϵ E, i.e., ∣c(e) - c0(e)∣ ≤ δc0(e), e ϵ E. For a given feasible solution X ϵ F, two functions of the parameter δ are introduced: the sensitivity function s(X, δ) and the accuracy function a(X, δ). The values of s(X, δ) and a(X, δ) are equal to the maximum relative error of the solution X when the perturbations of problem data are of the type (i) or (ii), respectively. Some general, but computationally inefficient formulae for calculating these functions are derived and their properties are studied. It is shown that s(X, δ) and a(X, δ) are nondecreasing, convex functions with a limited number of breakpoints. A practically efficient method of calculating upper and lower envelopes for the accuracy function is presented. This method is based on the notion of k-best solutions of the problem. It gives an interval to which the maximum relative error of the solution X must belong when the coefficients of vector c are given with accuracy δ. The approach is illustrated with an example of the symmetric traveling salesman problem. [ABSTRACT FROM AUTHOR]

This paper represents an integration of Mixed Integer Programming (MIP) and Constraint Logic Programming (CLP) which, like MIP, tightens bounds rather than adding constraints during search. The integrated system combines components of the CLP system ECLiPSe [7] and the MIP system CPLEX [5], in which constraints can be handled by either one or both components. Our approach is introduced in three stages. Firstly, we present an automatic transformation which maps CLP programs onto such CLP programs that any disjunction is eliminated in favour of auxiliary binary variables. Secondly, we present improvements of this mapping by using a committed choice operator and translations of pre-defined nonlinear constraints. Thirdly, we introduce a new hybrid algorithm which reduces the solution space of the problem progressively by calling finite domain propagation of ECLiPSe as well as dual simplex of CPLEX. The advantages of this integration are illustrated by efficiently solving difficult optimisation problems like the Hoist Scheduling Problem [23] and the Progressive Party Problem [27]. [ABSTRACT FROM AUTHOR]

This paper develops necessary and sufficient conditions for the set of solutions to an optimization problem to be nondecreasing in a weak sense still strong enough to guarantee the existence of an increasing selection, and thus strong enough to guarantee monotonicity when the solution is unique, as well as necessary and sufficient conditions for the set of optimizers to be nondecreasing in a strong sense which is strong enough to rule out the possibility of a decreasing selection. These necessary and sufficient conditions are variations of quasisupermodularity and the single crossing property introduced in Milgrom-Shannon [13]. Moreover, to determine when an objective function satisfies these conditions, this paper develops several characterizations of quasisupermodularity and the single crossing property and their variants, both in terms of differential conditions and in terms of restrictions on the structure of the level sets of these functions. Several examples are given to choice theory under loss aversion and to an auction problem. [ABSTRACT FROM AUTHOR]

In this paper, two different decision models for the planning of highway pavement improvements are presented. In the first model, we want to get a prescribed improvement in the state of the highway network with minimal agency cost. In the second model, a given amount of money is distributed between the highway sections in different states in such a way that the achieved improvements should be the best in some sense. The first model helps the administration in the estimation of the necessary cost for the annual highway improvements. The second model in addition gives an objective tool to the administration for the distribution of the total amount of money between the different regions of the country. We present the construction of the models in detail. Both of them use Markov transition probabilities according to the states of the highway sections and produce a special structure, large-scale, linear programming problem. Some numerical results are presented on the data from Hungarian highways. [ABSTRACT FROM AUTHOR]

The paper briefly presents Topsøe's setup and gives two results based on that. A delta theorem for multifunctions improving that of King [2] is given. In particular, the contingent derivative may be a compact-valued instead of a single-valued multifunction. Stochastic optimization is also discussed. Some results are achieved for the limit distribution of optimal values as well as of optimal solutions. [ABSTRACT FROM AUTHOR]

Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Uncertainty in the parameters of a mathematical program may present a modeller with considerable difficulties. Most approaches in the stochastic programming literature place an apparent heavy data and computational burden on the user and as such are often intractable. Moreover, the models themselves are difficult to understand. This probably explains why one seldom sees a fundamentally stochastic model being solved using stochastic programming techniques. Instead, it is common practice to solve a deterministic model with different assumed scenarios for the random coefficient. In this paper we present a simple approach to solving a stochastic model, based on a particular method for combining such scenario solutions into a single, feasible policy. The approach is computationally simple and easy to understand. Because of its generality, it can handle multiple competing objectives, complex stochastic constraints and may be applied in contexts other than optimization. To illustrate our model, we consider two distinct, important applications: the optimal management of a hydro-thermal generating system and an application taken from portfolio optimization. [ABSTRACT FROM AUTHOR]

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times. The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage. The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, the p-median problem and the fixed-charge p-median problem. Computational results are given for problems of up to the size 200 customers ⊗ 200 potential facility sites. [ABSTRACT FROM AUTHOR]