Search

Introduces a series of articles which appeared in the January 2005 issue. Reference to the papers presented at the 5th International Conference on Optimization: Techniques and Applications in Hong Kong, China; Claim that the papers were divided into three categories which are nonlinear optimization, scheduling and discrete optimization and engineering optimization.

This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms. [ABSTRACT FROM AUTHOR]

Decision problems involving multiple agents invariably lead to conflict and gaming. In recent years, multi-agent systems have been analyzed using approaches that explicitly assign to each agent a unique objective function and set of decision variables; the system is defined by a set of common constraints that affect all agents. The decisions made by each agent in these approaches affect the decisions made by the others and their objectives. When strategies are selected simultaneously, in a noncooperative manner, solutions are defined as equilibrium points [13,51] so that at optimality no player can do better by unilaterally altering his choice. There are other types of noncooperative decision problems, though, where there is a hierarchical ordering of the agents, and one set has the authority to strongly influence the preferences of the other agents. Such situations are analyzed using a concept known as a Stackelberg strategy [13,14,46]. The hierarchical optimization problem [11,16,23] conceptually extends the open-loop Stackelberg model to K players. In this paper, we provide a brief introduction and survey of recent work in the literature, and summarize the contributions of this volume. It should be noted that the survey is not meant to be exhaustive, but rather to place recent papers in context. [ABSTRACT FROM AUTHOR]

Recently Dekker and Hordijk [3,4] introduced conditions for the existence of deterministic Blackwell optimal policies in denumerable Markov decision chains with unbounded rewards. These conditions include ii-uniform geometric recurrence. The μ-uniform geometric recurrence property also implies the existence of average optimal policies, a solution to the average optimality equation with explicit formula's and convergence of the value iteration algorithm for average rewards. For this reason, the verification of μ-uniform geometric convergence is also useful in cases where average and α-discounted rewards are considered. On the other hand, μ-uniform geometric recurrence is a heavy condition on the Markov decision chain structure for negative dynamic programming problems. The verification of μ-uniform geometric recurrence for the Markov chain induced by some deterministic policy together with results by Sennott [14] yields the existence of a deterministic policy that minimizes the expected average cost for non-negative immediate cost functions. In this paper μ-uniform geometric recurrence will be proved for two queueing models: the K competing queues and the two centre open Jackson network with control of the service rates. [ABSTRACT FROM AUTHOR]

In this paper we study a method for global optimization of increasing positively homogeneous functions over the unit simplex, which is a version of the cutting angle method. Some properties of the auxiliary subproblem are studied and a special algorithm for its solution is proposed. A cutting angle method based on this algorithm allows one to find an approximate solution of some problems of global optimization with 50 variables. Results of numerical experiments are discussed. [ABSTRACT FROM AUTHOR]

This paper presents the application of a logic-based modelling language and integer programming framework for multicriteria optimisation proposed by Pinto and Rustem [12] to solve a bond portfolio problem. This application requires the analysis of conflicting objectives. The relevant information that should be taken into consideration during the solution search process can be better represented in terms of algebraic and logical relationships. The bond portfolio problem is introduced and the deterministic case is described based on the model by Nauss [9]. A logic-based model for a fictitious example is given, and finally the paper illustrates how one can interactively address the multiplicity of objectives. [ABSTRACT FROM AUTHOR]

In this paper, foundations of a new approach for solving vector optimization problems are introduced. Generalized Lagrangian duality, related for the first time with vector optimization, provides new scalarization techniques and allows for the generation of efficient solutions for problems which are not required to satisfy any convexity assumptions. [ABSTRACT FROM AUTHOR]

This paper considers the solution of the problem: infƒ[ y. x(y)] s.t. γ ϵ R[y,x(y)]⊆ Ek, where x(y) solves: min F(x, y) s.t. x ϵ (x, y) ⊆ En. In order to obtain local solutions, a first-order algorithm, which uses {dx(y)/dy} for solving a special case of the implicitly defined y-problem. is given. The derivative is obtained from {dx(y, r)/dy}. where r is a penalty function parameter and {x(y, r)} are approximations to the solution of the x-problem given by a sequential minimization algorithm. Conditions are stated under which x( y, r) and {dx( y, r)/dy} exist. The computation of {dx( y, r)/dy} requires the availability of ∇y F (x, y) and the partial derivatives of the other functions defining the set R(x, y) with respect to the parameters y. [ABSTRACT FROM AUTHOR]

In this paper, we provide a novel interpretation of a global optimization procedure for standard quadratic problems (QPs) in terms of selection models. A standard QP consists of maximizing a quadratic form over the standard simplex. Recently, local solutions to standard QPs have been obtained with the help of replicator dynamics, which were designed to model evolutionary processes. Following trajectories under these dynamics, one obtains a sequence of feasible points with strictly increasing objective values, which approach stationary points. We present regularity conditions which ensure that the limiting points are indeed local solutions, so that jamming could be avoided. Genetic engineering via negative fitness is a block pivoting procedure which either delivers a certificate for global optimality of the current local solution, or else enables an escape from its basin of attraction, if it is inefficient. The name originates from the way the block pivot is obtained: via minimization (rather than maximization) of a subproblem. We also elaborate on an important application, the search for a maximum clique in an undirected graph, and report both theoretical and empirical results. [ABSTRACT FROM AUTHOR]

When solving scenario-based stochastic programming problems, it is imperative that the employed solution methodology be based on some form of problem decomposition: mathematical, stochastic, or scenario decomposition. In particular, the scenario decomposition resulting from scenario approximations has perhaps the least tendency to be computationally tedious due to increases in the number of scenarios. Scenario approximations discussed in this paper utilize the second-moment information of the given scenarios to iteratively construct a (relatively) small number of representative scenarios that are used to derive bounding approximations on the stochastic program. While the sizes of these approximations grow only linearly in the number of random parameters, their refinement is performed by exploiting the behavior of the value function in the most effective manner. The implementation SMART discussed here demonstrates the aptness of the scheme for solving two-stage stochastic programs described with a large number of scenarios. [ABSTRACT FROM AUTHOR]

The paper deals with optimization of allocation of human resources among different activities. It is assumed that an individual is characterized by a ‘risk averse’ and ‘constant return to scale’ utility function of two variables: motivation to perform and reward following the performance. The individual is trying to maximize the utility by the best allocation of his time resources among the activities and by selecting the best portfolio of activities. Motivations are regarded, generally, as the product of the individual's preferences (i.e. subjective choice probabilities), productivities of time, output prices, performance and access probabilities, etc., while the rewards are profits or salaries connected with each activity. Satisfaction is defined as the maximum of utility attained for the optimum allocation and selection strategies. It is shown that for the given ‘equitable reward rate’, the optimum allocation and portfolio selection strategies can be derived explicitly and the derivation does not require the explicit knowledge of the individual's utility function. [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]

In modelling and managing complex environmental systems, inherent uncertainties of all relevant natural processes are to be taken into consideration. In the present paper diverse stochastic modelling and optimization approaches for handling such problems (primarily in the field of water quality analysis and control) are highlighted, drawing on the findings of case studies and real-world applications. [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]

The DFP algorithm of unconstrained optimization possesses excellent properties of convergence for convex functions. However, a convergence theory of the DFP algorithm without the convexity assumption has not yet been established. This paper gives the following result: If the objective function is suitably smooth, and if the DFP algorithm produces a convergent point sequence, then the limit point of the sequence is a critical point of the objective function. Also, some open questions are mentioned. [ABSTRACT FROM AUTHOR]

This paper presents a new class of methods for solving unconstrained optimization problems on parallel computers. The methods are intended to solve small to moderate dimensional problems where function and derivative evaluation is the dominant cost. They utilize multiple processors to evaluate the function, (finite difference) gradient, and a portion of the finite difference Hessian simultaneously at each iterate. We introduce three types of new methods, which all utilize the new finite difference Hessian information in forming the new Hessian approximation at each iteration; they differ in whether and how they utilize the standard secant information from the current step as well. We present theoretical analyses of the rate of convergence of several of these methods. We also present computational results which illustrate their performance on parallel computers when function evaluation is expensive. [ABSTRACT FROM AUTHOR]

This paper discusses the advantages of using spreadsheets for problem specification and report generation in optimization projects. It summarizes some of the mathematical programming software which is compatible with popular spreadsheets. A small production planning problem is used to illustrate the steps in input and processing of the results. Two programs are compared in detail. [ABSTRACT FROM AUTHOR]

Optimization algorithms or heuristics in which the user interacts significantly either during the solution process or as part of post-optimality analysis are becoming increasingly popular. An important underlying premise of such man/machine systems is that there are some steps in solving a problem in which the computer has an advantage and other steps in which a human has an advantage. This paper first discusses how man/machine systems can be useful in facilitating model specification and revision, coping with aspects of a problem that are difficult to quantify and assisting in the solution process. We then survey successful systems that have been developed in the areas of vehicle scheduling, location problems, job shop scheduling, course scheduling, and planning language-based optimization. [ABSTRACT FROM AUTHOR]

Systems reliability plays an important role in systems design, operation and management. Systems reliability can be improved by adding redundant components or increasing the reliability levels of subsystems. Determination of the optimal amount of redundancy and reliability levels among various subsystems under limited resource constraints leads to a mixed-integer nonlinear programming problem. The continuous relaxation of this problem in a complex system is a nonconvex nonseparable optimization problem with certain monotone properties. In this paper, we propose a convexification method to solve this class of continuous relaxation problems. Combined with a branch-and-bound method, our solution scheme provides an efficient way to find an exact optimal solution to integer reliability optimization in complex systems. [ABSTRACT FROM AUTHOR]

In this paper, we consider a mathematical program with complementarity constraints. We present a modified relaxed program for this problem, which involves less constraints than the relaxation scheme studied by Scholtes (2000). We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. We also consider a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is C-stationary to the original problem under the MPEC linear independence constraint qualification and, if the Hessian matrices of the Lagrangian functions of the relaxed problems are uniformly bounded below on the corresponding tangent space, it is M-stationary. We also obtain some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices mentioned above are new and can be verified easily. [ABSTRACT FROM AUTHOR]

In this paper, a functional inequality constrained optimization problem is studied using a discretization method and an adaptive scheme. The problem is discretized by partitioning the interval of the independent parameter. Two methods are investigated as to how to treat the discretized optimization problem. The discretization problem is firstly converted into an optimization problem with a single nonsmooth equality constraint. Since the obtained equality constraint is nonsmooth and does not satisfy the usual constraint qualification condition, relaxation and smoothing techniques are used to approximate the equality constraint via a smooth inequality constraint. This leads to a sequence of approximate smooth optimization problems with one constraint. An adaptive scheme is incorporated into the method to facilitate the computation of the sum in the inequality constraint The second method is to apply an adaptive scheme directly to the discretization problem. Thus a sequence of optimization problems with a small number of inequality constraints are obtained. Convergence analysis for both methods is established. Numerical examples show that each of the two proposed methods has its own advantages and disadvantages over the other. [ABSTRACT FROM AUTHOR]

Statistics and Optimization have been closely linked from the very outset. The search for a ‘best’ estimator (least squares, maximum likelihood, etc.) certainly relies on optimization tools. On the other hand, Statistics has often provided the motivation for the development of algorithmic procedures for certain classes of optimization problems. However, it is only relatively recently, more specifically in connection with the development of an approximation and sampling theory for stochastic programming problems, that the full connection has come to light. This in turn suggests a more comprehensive approach to the formulation of statistical estimation questions. This expository paper reviews some of the features of this approach. [ABSTRACT FROM AUTHOR]

Consider the gradually more and more complex problems of single row routing, channel routing and switchbox routing on the one hand, and the gradually less and less restrictive models (1-layer, Manhattan, unconstrained 2-layer, multilayer) on the other hand. The single row routing problems can always be solved in the Manhattan model, and the channel routing problem can always be solved in the unconstrained 2-layer model, in fact, both in linear time. In this paper, we show that the switchbox routing problem is solvable in the multilayer model, also in linear time. [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 formulation of the highway network design problem (NDP) as a bilevel linear program (BLP) allows more realistic solutions taking into account the reaction of users 10 improvements made by the system. In this paper, a conceptual framework for the optimization of investments in inter-regional highway networks in developing countries is proposed. The model is applied to the Tunisian network using actual data. Considerable effort was expended to make the implementation as realistic as possible, taking into consideration travel times, operating costs, accident costs, improvement costs, conservation laws, and effects of intra-regional flows. A new formulation allowing the incorporation of any improvement cost functions, including non-convex and non-concave functions, is introduced. [ABSTRACT FROM AUTHOR]

The introduction of uncertainty to mathematical programs greatly increases the size of the resulting optimization problems. Specialized methods that exploit program structures and advances in computer technology promise to overcome the computational complexity of certain classes of stochastic programs. In this paper we examine the progressive hedging algorithm for solving multi-scenario generalized networks. We present computational results demonstrating the effect of various internal tactics on the algorithm's performance. Comparisons with alternative solution methods are provided. [ABSTRACT FROM AUTHOR]

This paper concerns countable state space Markov decision processes endowed with a (long-run expected) average reward criterion. For these models we summarize and, in some cases, extend some recent results on sufficient conditions to establish the existence of optimal stationary policies. The topics considered are the following: (i) the new assumptions introduced by Sennott in [20–23], (ii) necessary and sufficient conditions for the existence of a bounded solution to the optimality equation, and (iii) equivalence of average optimality criteria. Some problems are posed. [ABSTRACT FROM AUTHOR]

In this paper, the properties of robust sets and robust functions are studied. Also, we study minimization of a robust function over a robust set and extend the optimality conditions of [3] and the algorithm of [4,5] to our case. The algorithm is shown to be effective. [ABSTRACT FROM AUTHOR]

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids arc in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems. [ABSTRACT FROM AUTHOR]

The paper reviews available models and techniques covering three classes of the multicriteria reliability problem. These classes include allocation of reliabilities in presence of multiple goals, reliability optimization with several kinds of failures and allocation of resources to optimize multiattribute systems. Optimization techniques are also suggested. The models and techniques are also evaluated with respect to their potential use in a DSS for reliability optimization. [ABSTRACT FROM AUTHOR]

This paper describes an implementation on the Neptune system at Loughborough University of Sutti's parallel (MIMD) algorithm [1–3] and an analysis of its performance. Parallel asynchronous versions of Powell's method [6] and Price's algorithm [7] are proposed, designed for efficient implementation on MIMD systems. [ABSTRACT FROM AUTHOR]

In this paper we will consider the effect of introducing parallel computers to solve optimisation problems. We briefly highlight four situations where most improvements are likely. We consider the possible interaction of the four classifications with the currently available parallel processing machines. A brief description of one of the parallel systems, ICL DAP, is outlined. We have implemented two parallel (SIMD) algorithms, one for local optimisation and the other for global optimisation, on the ICL DAP. Numerical results, together with the processing times, are reported. [ABSTRACT FROM AUTHOR]

A crucial step in global optimization algorithms based on random sampling in the search domain is decision about the achievement of a prescribed accuracy. In order to overcome the difficulties related to such a decision, the Bayesian Nonparametric Approach has been introduced. The aim of this paper is to show the effectiveness of the approach when an ad hoc clustering technique is used for obtaining promising starting points for a local search algorithm. Several test problems are considered. [ABSTRACT FROM AUTHOR]

This paper reviews tools which have great potential for reducing the difficulty of solving IP (and also MIP) problems, if well implemented in solvers. Recent experiments with Branch and Bound solvers, in connection with “Short Start Features”, have shown that implementations need and can still be improved. Concepts which are likely to be specially important for (0,1) MIP are pointed out. [ABSTRACT FROM AUTHOR]

Recent successes in applying tabu search to a wide variety of classical optimization problems have motivated the investigation of applying tabu search to the well-known general fixed charge problem (GFCP). In this paper, an adaptation of tabu search lo GFCP is described and computational results are given. In addition, the computational results are compared with those obtained from SWIFT-2, the most well-known and frequently used heuristic method for GFCP. As will be shown, the results are very encouraging. [ABSTRACT FROM AUTHOR]

In this paper, a new approach to cutting a rectangular sheet of material into pieces of arbitrary shapes is presented. The proposed method consists of two stages. After the generation of an initial solution, a tabu search is applied for finding a final cutting pattern. The presentation of the main ideas of the method is followed by a description of an implementation and some experimental results. [ABSTRACT FROM AUTHOR]

In this work, we study a nonsmooth optimization problem with generalized inequality constraints and an arbitrary set constraint. We present necessary conditions for a point to be a strict local minimizer of order k in terms of higher-order (upper and lower) Studniarski derivatives and the contingent cone to the constraint set. In the same line, when the initial space is finite dimensional, we develop sufficient optimality conditions. We also provide sufficient conditions for minimizers of order k using the lower Studniarski derivative of the Lagrangian function. Particular interest is put for minimizers of order two, using now a special second order derivative which leads to the Fréchet derivative in the differentiable case. [ABSTRACT FROM AUTHOR]

The article presents information on tabu search (TS), a mathematical optimization method. It mentions that a starting premise of TS is that intelligent inhibition plays a critical role in making effective use of memory. It is worth stressing that discoveries about effective uses of memory within the search methods may provide clues about strategies that humans are adept at employing.

The author offers his views on discrete optimization. According to him, the obvious analogies between quadratic assignment problems with a sum objective and quadratic assignment problems with a bottleneck objective led to an investigation on the common mathematical background of both problems. Some of the factors that makes the optimization attractive are the links to other mathematical areas like algebra and numerical analysis, geometry and combinatorics.

We propose a class of semidefinite programming (SDP) problems for which an optimal solution can be calculated directly, i.e., without using an iterative method. Several classes of such SDP problems have been proposed. Among them, Vanderbei and Yang (1995), Ohara (1998), and Wolkovicz (1996) are well known. We show that our class contains all of the three classes as special cases. [ABSTRACT FROM AUTHOR]

By parameter-free approach, we establish sufficient optimality conditions for nondifferentiable fractional variational programming under certain specific structure of generalized invexity. Employing the sufficient optimality conditions, two parameter-free dual models are formulated. The weak duality, strong duality and strict converse duality theorems are proved in the framework of generalized invexity. [ABSTRACT FROM AUTHOR]

Focuses on the approximability of hard combinatorial optimization problems. Description of developments in the theoretical characterization of approximation classes; Emphasis on Non-deterministic Polynomial Optimization problems; Suggestion that the study of approximability properties for optimization problems whose recognition version is NP-complete implies more subtle difficulties than that of NP-completeness.

We study the on-line problem of assigning tasks to identical machines whose regular working time — assumed to be unitary — can be extended. If the tasks assigned to a machine do not exceed the regular working time, then the working time of the machine is considered to be 1; otherwise, it is the completion time of the last task assigned to the machine. Each incoming task has to be assigned immediately to a machine and the assignment cannot be changed later. The objective is to minimize the sum of the working times of the machines. Since the regular working time of the machines can be seen as a given capacity, the problem can also be described through the bin packing terminology: the machines are viewed as bins and the tasks as items. A lower bound of 7/6 on the worst-case relative error of any on-line algorithm is shown. Then it is shown that a list scheduling heuristic which assigns the incoming task to the machine with smallest current load has worst-case error equal to 5/4. The bound is improved to 1.228 by a new algorithm which tends to load the partially loaded machines, as long as this does not cause an increase of the working time by more than a fixed and appropriately chosen quantity x » 0. [ABSTRACT FROM AUTHOR]

A new heuristic algorithm, based on the tabu search methodology, is proposed for constrained redundancy optimization in series and in complex systems. It has the advantage of not being blocked as soon as a local optimum is found. Results given by the new method are compared with those of previous heuristics on a series of examples. [ABSTRACT FROM AUTHOR]

Describes a survey in the form of a bibliography when degeneracy occurs in various integer linear optimization problems (ILP). Association of degeneracy to mathematical optimization problems; Existence of an optimal solution of ILP in a subsequent postoptimal analysis; Concerns on the primal cutting-plane methods.

We show that (L + l)-level linear programs are as difficult as level L of the polynomial-time hierarchy, even if one only considers problems with unique optimal solutions. [ABSTRACT FROM AUTHOR]

A penalty function method approach for solving a constrained bilevel optimization problem is proposed. In the algorithm, both the upper level and the lower level problems are approximated by minimization problems of augmented objective functions. A convergence theorem is presented. The method is applicable to the non-singleton lower-level reaction set case. Constraint qualifications which imply the assumptions of the general convergence theorem are given. [ABSTRACT FROM AUTHOR]

Scenario analysis, as proposed by Rockafellar and Wets, is a stochastic programming technique employing discrete scenarios with known probabilities, usually covering several time periods. The requirement of nonanticipativity (not using future information to make present decisions) is enforced during the computational solution by using Spingarn's method of partial inverses. The scenario analysis method as proposed relies on separability (with respect to scenarios) of all problem elements except the nonanticipativity constraint. We show how, by making a little more use of the partial inverse technique, one can include nonseparable convex constraints in such a procedure. As an illustrative example, we show how to analyze a portfolio optimization problem of Markowitz type (minimize variance for a given return) using scenarios. This offers the prospect of extending classical portfolio analysis from models based on historical behavior to models incorporating future scenarios of any desired type. [ABSTRACT FROM AUTHOR]

Focuses on the construction of branch-and-bound algorithms for combinatorial optimization problems encountered in practical applications. Determination of the basic structures of branch-and-bound algorithms by branching structures, lower bounding functions and dominance relations; Topics that are common to all branch-and-bound algorithms.

A model of a complicated function under uncertainty is constructed axiomatically, formalizing suppositions on rationality of information on a considered function. [ABSTRACT FROM AUTHOR]