Mixed integer programming approaches to exact minimization of total treatment time in cancer radiotherapy using multileaf collimators

The effectiveness of radiation therapy for cancer depends on the patient remaining still during treatment. It is thus important to minimize the total treatment time (TTT). When such treatment is delivered using multileaf collimators in “step-and-shoot” mode, it consists of a sequence of collimator configurations, or patterns; for each, the patient is exposed to radiation for a specified time, or beam-on time. The TTT can thus be divided into the total beam-on time and the time spent reconfiguring the collimators. The latter can reasonably be approximated by the number of patterns, multiplied by a constant overhead time per pattern. Previous approaches to this problem have all been heuristic; in particular none of them actually use the pattern overhead time to ascertain the best trade-off between beam-on time and number of patterns. In this paper, we develop exact solution approaches, based on mixed integer programming (MIP) formulations, which minimize the TTT. We consider direct solution of MIP formulations, and then exploit the bicriteria structure of the objective to derive an algorithm that “steps up” through the number of patterns used, leading to substantial computational savings.     

Structure minimization using the impact factor in neural networks

Despite many advances, the problem of determining the proper size of a neural network is important, especially for its practical implications in such issues as learning and generalization. Unfortunately, it is not usually obvious which size is best; a system that is too small will not be able to learn the data, while one that is just big enough may learn very slowly and be very sensitive to initial conditions and learning parameters. There are two types of approach to determining the network size: pruning and growing. Pruning consists of training a network which is larger than necessary, and then removing unnecessary weights/nodes. Here, a new pruning method is developed, based on the penalty-term method. This method makes the neural networks good for generalization, and reduces the retraining time needed after pruning weights/nodes. This work was presented, in part, at the 6th International Symposium on Artificial Life and Robotics, Tokyo, Japan, January 15–17, 2001.     

Total flow time minimization in a flowshop sequence-dependent group scheduling problem

We have developed a mathematical programming model for minimizing total flow time of the flow shop sequence dependent group scheduling (FSDGS) problem, typically classified as F_m|fmls, S_plk, prmu|∑C_j. As the problem is shown to be strongly NP-hard, a tabu search (TS) algorithm as well as a hybrid ant colony optimization (HACO) algorithm have been developed to heuristically solve the problem. A lower bounding (LB) method based on the Branch-and-Price algorithm is also developed to evaluate the quality of the metaheuristic algorithms. In order to compare the performance of metaheuristic algorithms, random test problems, ranging in size from small, medium, to large are created and solved by both the TS and the HACO algorithms. A comparison shows that the HACO algorithm has a better performance than the TS algorithm. The results of the heuristic algorithms are also compared with the results of the LB method to evaluate the quality of the solutions. The LB method presented in this paper can be generalized to solve the FSDGS problem with other objective functions.     

Computation of the Hessian matrix in aerodynamic inverse design using continuous adjoint formulations

Continuous adjoint formulations for the computation of (first and) second order derivatives of the objective function governing inverse design problems in 2D inviscid flows are presented. These are prerequisites for the use of the very efficient exact Newton method. Four new formulations based on all possible combinations of the direct differentiation method and the continuous adjoint approach to compute the sensitivity derivatives of objective functions, constrained by the flow equations, are presented. They are compared in terms of the expected CPU cost to compute the Hessian of the objective function used in single-objective optimization problems with N degrees of freedom. The less costly among them was selected for further study and tested in inverse design problems solved by means of the Newton method. The selected approach, which will be referred to as the direct-adjoint one, since it performs direct differentiation for the gradient and, then, uses the adjoint approach to compute the Hessian, requires as many as N+2 equivalent flow solutions for each Newton step. The major part of the CPU cost (N equivalent flow solutions) is for the computation of the gradient but, fortunately, this task is directly amenable to parallelization. The method is used to reconstruct ducts or cascade airfoils for a known pressure distribution along their solid boundaries, at inviscid flow conditions. The examined cases aim at demonstrating the accuracy of the proposed method in computing the exact Hessian matrix as well as the efficiency of the exact Newton method as an optimization tool in aerodynamic design.     

Efficient exact k-flexible aggregate nearest neighbor search in road networks using the M-tree

The Journal of Supercomputing - This study proposes an efficient exact k-flexible aggregate nearest neighbor (k-FANN) search algorithm in road networks using the M-tree. The state-of-the-art...     

Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type

This paper addresses the total completion time minimization in a two-stage differentiation flowshop where the sequences of jobs per type are predetermined. The two-stage differentiation flowshop consists of a stage-1 common machine and m stage-2 parallel dedicated machines. The goal is to determine an optimal interleaved processing sequence of all jobs at the first stage. We propose an dynamic programming algorithm, where nk is the number of type-k jobs. The running time is polynomial when m is constant.     

Mathematical aspect of the stream-function equations of compressible turbomachinery flows and their finite element approximations using optimal control

In this paper we establish the partial differential equation and properly pose conditions for the stream function on an arbitrary stream surface in a turbomachine using tensor analysis and a semi-geodesic coordinate system. We provide computational examples using the finite element method and also the error estimate of Galerkin's finite element approximation which depends on the Mach number.     

A versatile implementation of the Gauss-Newton minimization algorithm using MATLAB for Macintosh microcomputers

The present report describes a weighted nonlinear least-squares minimization routine for fitting a wide variety of functions nonlinear in the parameters. The minimization routine is implemented in MacMATLAB, the Macintosh microcomputer version of MATLAB, an interactive program for scientific numeric calculations. Our algorithm makes use of a subroutine that estimates the required derivatives numerically, avoiding the need to differentiate the function under study analytically. We have also implemented two specific subroutines to integrate ordinary differential equations numerically. Therefore, in principle, any kind of nonlinear function can be fitted to a given set of data. The program only requires that the user writes the appropriate equation in a specific subroutine, thus relieving one from knowing and using any 'low-level' code. Other features of the program are: (a) the possibility of using weight to correct for nonuniformity of variance by flexible specification of the error structure; (b) the possibility of checking the parameter values and the residual variance at each iteration; and (c) by the use of the graphic capabilities of MacMATLAB, the possibility of following the improvement of the fitting graphically. One example of nonlinear functions and one example of linear differential equation together with their respective 'function file' and illustrative data are presented to demonstrate the flexibility of our approach and the power of the method used.     

An exact solution to the stabilization of discrete systems using a first-order controller

An exact solution is derived for stabilizing a given but arbitrary, linear time-invariant discrete system by a first-order discrete-time feedback controller, which has received considerable attention in the past few years. An approach has been recently proposed to compute the first-order controllers, given in the form of C(z)=(zx/sub 1/+x/sub 2/)/(z+x/sub 3/). This approach derives the stabilizing set in the x/sub 1/-x/sub 2/ plane by fixing x/sub 3/, and then repeat the procedure by sweeping over all possible values of x/sub 3/. In this note, from the geometrical point of view, we present an exact solution to the problem.     

Uncertainty minimization in the localization of polyhedral objects

A straightforward method is presented for the determination of the optimal sensor exploration in the localization of a polyhedral object, whose geometry is known. Optimality is intended in the sense of the a posteriori covariance matrix of the object position and orientation parameters. The method consists in decomposing the problem into simpler subproblems, each one relative to a single planar face of the object. It requires reasonable processing time, i.e. comparable with the sensor activation time     

Energy minimization in the STT-RAM-based high-capacity last-level caches

The Journal of Supercomputing - Spin-transfer torque random access memory (STT-RAM) is a suitable alternative to DRAM in the large last-level caches (L3Cs) on account of low leakage, the absence of...     

Efficient calculation of the Gauss-Newton approximation of the Hessian matrix in neural networks

The Levenberg-Marquardt (LM) learning algorithm is a popular algorithm for training neural networks; however, for large neural networks, it becomes prohibitively expensive in terms of running time and memory requirements. The most time-critical step of the algorithm is the calculation of the Gauss-Newton matrix, which is formed by multiplying two large Jacobian matrices together. We propose a method that uses backpropagation to reduce the time of this matrix-matrix multiplication. This reduces the overall asymptotic running time of the LM algorithm by a factor of the order of the number of output nodes in the neural network.     

New exact solutions for the KdV equation with higher order nonlinearity by using the variational method

The Korteweg-de Vries (KdV) equation with higher order nonlinearity models the wave propagation in one-dimensional nonlinear lattice. A higher-order extension of the familiar KdV equation is produced for internal solitary waves in a density and current stratified shear flow with a free surface. The variational approximation method is applied to obtain the solutions for the well-known KdV equation. Explicit solutions are presented and compared with the exact solutions. Very good agreement is achieved, demonstrating the high efficiency of variational approximation method. The existence of a Lagrangian and the invariant variational principle for the higher order KdV equation are discussed. The simplest version of the variational approximation, based on trial functions with two free parameters is demonstrated. The jost functions by quadratic, cubic and fourth order polynomials are approximated. Also, we choose the trial jost functions in the form of exponential and sinh solutions. All solutions are exact and stable, and have applications in physics.     

An algorithm for the strip packing problem using collision free region and exact fitting placement

The irregular shape packing problem is approached. The container has a fixed width and an open dimension to be minimized. The proposed algorithm constructively creates the solution using an ordered list of items and a placement heuristic. Simulated annealing is the adopted metaheuristic to solve the optimization problem. A two-level algorithm is used to minimize the open dimension of the container. To ensure feasible layouts, the concept of collision free region is used. A collision free region represents all possible translations for an item to be placed and may be degenerated. For a moving item, the proposed placement heuristic detects the presence of exact fits (when the item is fully constrained by its surroundings) and exact slides (when the item position is constrained in all but one direction). The relevance of these positions is analyzed and a new placement heuristic is proposed. Computational comparisons on benchmark problems show that the proposed algorithm generated highly competitive solutions. Moreover, our algorithm updated some best known results.     

Minimization of voltage deviation and power losses in power networks using Pareto optimization methods

Voltage regulation is an important task in electrical engineering for controlling node voltages in a power network. A widely used solution for the problem of voltage regulation is based on adjusting the taps in under load tap changers (ULTCs) power transformers and, in some cases, turning on Flexible Alternating Current Transmission Systems (FACTS), synchronous machines or capacitor banks in the substations. Most papers found in the literature dealing with this problem aim to avoid voltage drops in radial networks, but few of them consider power losses or meshed networks. The aim of this paper is to present and evaluate the performance of several multi-objective algorithms, including hybrid approaches, in order to minimize both voltage deviation and power losses by operating ULTCs located in high voltage substations. In particular, a well-known multi-objective algorithm, PAES, is used for this purpose. PAES finds a set of solutions according to Pareto-optimization concepts. Furthermore, this algorithm is hybridized with simulated annealing and tabu search to improve the quality of the solutions. The implemented algorithms are evaluated using two test networks, and the numerical results are analyzed with two metrics often used in the multi-objective field. The results obtained demonstrate the good performance of these algorithms.