The complexity of minimizing the number of shape matrices subject to minimal beam-on time in multileaf collimator field decomposition with bounded fluence

The use of multileaf collimators (MLCs) is a modern way to realize intensity modulated fields in radiotherapy. An important step in the treatment planning is the shape matrix decomposition: the desired fluence distribution, given by an integer matrix, has to be decomposed into a small number shape matrices, i.e. (0,1)-matrices corresponding to the field shapes that can be delivered by the MLC used. The two main objectives are to minimize the total irradiation time, and the number of shape matrices. Assuming that the entries of the fluence matrix are bounded by a constant, we prove that a shape matrix decomposition with minimal number of shape matrices under the condition that the total irradiation time is minimal, can be determined in time polynomial in the matrix dimensions. The results of our algorithm are compared with Engel’s [K. Engel, A new algorithm for optimal multileaf collimator field segmentation, Discrete Appl. Math. 152 (1-3) (2005) 35-51.] heuristic for the reduction of the number of shape matrices.     

A coupled column generation,mixed integer approach to optimal planning of intensity modulated radiation therapy for cancer

Approximately 40% of all U.S. cancer cases are treated with radiation therapy. In Intensity-Modulated Radiation Therapy (IMRT) the treatment planning problem is to choose external beam angles and their corresponding intensity maps (showing how the intensity varies across a given beam) to maximize tumor dose subject to the tolerances of surrounding healthy tissues. Dose, like temperature, is a quantity defined at each point in the body, and the distribution of dose is determined by the choice of treatment parameters available to the planner. In addition to absolute dose limits in healthy tissues, some tissues have at least one dose-volume restriction that requires a fraction of its volume to not exceed a specified tighter threshold level for damage. There may also be a homogeneity limit for the tumor that restricts the allowed spread of dose across its volume. We formulate this planning problem as a mixed integer program over a coupled pair of column generation processes -- one designed to produce intensity maps, and a second specifying protected area choices for tissues under dose-volume restrictions. The combined procedure is shown to strike a balance between computing an approximately optimal solution and bounding its maximum possible suboptimality that we believe holds promise for implementations able to offer the power and flexibility of mixed-integer linear programming models on instances of practical scale.A portion of the work of Dr. Langer, Mr. Thai and Dr. Preciado-Walters was supported by National Science Foundation grant ECS-0120145 and National Cancer Institute 1R41CA91688-01. Dr. Rardin is participated while on rotation as Program Director for Operations Research and Service Enterprise Engineering at the National Science Foundation.     

Discrete problems associated to elliptic equations

This paper deals with the existence of positive solutions of the discrete counterpart of nonlinear elliptic problems. We apply our methods to the study of positive solutions under different hypotheses about the nonlinearities. For example, we consider the cases that are superlinear and sublinear at infinity. Copyright © 2016 John Wiley & Sons, Ltd.     

On games corresponding to sequencing situations with ready times

This paper considers the special class of cooperative sequencing games that arise from one-machine sequencing situations in which all jobs have equal processing times and the ready time of each job is a multiple of the processing time.By establishing relations between optimal orders of subcoalitions, it is shown that each sequencing game within this class is convex.This author is financially supported by the Dutch Organization for Scientific Research (NWO).     

Discrete non-linear inequalities and applications to boundary value problems

In this paper, we generalize some existing discrete Gronwall-Bellman-Ou-Iang-type inequalities to more general situations. These are in turn applied to study the boundedness, uniqueness, and continuous dependence of solutions of certain discrete boundary value problem for difference equations.     

Discrete radar ambiguity problems

In this paper, we pursue the study of the radar ambiguity problem started in [Ph. Jaming, Phase retrieval techniques for radar ambiguity functions, J. Fourier Anal. Appl. 5 (1999) 313–333; G. Garrigós, Ph. Jaming, J.-B. Poly, Zéros de fonctions holomorphes et contre-exemples en théorie des radars, in: Actes des rencontres d'analyse complexe, Atlantique, Poitiers, 2000, pp. 81–104, available on http://hal.ccsd.cnrs.fr/ccsd-00007482]. More precisely, for a given function u we ask for all functions v (called ambiguity partners) such that the ambiguity functions of u and v have same modulus. In some cases, v may be given by some elementary transformation of u and is then called a trivial partner of u, otherwise we call it a strange partner. Our focus here is on two discrete versions of the problem. For the first one, we restrict the problem to functions u of the Hermite class, u=P(x)e^−x2/2, thus reducing it to an algebraic problem on polynomials. Up to some mild restriction satisfied by quasi-all and almost-all polynomials, we show that such a function has only trivial partners. The second discretization, restricting the problem to pulse type signals, reduces to a combinatorial problem on matrices of a special form. We then exploit this to obtain new examples of functions that have only trivial partners. In particular, we show that most pulse type signals have only trivial partners. Finally, we clarify the notion of trivial partner, showing that most previous counterexamples are still trivial in some restricted sense.     

Discrete approximations to spherically symmetric distributions

Summary We consider the approximation of spherically symmetric distributions in ^d by linear combinations of Heaviside step functions or Dirac delta functions. The approximations are required to faithfully reproduce as many moments as possible. We discuss stable methods of computing such approximations, taking advantage of the close connection with Gauss-Christoffel quadrature. Numerical results are presented for the distributions of Maxwell, Bose-Einstein, and Fermi-Dirac.Dedicated to Fritz Bauer on the occasion of his 60th birthdayWork supported in part by the National Science Foundation under Grant MCS-7927158A1     

A two-dimensional strip cutting problem with sequencing constraint

We study a strip cutting problem that arises in the production of corrugated cardboard. In this context, rectangular items of different sizes are obtained by machines, called corrugators, that cut strips of large dimensions according to particular schemes containing at most two types of items. Because of buffer restrictions, these schemes have to be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet (sequencing constraint). We show that the problem of finding a set of schemes of minimum trim loss that satisfies an assigned demand for each item size is strongly NP-hard, even if the sequencing constraint is relaxed. Then, we present two heuristics for the problem with the sequencing constraint, both based on a graph characterization of the feasible solutions. The first heuristic is a two-phase procedure based on a mixed integer linear programming model. The second heuristic follows a completely combinatorial approach and consists of solving a suitable sequence of minimum cost matching problems. For both procedures, an upper bound on the number of schemes (setups) is found. Finally, a computational study comparing the quality of the heuristic solutions with respect to an LP lower bound is reported.     

The order of convergence of eigenfrequencies in finite element approximations of fluid-structure interaction problems

In this paper we prove a double order for the convergence of eigenfrequencies in fluid-structure vibration problems. We improve estimates given recently for compressible and incompressible fluids. To do this, we extend classical results on finite element spectral approximation to nonconforming methods for noncompact operators.

     

Global approximations to the principal real-valued branch of the Lambert W-function

W(z) is defined implicitly as the root of W exp(W) = z. It is shown that a simple analytic approximation has a relative error of less than 5% over the whole domain z ε [−exp(−1), ∞] of the principle branch—sufficiently accurate so that four Newton iterations refine this approximation to a relative error smaller than 1.E-12. As a second form of global approximation, the W-function is expanded as a series of rational Chebyshev functions TB_j in a shifted, logarithmic coordinate with an error that decreases exponentially fast with the series truncation.     

An outer approximations algorithm for computer-aided design problems

This paper presents an implementable algorithm of the outer approximations type for solving nonlinear programming problems with functional inequality constraints. The algorithm was motivated by engineering design problems in circuit tolerancing, multivariable control, and shock-resistant structures.This research was sponsored by the National Science Foundation, Grant No. ENG73-08214A01, and the National Science Foundation (RANN), Grant No. ENV76-04264.     

Discrete Dirichlet boundary value problems with upper semicontinuous right-hand sides

This paper deals with the relationship between solutions of Dirichlet boundary value problems (BVPs) for second order systems of differential inclusions with upper semicontinuous right-hand sides and associated numerical discrete Dirichlet BVPs of second order difference inclusions. First, the existence and estimate of solutions to the discrete BVP is discussed uniformly with respect to the discrete step size. Then convergence of solutions of the numerical discrete BVP and the corresponding semicontinous BVP is studied. Related results are also mentioned which motivated our study of this problem.     

On coupled Boltzmann transport equation related to radiation therapy

We consider a system of Boltzmann transport equations which models the charged particle evolution in media. The system is related to the dose calculation in radiation therapy. Although only one species of particles, say photons is invasing these particles mobilize other type of particles (electrons and positrons). Hence in realistic modelling of particle transport one needs a coupled system of three Boltzmann transport equations. The solution of this system must satisfy the inflow boundary condition. We show existence and uniqueness result of the solution applying generalized Lax-Milgram Theorem. In addition, we verify that (in the case of external therapy) under certain assumptions the “incoming flux to dose operator” D₁ is compact. Also the adjoint is analyzed. Finally we consider the inverse planning problem as an optimal control problem. Its solution can be used as an initial solution of the actual inverse planning problem.     

Fully discrete approximations of parabolic boundary-value problems with nonsmooth boundary data

We study a numerical scheme for the approximation of parabolic boundary-value problems with nonsmooth boundary data. This fully discrete scheme requires no boundary constraints on the approximating elements. Our principal result is the derivation of optimal convergence estimates in L_p[0,T; L₂()] norms for boundary data in L_p[0, T; L₂()], 1p . For the same algorithms, we also show that the convergence remains optimal even in higher norms. The techniques employed are based on the theory of analytic semigroups combined with singular integrals.This paper was written in 1990, when the author was in the Department of Mathematical Sciences, University of Cincinnati. A preliminary version of this research was presented at the SIAM Annual Meeting in July 1989.     

Using eigenstructure of the Hessian to reduce the dimension of the intensity modulated radiation therapy optimization problem

Optimization is of vital importance when performing intensity modulated radiation therapy to treat cancer tumors. The optimization problem is typically large-scale with a nonlinear objective function and bounds on the variables, and we solve it using a quasi-Newton sequential quadratic programming method. This study investigates the effect on the optimal solution, and hence treatment outcome, when solving an approximate optimization problem of lower dimension. Through a spectral decompostion, eigenvectors and eigenvalues of an approximation to the Hessian are computed. An approximate optimization problem of reduced dimension is formulated by introducing eigenvector weights as optimization parameters, where only eigenvectors corresponding to large eigenvalues are included. The approach is evaluated on a clinical prostate case. Compared to bixel weight optimization, eigenvector weight optimization with few parameters results in faster initial decline in the objective function, but with inferior final solution. Another approach, which combines eigenvector weights and bixel weights as variables, gives lower final objective values than what bixel weight optimization does. However, this advantage comes at the expense of the pre-computational time for the spectral decomposition. A preliminary version of this paper was presented at the AAPM 46th annual meeting, held July 25–29, 2004 in Pittsburgh, PA.     

Sharp estimates for finite element approximations to elliptic problems with Neumann boundary data of low regularity

Consider a second order homogeneous elliptic problem with smooth coefficients, , on a smooth domain, , but with Neumann boundary data of low regularity. Interior maximum norm error estimates are given for finite element approximations to this problem. When the Neumann data is not in , these local estimates are not of optimal order but are nevertheless shown to be sharp. A method for ameliorating this sub-optimality by preliminary smoothing of the boundary data is given. Numerical examples illustrate the findings.

     

Discrete approximations to optimization of neutral functional differential inclusions

The paper deals with the convergence of discrete approximations to optimization problems governed by neutral functional differential inclusions. The discrete approximations through Euler finite difference are constructed and the convergence of discrete approximations is proved.     

Interior penalty preconditioners for mixed finite element approximations of elliptic problems

It is established that an interior penalty method applied to second-order elliptic problems gives rise to a local operator which is spectrally equivalent to the corresponding nonlocal operator arising from the mixed finite element method. This relation can be utilized in order to construct preconditioners for the discrete mixed system. As an example, a family of additive Schwarz preconditioners for these systems is constructed. Numerical examples which confirm the theoretical results are also presented.

     

Sharp estimates for finite element approximations to parabolic problems with Neumann boundary data of low regularity

Consider a homogeneous parabolic problem on a smooth bounded domain in ℝ ^N but with initial data and Neumann boundary data of low regularity. Sharp interior maximum norm error estimates are given for a semidiscrete C ⁰ finite element approximation to this problem. These estimates are obtained by first establishing a new localized L ^∞ estimate for semidiscrete finite element approximations on interior subdomains. Numerical examples illustrate the findings. AMS subject classification (2000) 65N30