Preventive maintenance scheduling of power generating units

The problem of preventive maintenance planning of electric power generating units can be formulated as a mixed-integer linear optimization problem. An extension of the model is presented to deal with more realistic assumptions about utilization of power resource. We propose a heuristic iterative exchange procedure to solve these problems. We introduce two methods to prevent jamming situations outside the feasible domain or at a local optimum. The first method is a recursive exchange procedure called multiple exchanges method and the second relies on Lagrangian relaxation. Furthermore, we compare these procedures with a tabu search.This research was supported by NSERC (Grant A8312) and FCAR (Grant ER-0289).Michèle Charest had an NSERC Scholarship to work on this project.     

Criteria and dimension reduction of linear multiple criteria optimization problems

Two of the main approaches in multiple criteria optimization are optimization over the efficient set and utility function program. These are nonconvex optimization problems in which local optima can be different from global optima. Existing global optimization methods for solving such problems can only work well for problems of moderate dimensions. In this article, we propose some ways to reduce the number of criteria and the dimension of a linear multiple criteria optimization problem. By the concept of so-called representative and extreme criteria, which is motivated by the concept of redundant (or nonessential) objective functions of Gal and Leberling, we can reduce the number of criteria without altering the set of efficient solutions. Furthermore, by using linear independent criteria, the linear multiple criteria optimization problem under consideration can be transformed into an equivalent linear multiple criteria optimization problem in the space of linear independent criteria. This equivalence is understood in a sense that efficient solutions of each problem can be derived from efficient solutions of the other by some affine transformation. As a result, such criteria and dimension reduction techniques could help to increase the efficiency of existing algorithms and to develop new methods for handling global optimization problems arisen from multiple objective optimization.     

Successive search methods for solving a canonical DC programming problem

In this article, we propose two successive search methods for solving a canonical DC programming problem constrained by the difference set between two compact convex sets in the case where the dimension number is greater than or equal to three. In order to find feasible solutions, the algorithms generate the directions based on a branch and bound procedure, successively. By exploring the provisional solutions throughout the intersection of the boundaries of two compact convex sets, both algorithms calculate an approximate solution.     

Binary knapsack problems with random budgets

The binary knapsack problem is a combinatorial optimization problem in which a subset of a given set of elements needs to be chosen in order to maximize profit, given a budget constraint. In this paper, we study a stochastic version of the problem in which the budget is random. We propose two different formulations of this problem, based on different ways of handling infeasibility, and propose an exact algorithm and a local search-based heuristic to solve the problems represented by these formulations. We also present the results from some computational experiments.     

An efficient spectral method and rigorous error analysis based on dimension reduction scheme for fourth order problems

In this paper, we propose an effective spectral method based on dimension reduction scheme for fourth order problems in polar geometric domains. First, the original problem is decomposed into a series of one‐dimensional fourth order problems by polar coordinate transformation and the orthogonal properties of Fourier basis function. Then the weak form and the corresponding discrete scheme of each one‐dimensional fourth order problem are derived by introducing polar conditions and appropriate weighted Sobolev spaces. In addition, we define the projection operators in the weighted Sobolev space and give its approximation properties, and further prove the error estimation of each one‐dimensional fourth order problem. Finally, we provide some numerical examples, and the numerical results show the effectiveness of our algorithm and the correctness of the theoretical results.     

Generating equations approach for quadratic matrix equations

We show how Van Loan's method for annulling the (2,1) block of skew‐Hamiltonian matrices by symplectic‐orthogonal similarity transformation generalizes to general matrices and provides a numerical algorithm for solving the general quadratic matrix equation: For skew‐Hamiltonian matrices we find their canonical form under a similarity transformation and find the class of all symplectic‐orthogonal similarity transformations for annulling the (2,1) block and simultaneously bringing the (1,1) block to Hessenberg form. We present a structure‐preserving algorithm for the solution of continuous‐time algebraic Riccati equation. Unlike other methods in the literature, the final transformed Hamiltonian matrix is not in Hamiltonian–Schur form. Three applications are presented: (a) for a special system of partial differential equations of second order for a single unknown function, we obtain the matrix of partial derivatives of second order of the unknown function by only algebraic operations and differentiation of functions; (b) for a similar transformation of a complex matrix into a symmetric (and three‐diagonal) one by applying only finite algebraic transformations; and (c) for finite‐step reduction of the eigenvalues–eigenvectors problem of a Hermitian matrix to the eigenvalues– eigenvectors problem of a real symmetric matrix of the same dimension. Copyright © 1999 John Wiley & Sons, Ltd.     

A successive approximation method for quantum separability

Determining whether a quantum state is separable or inseparable （entangled） is a problem of fundamental importance in quantum science and has attracted much attention since its first recognition by Einstein, Podolsky and Rosen [Phys. Rev., 1935, 47： 777] and SchrSdinger [Naturwissenschaften, 1935, 23： 807-812, 823-828, 844-849]. In this paper, we propose a successive approximation method （SAM） for this problem, which approximates a given quantum state by a so-called separable state： if the given states is separable, this method finds its rank-one components and the associated weights; otherwise, this method finds the distance between the given state to the set of separable states, which gives information about the degree of entanglement in the system. The key task per iteration is to find a feasible descent direction, which is equivalent to finding the largest M-eigenvalue of a fourth-order tensor. We give a direct method for this problem when the dimension of the tensor is 2 and a heuristic cross-hill method for cases of high dimension. Some numerical results and experiences are presented.     

Finding maximum likelihood estimators for the three-parameter Weibull distribution

Much work has been devoted to the problem of finding maximum likelihood estimators for the three-parameter Weibull distribution. This problem has not been clearly recognized as a global optimization one and most methods from the literature occasionally fail to find a global optimum. We develop a global optimization algorithm which uses first order conditions and projection to reduce the problem to a univariate optimization one. Bounds on the resulting function and its first order derivative are obtained and used in a branch-and-bound scheme. Computational experience is reported. It is also shown that the solution method we propose can be extended to the case of right censored samples.     

A hybrid heuristic for the maximum dispersion problem

In this paper we propose a hybrid heuristic for the Maximum Dispersion Problem of finding a balanced partition of a set of objects such that the shortest intra-part distance is maximized. In contrast to clustering problems, dispersion problems aim for a large spread of objects in the same group. They arise in many practical applications such as waste collection and the formation of study groups. The heuristic alternates between finding a balanced solution, and increasing the dispersion. Balancing is achieved by a combination of a minimum cost flow algorithm to find promising pairs of parts and a branch-and-bound algorithm that searches for an optimal balance, and the dispersion is increased by a local search followed by an ejection chain method for escaping local minima. We also propose new upper bounds for the problem. In computational experiments we show that the heuristic is able to find solutions significantly faster than previous approaches. Solutions are close to optimal and in many cases provably optimal.     

Variable and large neighborhood search to solve the multiobjective set covering problem

In this paper, we study the multiobjective version of the set covering problem. To our knowledge, this problem has only been addressed in two papers before, and with two objectives and heuristic methods. We propose a new heuristic, based on the two-phase Pareto local search, with the aim of generating a good approximation of the Pareto efficient solutions. In the first phase of this method, the supported efficient solutions or a good approximation of these solutions is generated. Then, a neighborhood embedded in the Pareto local search is applied to generate non-supported efficient solutions. In order to get high quality results, two elaborate local search techniques are considered: a large neighborhood search and a variable neighborhood search. We intensively study the parameters of these two techniques. We compare our results with state-of-the-art results and we show that with our method, better results are obtained for different indicators.     

GRASP with path relinking for the orienteering problem

In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adaptive Search Procedure (GRASP) and the Path Relinking methodologies—for finding approximate solutions to this optimization problem. We explore different constructive methods and combine two neighbourhoods in the local search of GRASP. Our experimentation with 196 previously reported instances shows that the proposed procedure obtains high-quality solutions employing short computing times.     

Properties and methods for finding the best rank-one approximation to higher-order tensors

The problem of finding the best rank-one approximation to higher-order tensors has extensive engineering and statistical applications. It is well-known that this problem is equivalent to a homogeneous polynomial optimization problem. In this paper, we study theoretical results and numerical methods of this problem, particularly focusing on the 4-th order symmetric tensor case. First, we reformulate the polynomial optimization problem to a matrix programming, and show the equivalence between these two problems. Then, we prove that there is no duality gap between the reformulation and its Lagrangian dual problem. Concerning the approaches to deal with the problem, we propose two relaxed models. The first one is a convex quadratic matrix optimization problem regularized by the nuclear norm, while the second one is a quadratic matrix programming regularized by a truncated nuclear norm, which is a D.C. function and therefore is nonconvex. To overcome the difficulty of solving this nonconvex problem, we approximate the nonconvex penalty by a convex term. We propose to use the proximal augmented Lagrangian method to solve these two relaxed models. In order to obtain a global solution, we propose an alternating least eigenvalue method after solving the relaxed models and prove its convergence. Numerical results presented in the last demonstrate, especially for nonpositive tensors, the effectiveness and efficiency of our proposed methods.     

Maximally Disjoint Solutions of the Set Covering Problem

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP-complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, extensive computational tests are given demonstrating the nature of these algorithms. These tests are carried out both on randomly generated problems and on problems found in the literature.     

A Robust Heuristic for Batting Order Optimization Under Uncertainty

Baseball teams are faced with a difficult scheduling problem every day: given a set of nine players, find the optimal sequence in which they should bat. Effective optimization can increase a team's win total by up to 3 wins per season, and 10% of all Major League teams missed the playoffs by 3 or less wins in 1998. Considering the recent $252 million contract given to one player, it is obvious that baseball is a serious business in which making the playoffs has large financial benefits. Using the insights gleaned from a Markov chain model of baseball, we propose a batting order optimization heuristic that performs 1,000 times faster than the previous best heuristic for this problem. Our algorithm generates batting orders that (i) are optimal or near-optimal, and (ii) remain robust under uncertainty in skill measurement.     

Tree search for the stacking problem

The stacking problem is a hard combinatorial optimization problem with high practical interest in, for example, steel storage or container port operations. In this problem, a set of items is stored in a warehouse for a period of time, and a crane is used to place them in a limited number of stacks. Since the entrance and exit of items occurs in an arbitrary order, items may have to be relocated in order to reach and deliver other items below them. The objective of the problem is to find a feasible sequence of movements that delivers all items, while minimizing the total number of movements. We study the scalability of an exact approach to this problem, and propose two heuristic methods to solve it approximately. The two heuristic approaches are a multiple simulation algorithm using semi-greedy construction heuristics, and a stochastic best-first tree search algorithm. The two methods are compared in a set of challenging instances, revealing a superior performance of the tree search approach in most cases.     

Image registration with iterated local search

This contribution is devoted to the application of iterated local search to image registration, a very complex, real-world problem in the field of image processing. To do so, we first re-define this parameter estimation problem as a combinatorial optimization problem, then analyze the use of image-specific information to guide the search in the form of an heuristic function, and finally propose its solution by iterated local search. Our algorithm is tested by comparing its performance to that of two different baseline algorithms: iterative closest point, a well-known, image registration technique, a hybrid algorithm including the latter technique within a simulated annealing approach, a multi-start local search procedure, that allows us to check the influence of the search scheme considered in the problem solving, and a real coded genetic algorithm. Four different problem instances are tackled in the experimental study, resulting from two images and two transformations applied on them. Three parameter settings are analyzed in our approach in order to check three heuristic information scenarios where the heuristic is not used at all, is partially used or almost completely guides the search process, as well as two different number of iterations in the algorithms outer-inner loops. This work was partially supported by the Spanish Ministerio de Ciencia y Tecnología under project TIC2003-00877 (including FEDER fundings) and under Network HEUR TIC2002-10866-E.     

Optimal control of bioprocess systems using hybrid numerical optimization algorithms

In the paper, we consider the bioprocess system optimal control problem. Generally speaking, it is very difficult to solve this problem analytically. To obtain the numerical solution, the problem is transformed into a parameter optimization problem with some variable bounds, which can be efficiently solved using any conventional optimization algorithms, e.g. the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. However, in spite of the improved Broyden–Fletcher–Goldfarb–Shanno algorithm is very efficient for local search, the solution obtained is usually a local extremum for non-convex optimal control problems. In order to escape from the local extremum, we develop a novel stochastic search method. By performing a large amount of numerical experiments, we find that the novel stochastic search method is excellent in exploration, while bad in exploitation. In order to improve the exploitation, we propose a hybrid numerical optimization algorithm to solve the problem based on the novel stochastic search method and the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. Convergence results indicate that any global optimal solution of the approximate problem is also a global optimal solution of the original problem. Finally, two bioprocess system optimal control problems illustrate that the hybrid numerical optimization algorithm proposed by us is low time-consuming and obtains a better cost function value than the existing approaches.     

An efficient spectral‐Galerkin method based on a dimension reduction scheme for eigenvalue problems of Schrödinger equations

In this paper, we propose an efficient spectral‐Galerkin method based on a dimension reduction scheme for eigenvalue problems of Schrödinger equations. Firstly, we carry out a truncation from a three‐dimensional unbounded domain to a bounded spherical domain. By using spherical coordinate transformation and spherical harmonic expansion, we transform the original problem into a series of one‐dimensional eigenvalue problem that can be solved effectively. Secondly, we introduce a weighted Sobolev space to treat the singularity in the effective potential. Using the property of orthogonal polynomials in weighted Sobolev space, the error estimate for the approximate eigenvalues and corresponding eigenfunctions are proved. Error estimates show that our numerical method can achieve spectral accuracy for approximate eigenvalues and eigenfunctions. Finally, we give some numerical examples to demonstrate the efficiency of our algorithms and the correctness of the theoretical results.     

Multi-objective optimization for clustering 3-way gene expression data

In this paper, we use the Fuzzy C-means method for clustering 3-way gene expression data via optimization of multiple objectives. A reformulation of the total clustering criterion is used to obtain an expression which has fewer variables compared to the classical FCM criterion. This transformation allows the use of a direct global optimizer in constrast to the alternating search commonly used. Gene expression data from microarray technology is generally of high dimension. The problem of empty space is known for this kind of data. We propose in this paper a transformation allowing more contrast in distances between all pairs of data samples. This, hence, increases the likelihood of detecting group structure, if any, in high dimensional datasets.     

Combining Trust-Region Techniques and Rosenbrock Methods to Compute Stationary Points

Rosenbrock methods are popular for solving a stiff initial-value problem of ordinary differential equations. One advantage is that there is no need to solve a nonlinear equation at every iteration, as compared with other implicit methods such as backward difference formulas or implicit Runge–Kutta methods. In this article, we introduce a trust-region technique to select the time steps of a second-order Rosenbrock method for a special initial-value problem, namely, a gradient system obtained from an unconstrained optimization problem. The technique is different from the local error approach. Both local and global convergence properties of the new method for solving an equilibrium point of the gradient system are addressed. Finally, some promising numerical results are also presented. This research was supported in part by Grant 2007CB310604 from National Basic Research Program of China, and #DMS-0404537 from the United States National Science Foundation, and Grant #W911NF-05-1-0171 from the United States Army Research Office, and the Research Grant Council of Hong Kong.