Sensitivity analysis of a greedy heuristic for knapsack problems

In this paper, we carry out parametric analysis as well as a tolerance limit based sensitivity analysis of a greedy heuristic for two knapsack problems—the 0–1 knapsack problem and the subset sum problem. We carry out the parametric analysis based on all problem parameters. In the tolerance limit based approach, we use a definition of the sensitivity analysis problem that is polynomial for polynomial heuristics. One of the interesting and counterintuitive results described in this paper is that the tolerance limits obtained from the heuristic sensitivity analysis cannot be used as bounds for the tolerance limits of the sensitivity analysis of optimal solutions in most cases.     

Development of the parametric tolerance modeling and optimization schemes and cost-effective solutions

Most of previous research on tolerance optimization seeks the optimal tolerance allocation with process parameters such as fixed process mean and variance. This research, however, differs from the previous studies in two ways. First, an integrated optimization scheme is proposed to determine both the optimal settings of those process parameters and the optimal tolerance simultaneously which is called a parametric tolerance optimization problem in this paper. Second, most tolerance optimization models require rigorous optimization processes using numerical methods, since closed-form solutions are rarely found. This paper shows how the Lambert W function, which is often used in physics, can be applied efficiently to this parametric tolerance optimization problem. By using the Lambert W function, one can express the optimal solutions to the parametric tolerance optimization problem in a closed-form without resorting to numerical methods. For verification purposes, numerical examples for three cases are conducted and sensitivity analyses are performed.     

Derivatives of the Efficient Point Multifunction in Parametric Vector Optimization Problems

In this paper, we deal with the sensitivity analysis in vector optimization. More specifically, formulae for inner and outer evaluating the S-derivative of the efficient point multifunction in parametric vector optimization problems are established. These estimating formulae are presented via the set of efficient/weakly efficient points of the S-derivative of the original multifunction, a composite multifunction of the objective function and the constraint mapping. The elaboration of the formulae in vector optimization problems, having multifunction constraints and semiinfinite constraints, is also undertaken. Furthermore, examples are provided for analyzing and illustrating the obtained results.     

Parametric scaling of mathematical models

Parametric scaling, the process of extrapolation of a modelling result to new parametric conditions, is often required in model optimization, and can be important if the effects of parametric uncertainty on model predictions are to be quantified. Knowledge of the functional relationship between the model solution (y) and the system parameters (α) may also provide insight into the physical system underlying the model. This paper examines strategies for parametric scaling, assuming that only the nominal model solution y(α) and the associated parametric sensitivity coefficients (?y/?α, ?²y/?α², etc.) are known. The truncated Taylor series is shown to be a poor choice for parametric scaling, when y has known bounds. Alternate formulae are proposed which ‘build-in’ the constraints on y, thus expanding the parametric region in which the extrapolation may be valid. In the case where y has a temporal as well as a parametric dependence, the extrapolation may be further improved by removing from the Taylor series coefficients the ‘secular’ components, which refer to changes in the time scale of y(t), not to changes in y as a function of α.     

A novel differential evolution algorithm for binary optimization

Differential evolution (DE) is one of the most powerful stochastic search methods which was introduced originally for continuous optimization. In this sense, it is of low efficiency in dealing with discrete problems. In this paper we try to cover this deficiency through introducing a new version of DE algorithm, particularly designed for binary optimization. It is well-known that in its original form, DE maintains a differential mutation, a crossover and a selection operator for optimizing non-linear continuous functions. Therefore, developing the new binary version of DE algorithm, calls for introducing operators having the major characteristics of the original ones and being respondent to the structure of binary optimization problems. Using a measure of dissimilarity between binary vectors, we propose a differential mutation operator that works in continuous space while its consequence is used in the construction of the complete solution in binary space. This approach essentially enables us to utilize the structural knowledge of the problem through heuristic procedures, during the construction of the new solution. To verify effectiveness of our approach, we choose the uncapacitated facility location problem (UFLP)—one of the most frequently encountered binary optimization problems—and solve benchmark suites collected from OR-Library. Extensive computational experiments are carried out to find out the behavior of our algorithm under various setting of the control parameters and also to measure how well it competes with other state of the art binary optimization algorithms. Beside UFLP, we also investigate the suitably of our approach for optimizing numerical functions. We select a number of well-known functions on which we compare the performance of our approach with different binary optimization algorithms. Results testify that our approach is very efficient and can be regarded as a promising method for solving wide class of binary optimization problems.     

Worst-case performance of Wong's Steiner tree heuristic

A study of the worst-case performance of Wong's heuristic for the Steiner problem in directed networks (SPDN) is presented in this paper.SPDN is a classic combinatorial optimization problem having the status of a very difficult problem (NP-hard problem) and it is known as an optimization model for a broad class of problems in networks. Several exact and heuristic approaches have been designed for SPDN in the last twenty five years.Some papers analyze theoretical and experimental behavior of heuristics for SPDN, specially for undirected networks, but none of these has studied the worst-case performance of Wong's heuristic. In this paper, we find a lower bound for that performance and show that this bound is consistent with comparable results in the literature on SPDN and its undirected version.     

Bi-directional evolutionary topology optimization of geometrically nonlinear continuum structures with stress constraints

This paper proposes a design method to maximize the stiffness of geometrically nonlinear continuum structures subject to volume fraction and maximum von Mises stress constraints. An extended bi-directional evolutionary structural optimization (BESO) method is adopted in this paper. BESO method based on discrete variables can effectively avoid the well-known singularity problem in density-based methods with low density elements. The maximum von Mises stress is approximated by the p-norm global stress. By introducing one Lagrange multiplier, the objective of the traditional stiffness design is augmented with p-norm stress. The stiffness and p-norm stress are considered simultaneously by the Lagrange multiplier method. A heuristic method for determining the Lagrange multiplier is proposed in order to effectively constrain the structural maximum von Mises stress. The sensitivity information for designing variable updates is derived in detail by adjoint method. As for the highly nonlinear stress behavior, the updated scheme takes advantages from two filters respectively of the sensitivity and topology variables to improve convergence. Moreover, the filtered sensitivity numbers are combined with their historical sensitivity information to further stabilize the optimization process. The effectiveness of the proposed method is demonstrated by several benchmark design problems.     

Fine-tuning a parametric Clarke and Wright heuristic by means of EAGH (empirically adjusted greedy heuristics)

Alt?nel and Öncan (2005) (A new enhancement of the Clarke and Wrightsavings heuristic for the capacitated vehicle routing problem) proposed aparametric Clarke and Wright heuristic to solve the capacitated vehicle routingproblem (CVRP). The performance of this parametric heuristic is sensitive tofine-tuning. Antinel and Öncan used an enumerative parameter-settingapproach and improved on the results obtained with the original Clarke andWright heuristic, but their approach requires much more computation time tosolve an instance. Battarra et al (2008) (Tuning a parametricClarke–Wright heuristic through a genetic algorithm) proposed a geneticalgorithm to set the parameter values. They succeeded in reducing the timeneeded to solve an instance, but the quality of the solution was slightly worse.In this paper, we propose to use the EAGH (empirically adjusted greedyheuristics) procedure to set the parameter values. A computational experimentshows the efficiency of EAGH; in an even shorter time, we improve on the bestresults obtained with any parametric Clarke and Wright heuristic method proposedin the literature.     

Global optimization based on novel heuristics,low-discrepancy sequences and genetic algorithms

In this paper a new heuristic hybrid technique for bound-constrained global optimization is proposed. We developed iterative algorithm called GLP_τS that uses genetic algorithms, LP_τ low-discrepancy sequences of points and heuristic rules to find regions of attraction when searching a global minimum of an objective function. Subsequently Nelder–Mead Simplex local search technique is used to refine the solution. The combination of the three techniques (Genetic algorithms, LP_τO Low-discrepancy search and Simplex search) provides a powerful hybrid heuristic optimization method which is tested on a number of benchmark multimodal functions with 10–150 dimensions, and the method properties – applicability, convergence, consistency and stability are discussed in detail.     

PSOHS: an efficient two-stage approach for data clustering

Cluster analysis is an important task in data mining and refers to group a set of objects such that the similarities among objects within the same group are maximal while similarities among objects from different groups are minimal. The particle swarm optimization algorithm (PSO) is one of the famous metaheuristic optimization algorithms, which has been successfully applied to solve the clustering problem. However, it has two major shortcomings. The PSO algorithm converges rapidly during the initial stages of the search process, but near global optimum, the convergence speed will become very slow. Moreover, it may get trapped in local optimum if the global best and local best values are equal to the particle’s position over a certain number of iterations. In this paper we hybridized the PSO with a heuristic search algorithm to overcome the shortcomings of the PSO algorithm. In the proposed algorithm, called PSOHS, the particle swarm optimization is used to produce an initial solution to the clustering problem and then a heuristic search algorithm is applied to improve the quality of this solution by searching around it. The superiority of the proposed PSOHS clustering method, as compared to other popular methods for clustering problem is established for seven benchmark and real datasets including Iris, Wine, Crude Oil, Cancer, CMC, Glass and Vowel.     

Optimizing fuzzy p-hub center problem with generalized value-at-risk criterion

In this study, we reduce the uncertainty embedded in secondary possibility distribution of a type-2 fuzzy variable by fuzzy integral, and apply the proposed reduction method to p-hub center problem, which is a nonlinear optimization problem due to the existence of integer decision variables. In order to optimize p-hub center problem, this paper develops a robust optimization method to describe travel times by employing parametric possibility distributions. We first derive the parametric possibility distributions of reduced fuzzy variables. After that, we apply the reduction methods to p-hub center problem and develop a new generalized value-at-risk (VaR) p-hub center problem, in which the travel times are characterized by parametric possibility distributions. Under mild assumptions, we turn the original fuzzy p-hub center problem into its equivalent parametric mixed-integer programming problems. So, we can solve the equivalent parametric mixed-integer programming problems by general-purpose optimization software. Finally, some numerical experiments are performed to demonstrate the new modeling idea and the efficiency of the proposed solution methods.     

Database placement in communication networks for minimizing the overall transmission cost

The minimum spanning tree write policy for the maintenance of the consistency of a distributed database, where replicated data exist, has been proposed in [1]. In this paper, we first present a data placement heuristic algorithm in general networks for minimizing the overall transmission cost for processing the typical demands of queries (by a “simple” process strategy) and updates (by the minimum spanning tree write policy). Several interesting optimality estimation results of this algorithm are shown, while the computational intractability of the complete optimization, with respect to the simple strategy, is shown as well. Secondly, we apply a classical climbing hill technique to obtain a dynamic database placement algorithm based on an employed optimizer—a collection of distributed query process algorithms. This is guaranteed to output a “locally optimal” data allocation. The implementation results also show that those two heuristics work well in practice.     

Optimizing a multi-stage production/inventory system by DC programming based approaches

This paper deals with optimizing the cost of set up, transportation and inventory of a multi-stage production system in presence of bottleneck. The considered optimization model is a mixed integer nonlinear program. We propose two methods based on DC (Difference of Convex) programming and DCA (DC Algorithm)—an innovative approach in nonconvex programming framework. The mixed integer nonlinear problem is first reformulated as a DC program and then DCA is developed to solve the resulting problem. In order to globally solve the problem, we combine DCA with a Branch and Bound algorithm (BB-DCA). A convex minorant of the objective function is introduced. DCA is used to compute upper bounds while lower bounds are calculated from a convex relaxation problem. The numerical results compared with those of COUENNE (http://www.coin-or.org/download/binary/Couenne/), a solver for mixed integer nonconvex programming, show the rapidity and the ?-globality of DCA in almost cases, as well as the efficiency of the combined DCA-Branch and Bound algorithm. We also propose a simple heuristic algorithm which is proved by experimental results to be better than an existing heuristic in the literature for this problem.     

Coderivatives in parametric optimization

We consider parametric families of constrained problems in mathematical programming and conduct a local sensitivity analysis for multivalued solution maps. Coderivatives of set-valued mappings are our basic tool to analyze the parametric sensitivity of either stationary points or stationary point-multiplier pairs associated with parameterized optimization problems. An implicit mapping theorem for coderivatives is one key to this analysis for either of these objects, and in addition, a partial coderivative rule is essential for the analysis of stationary points. We develop general results along both of these lines and apply them to study the parametric sensitivity of stationary points alone, as well as stationary point-multiplier pairs. Estimates are computed for the coderivative of the stationary point multifunction associated with a general parametric optimization model, and these estimates are refined and augmented by estimates for the coderivative of the stationary point-multiplier multifunction in the case when the constraints are representable in a special composite form. When combined with existing coderivative formulas, our estimates are entirely computable in terms of the original data of the problem. Key words.parametric optimization – variational analysis – sensitivity – Lipschitzian stability – generalized differentiation – coderivativesThis research was partly supported by the National Science Foundation under grant DMS-0072179.     

Generalized sensitivity analysis of nonlinear programs using a sequence of quadratic programs

ABSTRACT

Local sensitivity information is obtained for KKT points of parametric NLPs that may exhibit active set changes under parametric perturbations; under appropriate regularity conditions, computationally relevant generalized derivatives of primal and dual variable solutions of parametric NLPs are calculated. Ralph and Dempe obtained directional derivatives of solutions of parametric NLPs exhibiting active set changes from the unique solution of an auxiliary quadratic program. This article uses lexicographic directional derivatives, a newly developed tool in nonsmooth analysis, to generalize the classical NLP sensitivity analysis theory of Ralph and Dempe. By viewing said auxiliary quadratic program as a parametric NLP, the results of Ralph and Dempe are applied to furnish a sequence of coupled QPs, whose unique solutions yield generalized derivative information for the NLP. A practically implementable algorithm is provided. The theory developed here is motivated by widespread applications of nonlinear programming sensitivity analysis, such as in dynamic control and optimization problems.     

Parametric generalized set-valued variational inclusions and resolvent equations

In this paper, we develop the sensitivity analysis for generalized set-valued variational inclusions and generalized resolvent equations. We establish the equivalence between the parametric generalized set-valued variational inclusions and parametric generalized resolvent equations, by using the resolvent operator technique without assuming the differentiability of the given data.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

Robust Optimization for the Connected Facility Location Problem

In this paper we present a robust optimization (RO) model for the Connected Facility Location (ConFL) problem within the framework introduced by Bertsimas and Sim [Bertsimas, D. and M. Sim, Robust discrete optimization and network flows, Mathematical Programming 98 (2003), pp. 49–71], and show how to use a heuristic in conjunction with a lower bounding mechanism to rapidly find high-quality solutions. The use of a heuristic and a lower bound mechanism within this RO approach decreases significantly its computational time and broadens its applicability to other NP-hard problems. Here we present some of our computational results that attest to the efficiency of the approach, particularly on the Robust ConFL problem.     

Heuristic algorithms for the minmax regret flow-shop problem with interval processing times

An uncertain version of the permutation flow-shop with unlimited buffers and the makespan as a criterion is considered. The investigated parametric uncertainty is represented by given interval-valued processing times. The maximum regret is used for the evaluation of uncertainty. Consequently, the minmax regret discrete optimization problem is solved. Due to its high complexity, two relaxations are applied to simplify the optimization procedure. First of all, a greedy procedure is used for calculating the criterion’s value, as such calculation is NP-hard problem itself. Moreover, the lower bound is used instead of solving the internal deterministic flow-shop. The constructive heuristic algorithm is applied for the relaxed optimization problem. The algorithm is compared with previously elaborated other heuristic algorithms basing on the evolutionary and the middle interval approaches. The conducted computational experiments showed the advantage of the constructive heuristic algorithm with regards to both the criterion and the time of computations. The Wilcoxon paired-rank statistical test confirmed this conclusion.