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.

Wireless local area networks (WLAN) has been in the spotlight as a potential solution to solve the exponentially growing demand of wireless services due to its wide availability and there have been a plenty of research works on WLAN including mathematical modeling and analysis. However, the spatial modeling and analysis of WLAN have received little attention due to the complexity in the dynamics of WLAN. In this paper, we provide spatial modeling and analysis based on stochastic geometry theory to investigate the impact of the spatial distribution on the performance of WLAN. Specifically, this paper is concerned with the correlation between consecutive packet transmissions. Throughout our analysis and simulation study we provide the conditions where the independence assumption on individual transmission results holds, which is widely assumed in most of the previous works on WLAN. [ABSTRACT FROM AUTHOR]

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]

Busy periods of finite buffer tandem service systems have not been addressed in the available literature. This paper defines the stage-I and stage-II busy periods of a two-stage tandem service system Mx/M/c→/PH(r)/1/K, analytically obtains their distributions, and presents efficient algorithms for the distributions with uniform error in time. The detailed analysis and algorithmic implementation for the two-stage tandem service system are completed, and the theoretical basis for its potential practical applications is provided. [ABSTRACT FROM AUTHOR]

In this paper, we present an efficient implementation of heuristic procedures for solving the continuous network design problem where network users behave according to Wardrop's first principle of traffic equilibrium. Numerical results involving a ‘standard’ benchmark problem are given. Also, it is shown that the cost mapping arising in the Iterative-Optimization-Assignment algorithm is integrable if and only if the volume-delay function is of either the BPR or some logarithmic form. [ABSTRACT FROM AUTHOR]

In this paper, we propose a probabilistic preemption scheme in cognitive radio networks that will simultaneously ensure the primary user (PU) packets' Quality of Service (QoS) and the secondary user (SU) packets' transmission continuity. This scheme differs from a complete preemption scheme or a complete non-preemption scheme in conventional cognitive radio networks in that a PU packet can interrupt an SU packet's transmission and preempt the channel with a certain probability that is termed the preemptive probability. In order to decrease the possible negative influence of SU packets on PU packets' QoS, we introduce an access threshold, i.e. a limit on the size of the SU packet buffer, which controls the access of the SU packets. As part of the mathematical analysis of the probabilistic preemption scheme, we establish a discrete-time priority queueing model and then characterize it by a two-dimensional Markov chain. Based on the steady-state solution of the system we give formulas for several performance measures of the network users. We also provide numerical results to highlight the influence of the preemptive probability and the access threshold on the system performance. Moreover, we also compare the system performance of the proposed probabilistic preemption scheme with the preemptive and non-preemptive schemes by using numerical results. Finally, we build an optimization framework by the help of properly chosen net benefit function to optimize the preemptive probability and the access threshold jointly. [ABSTRACT FROM AUTHOR]

This paper presents seven theorems which expand understanding of the theoretical structure of the Charnes­Cooper­Rhodes (CCR) model of Data Envelopment Analysis, especially with respect to slacks and the underlying structure of facets and faces. These theorems also serve as a basis for new algorithms which will provide optimal primal and dual solutions that satisfy the strong complementary slackness conditions (SCSC) for many (if not most) non-radially efficient DMUs; an improved procedure for identifying the set E of extreme efficient DMUs; and may, for many DEA domains, also settle in a single pass the existence or non-existence of input or output slacks in each of their DMUs. This paper also introduces the concept of a positive goal vector G, which is applied to characterize the set of all possible maximal optimal slack vectors. The appendix C presents an example which illustrates the need for a new concept, face regular, which focuses on the role of convexity in the intersections of radial efficient facets with the efficient frontier FR. The same example also illustrates flaws in the popular ‘sum of the slacks’ methodology. [ABSTRACT FROM AUTHOR]

The FAA has decided to install, operate, and maintain its own national microwave network called the Radio Communications Link (RCL) network. With this network and its capability to provide concentration points at any one of its microwave repeater locations, the FAA can substantially reduce Its leased line budget. This paper addresses the problem of determining the most cost-effective mix of point-to-point leased lines and ‘tail circuits’ to RCL concentrators for connecting communicating pairs of FAA facilities. The problem, formulated as an integer programming (IP) problem, is shown to be similar to the facility location problem. Also, like the facility problem, integral optimal solutions are frequently obtained. (The reason integral optimal solutions are frequently obtained for the facility location problem is not known.) Thus it is an example, more complex than the facility location problem, where such a phenomenon occurs. Also, the dimensionality of the problem precludes its being solved all in one piece. In this paper we formulate the problem, relate it to the facility location problem, and provide the partitioning and reduction techniques used to solve it in a reasonable amount of time. The partitioning and reduction techniques are independent of any particular formulation for this type of problem, and the solution methodology that would be applied to any subproblem. [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]

This paper studies the impact of service outsourcing under three supply chain power structures: manufacturer-Stackelberg, vertical-Nash and retailer-Stackelberg supply chains. We first investigate price and service decisions by comparing the integrated channel and the decentralized channel with service outsourcing. It is found that a lower retail price or a higher service level could occur in the decentralized channel with service outsourcing compared to those in the integrated channel, but they never occur simultaneously. Next, we examine the manufacturer's channel strategies, and demonstrate that service outsourcing can always help the manufacturer earn more profit from the decentralized channel than from the integrated channel in the manufacturer-Stackelberg and retailer-Stackelberg markets, as long as the retailer's service investment is sufficiently efficient. However, in the vertical-Nash supply chain, this occurs only when the manufacturer is inefficient and the retailer is efficient enough in service provision. Finally, comparisons of channel efficiency and numerical analysis are provided. [ABSTRACT FROM AUTHOR]

This paper presents the Local Search with SubProblem Exact Resolution (LSSPER) method based on large neighbourhood search for solving the resource-constrained project scheduling problem (RCPSP). At each step of the method, a subpart of the current solution is fixed while the other part defines a subproblem solved externally by a heuristic or an exact solution approach (using either constraint programming techniques or mathematical programming techniques). Hence, the method can be seen as a hybrid scheme. The key point of the method deals with the choice of the subproblem to be optimized. In this paper, we investigate the application of the method to the RCPSP. Several strategies for generating the subproblem are proposed. In order to evaluate these strategies, and, also, to compare the whole method with current state-of-the-art heuristics, extensive numerical experiments have been performed. The proposed method appears to be very efficient. [ABSTRACT FROM AUTHOR]

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem. [ABSTRACT FROM AUTHOR]

In this paper we introduce the concept of solving strategy for a linear semi-infinite programming problem, whose index set is arbitrary and whose coefficient functions have no special property at all. In particular, we consider two strategies which either approximately solve or exactly solve the approximating problems, respectively. Our principal aim is to establish a global framework to cope with different concepts of well-posedness spread out in the literature. Any concept of well posedness should entail different properties of these strategies, even in the case that we are not assuming the boundedness of the optimal set. In the paper we consider three desirable properties, leading to an exhaustive study of them in relation to both strategies. The more significant results are summarized in a table, which allows us to show the double goal of the paper. On the one hand, we characterize the main features of each strategy, in terms of certain stability properties (lower and upper semicontinuity) of the feasible set mapping, optimal value function and optimal set mapping. On the other hand, and associated with some cells of the table, we recognize different notions of Hadamard well-posedness. We also provide an application to the analysis of the Hadamard well-posedness for a linear semi-infinite formulation of the Lagrangian dual of a nonlinear programming problem. [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]

The usual Data Envelopment Analysis (DEA) model for measuring the relative efficiency assumes that all plants belong to distinct firms superior to them. For firms with more than one plant, Koopmans proposes a procedure for deriving the short-run production frontier for each firm. Modifying his idea, a DEA model is constructed in this paper for measuring the shortrun efficiency of each plant within a firm. Based on the theory of production economics that the long-run production frontier is an envelop super-imposed upon ail short-run production frontiers, another DEA model is constructed to measure the long-run efficiency of every plant. The long-run efficiency is always smaller than or equal to the short-run efficiency. Consequently, it is possible that an inefficient plant can only be improved in the long-run. With the models constructed in this paper, a decision-maker is able to distinguish between what can be achieved in the short-run and what in the long-run. To clarify the idea, an example of Taiwan forests is adopted for illustration. [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]

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]

In two-person games where each player has a finite number of pure strategies, the set of Nash equilibria is a Finite set when a certain nondegeneracy condition is satisfied. Recent investigations have shown that for n x n games, the cardinality of this finite set is bounded from above by a function ∅ (n) with 2n - 1 ≤ ∅(n) ≤ (27/4n/2 - 1, where n is the maximal number of pure strategies of any player. In the present paper, we generalize this result to a class of games which may not satisfy the nondegeneracy condition. The set of Nash equilibria may be infinite; it is shown that it consists of no more than ∅(n) arc-connected components. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new way to analyze bimatrix games. This new approach consists of considering the game as a bicriteria matrix game. The solution concepts behind this game are based on getting the probability to achieve some prespecified goals. We consider as a part of the solution, not only the payoff values, but also the probability to get them. In addition, to avoid the choice of only one goal, two different approaches are used. Firstly, sensitivity analysis of the solution set is carried out on the range of goals, secondly a partition of the goal space in a finite number of regions is presented. Some examples are included to illustrate the results in the paper. [ABSTRACT FROM AUTHOR]

We discuss in this paper several location problems for which it is an NP-hard problem to find an approximate solution. Given certain assumptions on the input distributions, we present polynomial algorithms that deliver a solution asymptotically close to the optimum with probability that is asymptotically one (the exact nature of this asymptotic convergence is described in the paper). In that sense the subproblems defined on the specified family of inputs are in fact easy. [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]

The purpose of this paper is to investigate the effect of individual arcs and nodes on the description of feasibility in an uncapacitated network. This is done by developing an iterative algorithm for finding all (necessary) Gale--Hoffman inequalities for the network. [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]

Nonlinear bilevel programming problems, of which the equilibrium network design problem is one, are extremely difficult to solve. Even if an optimum solution is obtained, there is no sure way of knowing whether the solution is the global optimum or not, due to the nonconvexity of the bilevel programming problem. This paper reviews and discusses recent developments in solution methodologies for nonlinear programming models of the equilibrium network design problem. In particular, it provides a primer for descent-type algorithms reported in the technical literature and proposes certain enhancements thereof. [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]

The bilevel programming problem (BLPP) is a two-person nonzero sum game in which play is sequential and cooperation is not permitted. In this paper, we examine a class of BLPPs where the leader controls a set of continuous and discrete variables and tries to minimize a convex nonlinear objective function. The follower's objective function is a convex quadratic in a continuous decision space. All constraints arc assumed to be linear. A branch and bound algorithm is developed that finds global optima. The main purpose of this paper is to identify efficient branching rules, and to determine the computational burden of the numeric procedures. Extensive test results are reported. We close by showing that it is not readily possible to extend the algorithm to the more general case involving integer follower variables. [ABSTRACT FROM AUTHOR]

The maximal covering location problem has been shown to be a useful tool in siting emergency services. In this paper we expand the model along two dimensions - workload capacities on facilities and the allocation or multiple levels of backup or prioritized service for all demand points. In emergency service facility location decisions such as ambulance sitting, when all of a facility's resources are needed to meet each call for service and the demand cannot be queued, the need for a backup unit may be required. This need is especially significant in areas of high demand. These areas also will often result in excessive workload for some facilities. Effective siting decisions, therefore, must address both the need for a backup response facility for each demand point and a reasonable limit on each facility's workload. In this paper, we develop a model which captures these concerns as well as present an efficient solution procedure using Lagrangian relaxation. Results of extensive computational experiments are presented to demonstrate the viability of the approach. [ABSTRACT FROM AUTHOR]

In an earlier paper, the authors formulated an acoustic antenna array design problem as a nonlinear program. Computation times for large problems (about 400 sensors) were in the range of 8 to 10 hours on a Vax 11/780. Most of this time was spent in computing the objective function and its gradient. This paper describes how these computations (and these only) were recoded to exploit the vector processing capabilities of a Cray 1-M computer. Run times are reduced to less than one minute. The results have implications for many nonlinear programs whose function evaluations are very time consuming. [ABSTRACT FROM AUTHOR]

In this paper we introduce a stochastic interdiction problem for median systems in which the operational state of the system's disrupted elements in the aftermath of the disruption is uncertain as it is based on the intensity of the disruption. We assume that a disruption disables a facility with a given probability and this probability depends on the intensity of the disruption. The objective of this problem is to identify which disruption scenario entails a maximum overall traveling distance in serving all customers. We show that the initial two stage stochastic formulation can be reformulated into a deterministic counterpart whose size is polynomial in the number of facilities and intensity levels. Then, our ensuing efforts to solve the problem efficiently focus on studying alternative deterministic formulations that allow the solution of realistic size instances of the model. We observe that the most efficient of the deterministic formulations provide great scalability with respect to variations in the input parameters and size of the instances solved. Finally, we analyze the robustness of the optimal solutions due to misestimations in the probability functions that relate disruption intensity levels with the probabilities of facility survivability. [ABSTRACT FROM AUTHOR]

The aim of the present paper is to study a one-point solution concept for bicooperative games. For these games introduced by Bilbao (Cooperative Games on Combinatorial Structures, ) , we define a one-point solution called the Shapley value, since this value can be interpreted in a similar way to the classical Shapley value for cooperative games. The main result of the paper is an axiomatic characterization of this value. [ABSTRACT FROM AUTHOR]

The article looks at the operational use of integer linear programming (ILP) models. It is apparent that ILP has reached a level of maturity that enables live management decision problems to be routinely solved. It notes that it has been achieved by an enormous increase in computing power, major improvements to the ILP solution codes and a greater understanding of the importance of a good formulation, and a finer knowledge of the mathematical structure of some common formulation constructs.

The paper presents a review of the basic concepts of the Logical Analysis of Data (LAD), along with a series of discrete optimization models associated to the implementation of various components of its general methodology, as well as an outline of applications of LAD to medical problems. The combinatorial optimization models described in the paper represent variations on the general theme of set covering, including some with nonlinear objective functions. The medical applications described include the development of diagnostic and prognostic systems in cancer research and pulmonology, risk assessment among cardiac patients, and the design of biomaterials. [ABSTRACT FROM AUTHOR]

In this paper, a new notion of exceptional family of elements (EFE) for a pair of functions involved in the implicit complementarity problem (ICP) is introduced. Based upon this notion and the Leray-Schauder Alternative, a general alternative is obtained which gives more general existence theorems for the implicit complementarity problem. Finally, via the techniques of continuous selections, these existence theorems are extended to the multi-valued implicit complementarity problems (MIPS). [ABSTRACT FROM AUTHOR]

In the sixties SOR has been the working horse for the numerical solution of elliptic boundary problems; classical results for chosing the relaxation parameter have been derived by D. Young and R.S. Varga. In the last fifteen years SOR has been examined for the computation of the stationary distribution of Markov chains. In the paper there are pointed out similarities and differences compared with the application of SOR for elliptic boundary problems. [ABSTRACT FROM AUTHOR]

This paper studies a class of infinite dimensional linear programming problems known as the general capacity problem. A relaxed cutting plane algorithm is proposed. A convergence proof together with some analysis of the results produced by the algorithm are given. A numerical example is also included to illustrate the computational procedure. [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]

In this paper, we give a generalized Abadie constraint qualification (CQ) for a class of nonsmooth vector-valued optimization. Under this CQ, we obtained the Kuhn-Tucker-type optimality condition where the multipliers associated with the objective functions are all positive. [ABSTRACT FROM AUTHOR]

Heuristic search methods have been increasingly applied to combinatorial optimization problems. While a specific problem defines a unique search space, different ‘landscapes’ are created by the different heuristic search operators used to search it. In this paper, a simple example will be used to illustrate the fact that the landscape structure changes with the operator; indeed, it often depends even on the way the operators are applied. Recent attention has focused on trying to better understand the nature of these ‘landscapes’. Recent work by Boese et al. [2] has shown that instances of the TSP are often characterised by a ‘big valley’ structure in the case of a 2-opt exchange operator, and a particular distance metric. In this paper, their work is developed by investigating the question of how landscapes change under different search operators in the case of the n/m/P/Cmax flowshop problem. Six operators and four distance metrics are defined, and the resulting landscapes examined. The work is further extended by proposing a statistical randomisation test to provide a numerical assessment of the landscape. Other conclusions relate to the existence of ultra-metricity, and to the usefulness or otherwise of hybrid neighbourhood operators. [ABSTRACT FROM AUTHOR]

We consider the problem of locating a single facility on a network in the presence of r ≥ 2 median-type objectives, represented by r sets of edge weights (or lengths) corresponding to each of the objectives. When r = 1, then one gets the classical 1-median problem where only the vertices need to be considered for determining the optimal location (Hakimi [1]). The paper examines the case when r ≥ 2 and provides a method to determine the non-dominated set of points for locating the facility. [ABSTRACT FROM AUTHOR]

The Capacitated Minimal Spanning Tree Problem (CMSTP) is to find a minimal spanning tree with an additional cardinality constraint on the size of the subtrees off of a given root node. This problem is closely related to the design of centralized networks where one wants to link, with minimum cost, several terminals to a given root node (typically, a concentrator or a computer center). In this paper, we present a new extended and compact formulation for the CMSTP. This formulation is a ‘hop-indexed’ single-commodity flow model and generalizes a well-known single-commodity flow model. We introduce a new set of valid inequalities, denoted by ‘hop ordering’ inequalities, which are not redundant for the LP relaxation of the new formulation. We present a new cutting plane method for the CMSTP with the new formulation as the initial model and using constraint generation for adding ‘hop-ordering’ constraints and generalized subtour elimination constraints to the current LP model. We present computational results from a set of tests with 40 and 80 nodes which compare our lower bounds with the bounds given by other known methods. The main contribution of our proposed method is to considerably close previously known gaps for tests which have been classified as hard ones, namely tightly capacitated tests with the root in the comer of the grid of points. [ABSTRACT FROM AUTHOR]

In this paper, the uncapacitated facility location problem is considered, A tabu search algorithm for solving this problem is proposed. The algorithm is tested on some standard test problems taken from literature and its performance is compared with the known optimal solutions. Computational results show that the proposed algorithm produces optimal solutions for all test problems, and that it is very efficient in terms of time compared to existing algorithms in the literature. [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]

The paper reviews the role of sensors as a variable depicting information in a stochastic program. Through examples, and with mathematical analysis of random measures, it is shown how policy variables affect the sensors in a given problem. Sensors are amenable to mathematical derivations. It is shown how the trade-off between the gain from introducing new information into the problem, and the cost of that action, can be addressed. Suggestions for further investigation are offered. [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]

The paper presents an algorithm for determining non-dominated basic solutions of the linear programming problem with two objectives in which the coefficients depend in a linear way on a parameter, and a modified version of an algorithm for the non-parametric case. [ABSTRACT FROM AUTHOR]

The concept of a strict extended partial order (SEPO) has turned out to be very useful in explaining (resp. rationalizing) non-binary choice functions. The present paper provides a general account of the concept of extended binary relations, i.e. relations between subsets and elements of a given universal set of alternatives. In particular, we define the concept of a weak extended partial order (WEPO) and show how it can be used in order to represent rankings of Opportunity sets that display a ‘preference for opportunities’. We also clarify the relationship between SEPOs and WEPOs, which involves a non-trivial condition, called ‘strict properness’. Several characterizations of strict (and weak) properness are provided, based on which we argue for properness as an appropriate condition demarcating ‘choice based’ preference. [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]

This paper is a survey of genetic algorithms for the traveling salesman problem. Genetic algorithms are randomized search techniques that simulate some of the processes observed in natural evolution. In this paper, a simple genetic algorithm is introduced, and various extensions are presented to solve the traveling salesman problem. Computational results are also reported for both random and classical problems taken from the operations research literature. [ABSTRACT FROM AUTHOR]