Implementing pure adaptive search for global optimization using Markov chain sampling

The Pure Adaptive Search (PAS) algorithm for global optimization yields a sequence of points, each of which is uniformly distributed in the level set corresponding to its predecessor. This algorithm has the highly desirable property of solving a large class of global optimization problems using a number of iterations that increases at most linearly in the dimension of the problem. Unfortunately, PAS has remained of mostly theoretical interest due to the difficulty of generating, in each iteration, a point uniformly distributed in the improving feasible region. In this article, we derive a coupling equivalence between generating an approximately uniformly distributed point using Markov chain sampling, and generating an exactly uniformly distributed point with a certain probability. This result is used to characterize the complexity of a PAS-implementation as a function of (a) the number of iterations required by PAS to achieve a certain solution quality guarantee, and (b) the complexity of the sampling algorithm used. As an application, we use this equivalence to show that PAS, using the so-called Random ball walk Markov chain sampling method for generating nearly uniform points in a convex region, can be used to solve most convex programming problems in polynomial time.     

Simulated annealing for constrained global optimization

Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.This material is based on work supported by a NATO Collaborative Research Grant, no. 0119/89.     

Supply capacity acquisition and allocation with uncertain customer demands

We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.     

Target market selection and marketing effort under uncertainty: The selective newsvendor

We consider a firm that markets, procures, and delivers a good with a single selling season in a number of different markets. The price for the good is market-dependent, and each market has an associated demand distribution, with parameters that depend on the amount of marketing effort applied. Given long procurement lead-times, the firm must decide which markets it will serve prior to procuring the good. We develop a profit maximizing model to address the firm’s integrated market selection, marketing effort, and procurement decisions. The model implicitly accounts for inventory pooling across markets, which reduces safety stock costs but increases model complexity. The resulting model is a nonlinear integer optimization problem, for which we develop specialized solution methods. For the case in which budget constraints exist, we provide a novel solution approach that uses a tailored branch-and-bound algorithm. Our approach solves a broad range of 3000 test instances in an average of less than 2 seconds, significantly outperforming a leading commercial global optimization solver.     

Allocating procurement to capacitated suppliers with concave quantity discounts

We consider a procurement problem where suppliers offer concave quantity discounts. The resulting continuous knapsack problem involves the minimization of a sum of separable concave functions. We identify polynomially solvable special cases of this NP-hard problem, and provide a fully polynomial-time approximation scheme for the general problem.     

Improving Hit-and-Run for global optimization

Improving Hit-and-Run is a random search algorithm for global optimization that at each iteration generates a candidate point for improvement that is uniformly distributed along a randomly chosen direction within the feasible region. The candidate point is accepted as the next iterate if it offers an improvement over the current iterate. We show that for positive definite quadratic programs, the expected number of function evaluations needed to arbitrarily well approximate the optimal solution is at most O(n^5/2) wheren is the dimension of the problem. Improving Hit-and-Run when applied to global optimization problems can therefore be expected to converge polynomially fast as it approaches the global optimum.Paper presented at the II. IIASA-Workshop on Global Optimization, December 9–14, 1990, Sopron (Hungary).     

Designing two-echelon supply networks

A modern distribution network design model needs to deal with the trade-offs between a variety of factors, including (1) location and associated (fixed) operating cost of distribution centers (DCs), (2) total transportation costs, and (3) storage holding and replenishment costs at DCs and retail outlets. In addition, network design models should account for factors such as (4) stockouts, by setting appropriate levels of safety stocks, or (5) capacity concerns, which may affect operating costs in the form of congestion costs. The difficulty of making such trade-offs is compounded by the fact that even finding the optimal two-echelon inventory policy in a fixed and uncapacitated distribution network is already a hard problem. In this paper, we propose a generic modeling framework to address these issues that continues and extends a recent stream of research aimed at integrating insights from modern inventory theory into the supply chain network design domain. Our approach is flexible and general enough to incorporate a variety of important side constraints into the problem.     

On solving the multi-period single-sourcing problem under uncertainty

We present a framework for solving the strategic problem of assigning retailers to facilities in a multi-period single-sourcing product environment under uncertainty in the demand from the retailers and the cost of production, inventory holding, backlogging and distribution of the product. By considering a splitting variable mathematical representation of the Deterministic Equivalent Model, we specialize the so-called Branch-and-Fix Coordination algorithmic framework. It exploits the structure of the model and, specifically, the non-anticipativity constraints for the assignment variables. The algorithm uses the Twin Node Family (TNF) concept. Our procedure is specifically designed for coordinating the selection of the branching TNF and the branching S3 set, such that the non-anticipativity constraints are satisfied. Some computational experience is reported. D. Romero Morales: The work of this author was supported in part by the National Science Foundation under Grant No. DMI-0355533 The work of the first three authors has been partially supported by the grants TIC2003-05982-C05-05 and SEC2002-00112 from MCyT, Spain     

Optimising Noisy Objective Functions

This discussion paper considers the use of stochastic algorithms for solving global optimisation problems in which function evaluations are subject to random noise. An idea is outlined for discussion at the forthcoming Stochastic Global Optimisation 2001 workshop in Hanmer in June; we propose that a noisy version of pure random search be studied.