A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems

This paper is a review of the approachesdeveloped to solve 2D packing problems withmeta-heuristic algorithms. As packing tasks arecombinatorial problems with very large searchspaces, the recent literature encourages theuse of meta-heuristic search methods, inparticular genetic algorithms. The objective ofthis paper is to present and categorise thesolution approaches in the literature for 2Dregular and irregular strip packing problems.The focus is hereby on the analysis of themethods involving genetic algorithms. Anoverview of the methods applying othermeta-heuristic algorithms including simulatedannealing, tabu search, and artificial neuralnetworks is also given.     

Optimal Control of Two-Stage Discrete Event Systems with Real-Time Constraints

We consider discrete event systems (DES) involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal sample path that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider a two-stage problem with homogeneous cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing “virtual” deadlines at the first stage, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that the solution obtained by an iterative virtual deadline algorithm (VDA) converges to the global optimal solution of the two-stage problem and illustrate the efficiency of the VDA through numerical examples.

On the analysis of stochastic divide and conquer algorithms

This paper develops general tools for the analysis of stochastic divide and conquer algorithms. We concentrate on the average performance and the distribution of the running time of the algorithm. As a special example we analyse the average performance and the running time distribution of the (2k + 1)-median version of Quicksort. Online publication October 13, 2000.     

ON THE PARTIAL SUMS OF RESIDUALS IN AUTOREGRESSIVE AND MOVING AVERAGE MODELS

Abstract. The limiting process of partial sums of residuals in stationary and invertible autoregressive moving-average models is studied. It is shown that the partial sums converge to a standard Brownian motion under the assumptions that estimators of unknown parameters are root- n consistent and that innovations are independent and identically distributed random variables with zero mean and finite variance or, more generally, are martingale differences with moment restrictions specified in Theorem 1. Applications for goodness-of-fit and change-point problems are considered. The use of residuals for constructing nonparametric density estimation is discussed.     

Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

Improved LP-based algorithms for the closest string problem

In a recent paper by Liu et al. [Exact algorithm and heuristic for the closest string problem, Computers & Operations Research 2011;38:1513-20], a polynomial time heuristic procedure is proposed for the closest string problem (CSP). Such heuristic called LDDA_LSS is a combination of a previously published approximation algorithm and local search strategies. This paper points out that an instant algorithm deriving a feasible solution directly from the continuous relaxation solution of a standard ILP formulation of CSP already strongly outperforms LDDA_LSS both in terms of solution quality and computing time. Two core based procedures are then proposed that further improve the results of the instant algorithm. Based on these results, we conclude that such LP-based approaches for their efficiency and simplicity should be used as a benchmark for future heuristics on CSP.     

A regularization method for a Cauchy problem of Laplace's equation in an annular domain

In this paper, we propose a new regularization method based on a finite-dimensional subspace generated from fundamental solutions for solving a Cauchy problem of Laplace's equation in an annular domain. Based on a conditional stability for the Cauchy problem of Laplace's equation, we obtain a convergence estimate under the suitable choice of a regularization parameter and an a-priori bound assumption on the solution. A numerical example is provided to show the effectiveness of the proposed method from both accuracy and stability.     

Combination of non-classical pseudospectral and direct methods for the solution of brachistochrone problem

In this paper, we propose a combination of non-classical pseudospectral and direct methods to find the solution of brachistochrone problem. The method converts the optimal control problem of brachistochrone, into a sequence of quadratic programming problems. To this end, the quasilinearization method is used to replace the nonlinear optimal control problem into a sequence of constrained linear-quadratic optimal control problems; then each of the state variables is approximated by a weighted interpolation function based on the non-classical orthogonal polynomials. The method gives the information of the quadratic programming problems explicitly (the Hessian and the gradient of the cost function). Using this method, the solution of the brachistochrone problem is compared with those in the literature.     

Optimal error estimates of the penalty method for the linearized viscoelastic flows

In this article, optimal error estimates of the penalty method for the linearized viscoelastic flows equations arising in the Oldroyd model are derived. Furthermore, error estimates for the backward Euler time discretization scheme in L ² and H ¹-norms are obtained.