Search

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]

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 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]

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]

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 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]

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]

In practical problem situations data are usually inherently unreliable. A mathematical representation of uncertainty leads to stochastic optimization problems. In this paper the complexity of stochastic combinatorial optimization problems is discussed. Surprisingly, certain stochastic versions of NP-hard deterministic combinatorial problems appear to be solvable in polynomial time. [ABSTRACT FROM AUTHOR]

The challenge of maximizing the diversity of a collection of points arises in a variety of settings, including the setting of search methods for hard optimization problems. One version of this problem, called the Maximum Diversity Problem (MDP), produces a quadratic binary optimization problem subject to a cardinality constraint, and has been the subject of numerous studies. This study is focused on the Maximum Minimum Diversity Problem (MMDP) but we also introduce a new formulation using MDP as a secondary objective. We propose a fast local search based on separate add and drop operations and on simple tabu mechanisms. Compared to previous local search approaches, the complexity of searching for the best move at each iteration is reduced from quadratic to linear; only certain streamlining calculations might (rarely) require quadratic time per iteration. Furthermore, the strong tabu rules of the drop strategy ensure a powerful diversification capacity. Despite its simplicity, the approach proves superior to most of the more advanced methods from the literature, yielding optimally-proved solutions for many problems in a matter of seconds and even attaining a new lower bound. [ABSTRACT FROM AUTHOR]

In this work, we consider a complex flowshop scheduling problem in which both no-wait and separate setup times are considered. The optimisation criterion is the minimisation of the total completion time. We propose an effective dominance rule for the four machine case that can also be used for m machines. Five simple and fast heuristics are proposed along with two easy to code stochastic local search methods, one of them being based on Iterated Local Search (ILS). An extensive computational evaluation is carried out with two sets of 5,400 instances. All seven methods are compared to two recent algorithms. The results, confirmed by thorough statistical analyses, show that the proposed methods are more effective and efficient when compared to the best existing algorithms in the literature for the considered problem. [ABSTRACT FROM AUTHOR]

Variational inequalities and related problems may be solved via smooth bound constrained optimization. A comprehensive discussion of the important features involved with this strategy is presented. Complementarity problems and mathematical programming problems with equilibrium constraints are included in this report. Numerical experiments are commented. Conclusions and directions of future research are indicated. [ABSTRACT FROM AUTHOR]

Processes of iterated elimination of strategies that are not best responses are studied. Some suggestions are made about how rational players may use their mutual knowledge about game and behavior. [ABSTRACT FROM AUTHOR]

We propose a new Memetic Particle Swarm Optimization scheme that incorporates local search techniques in the standard Particle Swarm Optimization algorithm, resulting in an efficient and effective optimization method, which is analyzed theoretically. The proposed algorithm is applied to different unconstrained, constrained, minimax and integer programming problems and the obtained results are compared to that of the global and local variants of Particle Swarm Optimization, justifying the superiority of the memetic approach. [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 Colombian coffee supply network, managed by the Federación Nacional de Cafeteros de Colombia (Colombian National Coffee-Growers Federation), requires slimming down operational costs while continuing to provide a high level of service in terms of coverage to its affiliated coffee growers. We model this problem as a biobjective (cost-coverage) uncapacitated facility location problem (BOUFLP). We designed and implemented three different algorithms for the BOUFLP that are able to obtain a good approximation of the Pareto frontier. We designed an algorithm based on the Nondominated Sorting Genetic Algorithm; an algorithm based on the Pareto Archive Evolution Strategy; and an algorithm based on mathematical programming. We developed a random problem generator for testing and comparison using as reference the Colombian coffee supply network with 29 depots and 47 purchasing centers. We compared the algorithms based on the quality of the approximation to the Pareto frontier using a nondominated space metric inspired on Zitzler and Thiele's. We used the mathematical programming-based algorithm to identify unique tradeoff opportunities for the reconfiguration of the Colombian coffee supply network. Finally, we illustrate an extension of the mathematical programming-based algorithm to perform scenario analysis for a set of uncapacitated location problems found in the literature. [ABSTRACT FROM AUTHOR]

We consider a vector linear combinatorial optimization problem in which initial coefficients of objective functions are subject to perturbations. For Pareto and lexicographic principles of efficiency we introduce appropriate measures of the quality of a given feasible solution. These measures correspond to so-called stability and accuracy functions defined earlier for scalar optimization problems. Then we study properties of such functions and calculate the maximum norms of perturbations for which an efficient solution preserves the efficiency. [ABSTRACT FROM AUTHOR]

The data association problem consists of associating pieces of information emanating from different sources in order to obtain a better description of the situation under study. This problem arises, in particular, when, considering several sensors, we aim at associating the measures corresponding to a same target. This problem, widely studied in the literature, is often stated as a multidimensional assignment problem where a state criterion is optimized. While this approach seems satisfactory in simple situations where the risk of confusing targets is relatively low, it is much more difficult to get a correct description in denser situations. This is why, we propose, for the first time to our knowledge, to address this problem in a multiple criteria framework using a second complementary criterion, based on the identification of the targets. Due to the specificities of the problem, simple and efficient approaches can be used to generate non-dominated solutions. Moreover, we show that the accuracy of the proposed solutions is greatly increased when considering a second criterion. A bi-criteria interactive procedure is also introduced to assist an operator in solving conflicting situations. [ABSTRACT FROM AUTHOR]

In stochastic optimal control, a key issue is the fact that “solutions” are searched for in terms of “closed-loop control laws” over available information and, as a consequence, a major potential difficulty is the fact that present control may affect future available information. This is known as the “dual effect” of control. Our main result consists in characterizing the maximal set of closed-loop control laws containing open-loop ones and for which the information provided by observations closed with such a feedback remains fixed. We give more specific results in the two following cases: multi-agent systems and discrete time stochastic input-output systems with dynamic information structure. [ABSTRACT FROM AUTHOR]

Constraint programming and local search are two well known optimization technologies. In recent years, methods for combining these two technologies have been put forward, one of which advocates the use of constraint programming for searching the local neighborhood of the current solution. We present a search technique which improves on the performance of this constraint programming-based local search method and perform experiments on a variety of both simple and more complex combinatorial problems. We also demonstrate the benefit of combining local and complete search methods. [ABSTRACT FROM AUTHOR]

Geometric optimization is an important class of problems that has many applications, especially in engineering design. In this article, we provide new simplified proofs for the well-known associated duality theory, using conic optimization. After introducing suitable convex cones and studying their properties, we model geometric optimization problems with a conic formulation, which allows us to apply the powerful duality theory of conic optimization and derive the duality results valid for geometric optimization. [ABSTRACT FROM AUTHOR]

Some developments in structure and stability of stochastic programs during the last decade together with interrelations to optimization theory and stochastics are reviewed. With weak convergence of probability measures as a backbone we discuss qualitative and quantitative stability of recourse models that possibly involve integer variables. We sketch stability in chance constrained stochastic programming and provide some applications in statistical estimation. Finally, an outlook is devoted to issues that were not discussed in detail and to some open problems. [ABSTRACT FROM AUTHOR]

We consider a complex system consisting of N identical components that are expected to function properly during a given period (mission time). Due to the possibility of failure before completion of the mission time, one allows for maintenance as well as bum-in, the latter in order to cope with the problem of ‘infant mortality’. We present a two-level (Bayesian) Dynamic Programming approach to determine the optimal timing of the maintenance interventions and durations of bum-in, including maintenance-induced bum-in. We also discuss ways to reduce the ‘curse of dimensionality’. [ABSTRACT FROM AUTHOR]

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]

Medium to large network location problems can often be solved only approximately within reasonable computing time. Standard solution techniques focus on the tentative choice of locations embedded in an enumerative search. In contrast, the method presented here selects or rejects facilities conclusively and thus avoids costly backtracking schemes. It draws on supermodularity and Lagrangian relaxation. We rank well-known variable-fixing tests and propose a hierarchy of tests that provides an attractive time-accuracy trade-off which we assess computationally. [ABSTRACT FROM AUTHOR]

A family of two-stage location problems is considered. These problems involve a system providing a choice of depots and/or plants, each with an associated location cost, and a set of demand points which must be supplied, in such a way that the total cost is minimized. By using Lagrangian relaxation, lower bounds and heuristic solutions are obtained for two kinds of formulation involving two or three indexes for each transportation variable. The goodness of both formulations is compared by means of a computational study, and the results for several instances are presented. [ABSTRACT FROM AUTHOR]

In 1987, J. Dulá considered the problem of finding an upper bound for the expectation of a so-called ‘simplicial’ function of a random vector and used for this purpose first and total second moments. Under the same moment conditions we consider some different cases of ‘recourse’ functions and demonstrate how the related moment problems can be solved by solving nonsmooth (unconstrained) optimization problems and thereafter satisfying simple linear constraint systems. [ABSTRACT FROM AUTHOR]

A new concept of (normalized) convergence of random variables is introduced. This convergence is preserved under Lipschitz transformations, follows from convergence in mean and itself implies convergence in probability. If a sequence of random variables satisfies a limit theorem then it is a normalized convergent sequence. The introduced concept is applied to the convergence rate study of a statistical approach in stochastic optimization. [ABSTRACT FROM AUTHOR]

The problem of interest is to partition a collection of machines into production cells so that a given set of part-manufacturing requirements may be carried out optimally. In the present case transitions of parts between different cells is the only measure of machine partition goodness. The present formulation and approximate solution of this optimization problem is best described as one of successive approximations or as a one-at-a-time method. An initial cellular structure is taken and an easy part assignment optimization routine executed. With the part assignment fixed, a heuristic is employed to find an improved cell structure. These bipartite iterations continue until a convergence criterion is satisfied. Several small computer examples are provided and the straightforward requirements for large problem adaptation. [ABSTRACT FROM AUTHOR]