Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

Primal cutting plane algorithms revisited

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent.  In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.     

On the analysis of a dynamic evolutionary algorithm

Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple variants of evolutionary algorithms like the (1+1) EA on rather simple functions. Nevertheless, only the analysis of the expected run time and the success probability within a given number of steps can guide the choice of the free parameters of the algorithms. Here static (1+1) EAs with a fixed mutation probability are compared with dynamic (1+1) EAs with a simple schedule for the variation of the mutation probability. The dynamic variant is first analyzed for functions typically chosen as example-functions for evolutionary algorithms. Afterwards, it is shown that it can be essential to choose the suitable variant of the (1+1) EA. More precisely, functions are presented where each static (1+1) EA has exponential expected run time while the dynamic variant has polynomial expected run time. For other functions it is shown that the dynamic (1+1) EA has exponential expected run time while a static (1+1) EA with a good choice of the mutation probability has polynomial run time with overwhelming probability.     

Scale Invariance Properties in the Simulated Annealing Algorithm

The Boltzmann distribution used in the steady-state analysis of the simulated annealing algorithm gives rise to several scale invariant properties. Scale invariance is first presented in the context of parallel independent processors and then extended to an abstract form based on lumping states together to form new aggregate states. These lumped or aggregate states possess all of the mathematical characteristics, forms and relationships of states (solutions) in the original problem in both first and second moments. These scale invariance properties therefore permit new ways of relating objective function values, conditional expectation values, stationary probabilities, rates of change of stationary probabilities and conditional variances. Such properties therefore provide potential applications in analysis, statistical inference and optimization. Directions for future research that take advantage of scale invariance are also discussed.     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Local Feasible QP-Free Algorithms for the Constrained Minimization of SC1 Functions

We consider the problem of minimizing an SC¹ function subject to inequality constraints. We propose a local algorithm whose distinguishing features are that: (a) a fast convergence rate is achieved under reasonable assumptions that do not include strict complementarity at the solution; (b) the solution of only linear systems is required at each iteration; (c) all the points generated are feasible. After analyzing a basic Newton algorithm, we propose some variants aimed at reducing the computational costs and, in particular, we consider a quasi-Newton version of the algorithm.     

On the Application of the Auxiliary Problem Principle

The auxiliary problem principle (APP) derives from a general theory on decomposition-coordination methods establishing a comprehensive framework for both one-level and two-level methods. In this paper, the results of the two-level methods of APP are specialized for an efficient application to some engineering problems.     

基于遗传算法和指标满意度求解的第三方物流企业物流中心选址方法

本利用AHP和模糊综合评价法评价物流中心选址的定性指标、用量化选址模型结合遗传算法计算定量指标，再藉助指标满意度求解把定性和定量的指标进行综合，从而为决策对物流中心选址做出科学的决策提供支持。     

Minimum Distance Between the Faces of Two Convex Polyhedra: A Sufficient Condition

The problem of finding the Euclidean distance between two convex polyhedra can be reduced to the combinatorial optimization problem of finding the minimum distance between their faces. This paper presents a global optimality criterion for this problem. An algorithm (QLDPA) for the fast computation of the distance between convex and bounded polyhedra is proposed as an application of it. Computer experiments show its fast performance, especially when the total number of vertices is large.     

Robust handling of non‐linear constraints for GA optimization of aerodynamic shapes

A new approach to the robust handling of non‐linear constraints for GAs (genetic algorithms) optimization is proposed. A specific feature of the approach consists of the change in the conventional search strategy by employing search paths which pass through both feasible and infeasible points (contrary to the traditional approach where only feasible points may be included in a path). The method (driven by full Navier–Stokes computations) was applied to the problem of multiobjective optimization of aerodynamic shapes subject to various geometrical and aerodynamic constraints. The results demonstrated that the method retains high robustness of conventional GAs while keeping CFD computational volume to an acceptable level, which allowed the algorithm to be used in a demanding engineering environment. Copyright © 2004 John Wiley & Sons, Ltd.