Finding multiple solutions to general integer linear programs

Integer linear programming (ILP) problems occur frequently in many applications. In practice, alternative optima are useful since they allow the decision maker to choose from multiple solutions without experiencing any deterioration in the objective function. This study proposes a general integer cut to exclude the previous solution and presents an algorithm to identify all alternative optimal solutions of an ILP problem. Numerical examples in real applications are presented to demonstrate the usefulness of the proposed method.     

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided.     

Numerical comparison of network design algorithms for regionalized variables

The technique of kriging has a fundamental importance in applied sciences such as hydrology, meteorology, soil sciences, and mining. By using kriging, not only can the estimates of the natural phenomena be determined, but the estimation variances reflect the uncertainty of the estimation process. The sampling points for kriging should be selected to minimize the uncertainty, that is, to minimize the estimation variance of the kriging estimator. In this paper four algorithms for optimal observation network design are compared. Two of the algorithms give global optima, while the others give only suboptimal solutions. The computer time required for using the heuristic algorithms, giving only suboptimal solutions, is much less than that of the optimizing procedures. It is also shown on the basis of our experiments that the suboptimal solutions are either optimal or very close to optimal; consequently on the basis of our simulated examples, the heuristic algorithms are highly recommended for practical applications.     

GEM: A novel evolutionary optimization method with improved neighborhood search

A new optimization technique called Grenade Explosion Method (GEM) is introduced and its underlying ideas, including the concept of Optimal Search Direction (OSD), are elaborated. The applicability and efficiency of the technique is demonstrated using standard benchmark functions. Comparison of the results with those of other, widely-used, evolutionary algorithms shows that the proposed algorithm outperforms its rivals both in the success rate and rate of convergence. The method is also shown to be capable of finding most, or even all, optima of functions having multiple global optima. Moreover, it is shown that the performance of GEM is invariant against shifting and scaling of the search space and objective function.     

Finding optimal hyperpaths in large transit networks with realistic headway distributions

This paper implements and tests a label-setting algorithm for finding optimal hyperpaths in large transit networks with realistic headway distributions. It has been commonly assumed in the literature that headway is exponentially distributed. To validate this assumption, the empirical headway data archived by Chicago Transit Agency are fitted into various probabilistic distributions. The results suggest that the headway data fit much better with Loglogistic, Gamma and Erlang distributions than with the exponential distribution. Accordingly, we propose to model headway using the Erlang distribution in the proposed algorithm, because it best balances realism and tractability. When headway is not exponentially distributed, finding optimal hyperpaths may require enumerating all possible line combinations at each transfer stop, which is tractable only for a small number of alternative lines. To overcome this difficulty, a greedy method is implemented as a heuristic and compared to the brute-force enumeration method. The proposed algorithm is tested on a large scale CTA bus network that has over 10,000 stops. The results show that (1) the assumption of exponentially distributed headway may lead to sub-optimal route choices and (2) the heuristic greedy method provides near optimal solutions in all tested cases.     

A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains

In this paper, we investigate the lot and delivery scheduling problem in a simple supply chain where a single supplier produces multiple components on a flexible flow line (FFL) and delivers them directly to an assembly facility (AF). It is assumed that all of parameters such as demand rates for the components are deterministic and constant over a finite planning horizon. The main objective is to find a lot and delivery schedule that would minimize the average of holding, setup, and transportation costs per unit time for the supply chain. We develop a new mixed integer nonlinear program (MINLP) and an optimal enumeration method to solve the problem. Due to difficulty of obtaining the optimal solution in medium and large-scaled problems, a hybrid genetic algorithm (HGA) is also developed. The proposed HGA incorporates a neighborhood search (NS) into a basic genetic algorithm that enables the algorithm to perform genetic search over the subspace of local optima. The two proposed solution methods are compared on randomly generated problems, and computational results show that the performance of HGA is very promising because it is able to find an optimal or near-optimal solution for majority of the test problems.     

An inverse problem for the acoustics equations: A multilevel adaptive algorithm

A numerical solution to an inverse problem for the acoustic equations using an optimization method for a stratified medium is presented. With the distribution of an acoustic wave field on the medium’s surface, the 1D distributions of medium’s density, as well as the velocity and absorption coefficient of the acoustic wave, are determined. Absorption in a Voigt body model is considered. The conjugate gradients and the Newton method are used for minimization. To increase the efficiency of the numerical method, a multilevel adaptive algorithm is proposed. The algorithm is based on a division of the whole procedure of solving the inverse problem into a series of consecutive levels. Each level is characterized by the number of parameters to be determined at the level. In moving from one level to another, the number of parameters changes adaptively according to the functional minimized and the convergence rate. The minimization parameters are chosen as illustrated by results of solving the inverse problem in a spectral domain, where the desired quantities are presented as Chebyshev polynomial series and minimization is carried out with respect to the coefficients of these series. The method is compared in efficiency with a nonadaptive method. The optimal parameters of the multilevel method are chosen. It is shown that the multilevel algorithm offers several advantages over the one without partitioning into levels. The algorithm produces primarily a more accurate solution to the inverse problem.     

A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity among second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such a scaled norm, the obtained method behaves as a line-search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second-order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line-search algorithm. The good potential of the obtained algorithms is shown on a set of large-scale optimization problems.     

Calculation of an optimal region of operation for dual response systems fitted from experimental data

While there is abundant literature on Response Surface Methodology (RSM) about how to seek optimal operating settings for Dual Response Systems (DRS) using various optimisation approaches, the inherent sampling variability of the fitted responses has typically been neglected. That is, the single global optimum settings for the fitted response represent the expected value of the fitted functions since the true response systems are, in general, noisy and unknown in many engineering and scientific experiments. This paper presents an approach for DRS based on Monte Carlo simulation of the system under study. For each simulated set of responses, a new global optimisation algorithm for DRS is utilised to compute the global optimal factor settings. Repetition of this process constructs an optimal region in the control factor space that provides more useful information to a process engineer than a single optimal—expected—solution. It is shown how the optimal region can be used as an indicator of how trustworthy this single solution is, and as a set of alternative solutions from where an engineer can select other process settings in case limitations not considered by the DRS model prevent the adoption of the single expected optimum. Application to Taguchi's Robust Parameter Design problems illustrates the proposed method.     

Generalized Surrogate Problem Methodology for Online Stochastic Discrete Optimization

We consider stochastic discrete optimization problems where the decision variables are nonnegative integers and propose a generalized surrogate problem methodology that modifies and extends previous work in Ref. 1. Our approach is based on an online control scheme which transforms the problem into a surrogate continuous optimization problem and proceeds to solve the latter using standard gradient-based approaches while simultaneously updating both the actual and surrogate system states. In contrast to Ref. 1, the proposed methodology applies to arbitrary constraint sets. It is shown that, under certain conditions, the solution of the original problem is recovered from the optimal surrogate state. Applications of this approach include solutions to multicommodity resource allocation problems; in these problems, exploiting the convergence speed of the method, one can overcome the obstacle posed by the presence of local optima.     

Subset simulation for unconstrained global optimization

Global optimization problem is known to be challenging, for which it is difficult to have an algorithm that performs uniformly efficient for all problems. Stochastic optimization algorithms are suitable for these problems, which are inspired by natural phenomena, such as metal annealing, social behavior of animals, etc. In this paper, subset simulation, which is originally a reliability analysis method, is modified to solve unconstrained global optimization problems by introducing artificial probabilistic assumptions on design variables. The basic idea is to deal with the global optimization problems in the context of reliability analysis. By randomizing the design variables, the objective function maps the multi-dimensional design variable space into a one-dimensional random variable. Although the objective function itself may have many local optima, its cumulative distribution function has only one maximum at its tail, as it is a monotonic, non-decreasing, right-continuous function. It turns out that the searching process of optimal solution(s) of a global optimization problem is equivalent to exploring the process of the tail distribution in a reliability problem. The proposed algorithm is illustrated by two groups of benchmark test problems. The first group is carried out for parametric study and the second group focuses on the statistical performance.     

Classical differential geometry solution of the brachistochrone tunnel problem

The Frenet-Serret equations of classical differential geometry are used to describe the quickest descent tunneling path problem. The optimal tunnel is shown to have a constant turn rate with zero torsion and is equivalent to Edelbaum's hypocycloid solution. The solutions are obtained using the maximum principle and singular arc conditions. The optimal curvature is a first-order singular arc and the optimal torsion is a second-order singular arc. Our treatment includes both the normal and the abnormal optimal control problems. Our problem is abnormal for the case where the final speed is zero. Analytical solutions for the optimal time histories are derived for all states and all adjoint states. One of Leitmann's sufficiency field theorems is used to establish optimality of the solutions.     

A Comparison of Global Optimization Methods for the Design of a High-speed Civil Transport

The conceptual design of aircraft often entails a large number of nonlinear constraints that result in a nonconvex feasible design space and multiple local optima. The design of the high-speed civil transport (HSCT) is used as an example of a highly complex conceptual design with 26 design variables and 68 constraints. This paper compares three global optimization techniques on the HSCT problem and two test problems containing thousands of local optima and noise: multistart local optimizations using either sequential quadratic programming (SQP) as implemented in the design optimization tools (DOT) program or Snyman's dynamic search method, and a modified form of Jones' DIRECT global optimization algorithm. SQP is a local optimizer, while Snyman's algorithm is capable of moving through shallow local minima. The modified DIRECT algorithm is a global search method based on Lipschitzian optimization that locates small promising regions of design space and then uses a local optimizer to converge to the optimum. DOT and the dynamic search algorithms proved to be superior for finding a single optimum masked by noise of trigonometric form. The modified DIRECT algorithm was found to be better for locating the global optimum of functions with many widely separated true local optima.     

Enhanced speciation in particle swarm optimization for multi-modal problems

In this paper, we present a novel multi-modal optimization algorithm for finding multiple local optima in objective function surfaces. We build from Species-based particle swarm optimization (SPSO) by using deterministic sampling to generate new particles during the optimization process, by implementing proximity-based speciation coupled with speciation of isolated particles, and by including “turbulence regions” around already found solutions to prevent unnecessary function evaluations. Instead of using error threshold values, the new algorithm uses the particle’s experience, geometric mean, and “exclusion factor” to detect local optima and stop the algorithm. The performance of each extension is assessed with leave-it-out tests, and the results are discussed. We use the new algorithm called Isolated-Speciation-based particle swarm optimization (ISPSO) and a benchmark algorithm called Niche particle swarm optimization (NichePSO) to solve a six-dimensional rainfall characterization problem for 192 rain gages across the United States. We show why it is important to find multiple local optima for solving this real-world complex problem by discussing its high multi-modality. Solutions found by both algorithms are compared, and we conclude that ISPSO is more reliable than NichePSO at finding optima with a significantly lower objective function value.     

Feature extraction algorithms for constrained global optimization II. Batch process scheduling application

The feature extraction algorithms developed in part I of this series are applied to solve nonconvex mixed integer nonlinear programming problems which arise in the optimal scheduling of multipurpose chemical plants. A general formulation of the multipurpose plant scheduling problem is developed which considers the allocation of plant equipment and secondary, limited resources to recipe operations so as to satisfy given production requirements while minimizing cost. Results obtained with a test example involving 135 binary and 922 continuous variables show that the successive refinement strategy is effective in identifying dominant regions of the solution space. Furthermore it is shown that multiple moment based characterization methods are superior to the interval analysis method reported in the literature. Trials using a second, larger nonlinear test problem involving 356 binary and 2402 continuous variables demonstrate that the focused successive refinement strategy is more efficient than a constant resolution strategy which employs genetic algorithm constructions. Although the conventional genetic algorithm can be significantly improved by introducing a heuristic mutation strategy which increases the likelihood of constant feasibility, the successive refinement strategy remains dominant. These studies demonstrate that the feature extraction strategy employing successive refinements and relatively low order moment based region characterization methods, offers an effective approach to solving an important class of large scale MINLP problems with multiple local optima.     

Dynamic bidding strategies in search-based advertising

Search-based advertising allows the advertisers to run special campaigns targeted to different groups of potential consumers at low costs. Google, Yahoo and Microsoft advertising programs allow the advertisers to bid for an ad position on the result page of a user’s query when the user searches for a keyword that the advertiser relates to its products or services. The expected revenue generated by the ad depends on the ad position, and the ad positions of the advertisers are concurrently determined after an instantaneous auction based on the bids of the advertisers. The advertisers are charged only when their ads are clicked by the users. To avoid excessive ad expenditures due to sudden surges in the keyword-search activities, each advertiser reserves a fixed finite daily budget, and the ads are not shown in the remainder of the day when the budget is depleted. Arrival times of keyword-search instances, ad positions, ad selections, and sales generated by the ads are random. Therefore, an advertiser faces a dynamic stochastic total net revenue optimization problem subject to a strict budget constraint. Here we formulate and solve this problem using dynamic programming. We show that there is always an optimal dynamic bidding policy. We describe an iterative numerical approximation algorithm that uniformly converges to the optimal solution at an exponential rate of the number of iterations. We illustrate the algorithm on numerical examples. Because dynamic programing calculations of the optimal bidding policies are computationally demanding, we also propose both static and dynamic alternative bidding policies. We numerically compare the performances of optimal and alternative bidding policies by systematically changing each input parameter. The relative percentage total net revenue losses of the alternative bidding policies increases with the budget loading, but were never more than 3.5 % of maximum expected total net revenue. The best alternative to the optimal bidding policy turned out to be a static greedy bidding policy. Finally, statistical estimation of the model parameters is visited.     

The optimal control of just-in-time-based production and distribution systems and performance comparisons with optimized pull systems

In just-in-time (JIT) production systems, there is both input stock in the form of parts and output stock in the form of product at each stage. These activities are controlled by production-ordering and withdrawal kanbans. This paper discusses a discrete-time optimal control problem in a multistage JIT-based production and distribution system with stochastic demand and capacity, developed to minimize the expected total cost per unit of time. The problem can be formulated as an undiscounted Markov decision process (UMDP); however, the curse of dimensionality makes it very difficult to find an exact solution. The author proposes a new neuro-dynamic programming (NDP) algorithm, the simulation-based modified policy iteration method (SBMPIM), to solve the optimal control problem. The existing NDP algorithms and SBMPIM are numerically compared with a traditional UMDP algorithm for a single-stage JIT production system. It is shown that all NDP algorithms except the SBMPIM fail to converge to an optimal control.Additionally, a new algorithm for finding the optimal parameters of pull systems is proposed. Numerical comparisons between near-optimal controls computed using the SBMPIM and optimized pull systems are conducted for three-stage JIT-based production and distribution systems. UMDPs with 42 million states are solved using the SBMPIM. The pull systems discussed are the kanban, base stock, CONWIP, hybrid and extended kanban.     

A framework for finding robust optimal solutions over time

Dynamic optimization problems (DOPs) are those whose specifications change over time, resulting in changing optima. Most research on DOPs has so far concentrated on tracking the moving optima (TMO) as closely as possible. In practice, however, it will be very costly, if not impossible to keep changing the design when the environment changes. To address DOPs more practically, we recently introduced a conceptually new problem formulation, which is referred to as robust optimization over time (ROOT). Based on ROOT, an optimization algorithm aims to find an acceptable (optimal or sub-optimal) solution that changes slowly over time, rather than the moving global optimum. In this paper, we propose a generic framework for solving DOPs using the ROOT concept, which searches for optimal solutions that are robust over time by means of local fitness approximation and prediction. Empirical investigations comparing a few representative TMO approaches with an instantiation of the proposed framework are conducted on a number of test problems to demonstrate the advantage of the proposed framework in the ROOT context.     

Asymptotic Solution of a Singularly Perturbed Linear-Quadratic Problem in Critical Case with Cheap Control

Using the direct scheme method, we construct an asymptotic expansion for the solution of a singularly perturbed optimal problem in critical case with cheap control and two fixed end-points. The asymptotic solution contains the outer series and two boundary-layer series in the vicinities of the two end-points. The error estimates for state and control variables and the functional are obtained. It is shown that the value of minimized functional does not increase when a higher-order approximation to the optimal control is used. An illustrative example is given.     

Stochastic Nelder–Mead simplex method – A new globally convergent direct search method for simulation optimization

Nelder–Mead simplex method (NM), originally developed in deterministic optimization, is an efficient direct search method that optimizes the response function merely by comparing function values. While successful in deterministic settings, the application of NM to simulation optimization suffers from two problems: (1) It lacks an effective sample size scheme for controlling noise; consequently the algorithm can be misled to the wrong direction because of noise, and (2) it is a heuristic algorithm; the quality of estimated optimal solution cannot be quantified. We propose a new variant, called Stochastic Nelder–Mead simplex method (SNM), that employs an effective sample size scheme and a specially-designed global and local search framework to address these two problems. Without the use of gradient information, SNM can handle problems where the response functions are nonsmooth or gradient does not exist. This is complementary to the existing gradient-based approaches. We prove that SNM can converge to the true global optima with probability one. An extensive numerical study also shows that the performance SNM is promising and is worthy of further investigation.