Combinatorial optimization for an improved transition from fluence optimization to fluence delivery in IMRT treatment planning

The intensity modulated radiation therapy (IMRT) treatment planning problem is usually divided into three smaller problems that are solved sequentially: geometry problem, intensity problem and realization problem. There are many models and algorithms that address each one of the problems in a satisfactory way. However, these problems cannot be seen separately, because strong links exist between them. While the linkage between the geometry problem and the intensity problem is straightforward, the linkage between the intensity problem and the realization problem is all but simple and will determine the quality of the treatment planning. In practice, the linkage between these problems is, most of the times, done in a rather simple way, usually by rounding. This can lead to a significant deterioration of the treatment plan quality. We propose a combinatorial optimization approach to enable an improved transition from optimized to delivery fluence maps in IMRT treatment planning. Two clinical examples of head and neck cancer cases are used, both to present numerical evidences of the resulting deterioration of plan quality if a simplistic approach is used, and also to highlight a combinatorial optimization approach as a valuable alternative when linking the intensity problem and the realization problem.     

IMRT treatment planning for prostate cancer using prioritized prescription optimization and mean-tail-dose functions

Treatment planning for intensity modulated radiation therapy (IMRT) is challenging due to both the size of the computational problems (thousands of variables and constraints) and the multi-objective, imprecise nature of the goals. We apply hierarchical programming to IMRT treatment planning. In this formulation, treatment planning goals/objectives are ordered in an absolute hierarchy, and the problem is solved from the top-down such that more important goals are optimized in turn. After each objective is optimized, that objective function is converted into a constraint when optimizing lower-priority objectives. We also demonstrate the usefulness of a linear/quadratic formulation, including the use of mean-tail-dose (mean dose to the hottest fraction of a given structure), to facilitate computational efficiency. In contrast to the conventional use of dose-volume constraints (no more than x% volume of a structure should receive more than y dose), the mean-tail-dose formulation ensures convex feasibility spaces and convex objective functions. To widen the search space without seriously degrading higher priority goals, we allowed higher priority constraints to relax or 'slip' a clinically negligible amount during lower priority iterations. This method was developed and tuned for external beam prostate planning and subsequently tested using a suite of 10 patient datasets. In all cases, good dose distributions were generated without individual plan parameter adjustments. It was found that allowance for a small amount of 'slip,' especially in target dose homogeneity, often resulted in improved normal tissue dose burdens. Compared to the conventional IMRT treatment planning objective function formulation using a weighted linear sum of terms representing very different dosimetric goals, this method: (1) is completely automatic, requiring no user intervention, (2) ensures high-priority planning goals are not seriously degraded by lower-priority goals, and (3) ensures that lower priority, yet still important, normal tissue goals are separately pushed as far as possible without seriously impacting higher priority goals.     

Strong valid inequalities for fluence map optimization problem under dose-volume restrictions

Fluence map optimization problems are commonly solved in intensity modulated radiation therapy (IMRT) planning. We show that, when subject to dose-volume restrictions, these problems are NP-hard and that the linear programming relaxation of their natural mixed integer programming formulation can be arbitrarily weak. We then derive strong valid inequalities for fluence map optimization problems under dose-volume restrictions using disjunctive programming theory and show that strengthening mixed integer programming formulations with these valid inequalities has significant computational benefits.     

A multiobjective optimization model for water resources planning

A technique is developed for solving multiple objective optimization programs. The approach decomposes the system into groups of objectives according to their priority in the model. A lexicographic ordering (goal programming) approach is used to analyse this system of groups, while the solution structure of each individual group is developed using the method of constraints. The technique is applied to a planning model for river basins.     

A collaboratory for radiation therapy treatment planning optimization research

Intensity modulated radiation therapy treatment planning (IMRTP) is a challenging application of optimization technology. We present software tools to facilitate IMRTP research by computational scientists who may not have convenient access to radiotherapy treatment planning systems. The tools, developed within Matlab and CERR (computational environment for radiotherapy research), allow convenient access, visualization, programmable manipulation, and sharing of patient treatment planning data, as well as convenient generation of dosimetric data needed as input for treatment plan optimization research. CERR/Matlab also provides a common framework for storing, reviewing, sharing, and comparing optimized dose distributions from multiple researchers.     

A robust optimization model for production planning of perishable products

In this study, a robust optimization model is developed to solve production planning problems for perishable products in an uncertain environment in which the setup costs, production costs, labour costs, inventory costs, and workforce changing costs are minimized. Using the concept of postponement, the production process for perishable products is differentiated into two phases to better utilize the resources. By adjusting penalty parameters, decision-makers can determine an optimal production loading plan and better utilize resources while considering different economic growth scenarios. A case from a Hong Kong plush toy company is studied and the characteristics of perishable products are discussed. Numerical results demonstrate the robustness and effectiveness of the proposed model. An analysis of the trade-off between solution robustness and model robustness is also presented.     

Mixed-integer programming techniques for decomposing IMRT fluence maps using rectangular apertures

We consider a matrix decomposition problem arising in Intensity Modulated Radiation Therapy (IMRT). The problem input is a matrix of intensity values that are to be delivered to a patient via IMRT from some given angle, under the condition that the IMRT device can only deliver radiation in rectangular shapes. This paper studies the problem of minimizing the number of rectangles (and their associated intensities) necessary to decompose such a matrix. We propose an integer programming-based methodology for providing lower and upper bounds on the optimal solution, and demonstrate the efficacy of our approach on clinical data.     

A robust optimization model for multi-site production planning problem in an uncertain environment

This paper addresses the multi-site production planning problem for a multinational lingerie company in Hong Kong subject to production import/export quotas imposed by regulatory requirements of different nations, the use of manufacturing factories/locations with regard to customers’ preferences, as well as production capacity, workforce level, storage space and resource conditions at the factories. In this paper, a robust optimization model is developed to solve multi-site production planning problem with uncertainty data, in which the total costs consisting of production cost, labor cost, inventory cost, and workforce changing cost are minimized. By adjusting penalty parameters, production management can determine an optimal medium-term production strategy including the production loading plan and workforce level while considering different economic growth scenarios. The robustness and effectiveness of the developed model are demonstrated by numerical results. The trade-off between solution robustness and model robustness is also analyzed.     

A robust optimization model for multi-product two-stage capacitated production planning under uncertainty

Production planning (PP) is one of the most important issues carried out in manufacturing environments which seeks efficient planning, scheduling and coordination of all production activities that optimizes the company’s objectives. In this paper, we studied a two-stage real world capacitated production system with lead time and setup decisions in which some parameters such as production costs and customer demand are uncertain. A robust optimization model is developed to formulate the problem in which minimization of the total costs including the setup costs, production costs, labor costs, inventory costs, and workforce changing costs is considered as performance measure. The robust approach is used to reduce the effects of fluctuations of the uncertain parameters with regards to all the possible future scenarios. A mixed-integer programming (MIP) model is developed to formulate the related robust production planning problem. In fact the robust proposed model is presented to generate an initial robust schedule. The performance of this schedule could be improved against of any possible occurrences of uncertain parameters. A case from an Iran refrigerator factory is studied and the characteristics of factory and its products are discussed. The computational results display the robustness and effectiveness of the model and highlight the importance of using robust optimization approach in generating more robust production plans in the uncertain environments. The tradeoff between solution robustness and model robustness is also analyzed.     

A robust optimization model for agile and build-to-order supply chain planning under uncertainties

Supply chain planning as one of the most important processes within the supply chain management concept, has a great impact on firms’ success or failure. This paper considers a supply chain planning problem of an agile manufacturing company operating in a build-to-order environment under various kinds of uncertainty. An integrated optimization approach of procurement, production and distribution costs associated with the supply chain members has been taken into account. A robust optimization scenario-based approach is used to absorb the influence of uncertain parameters and variables. The formulation is a robust optimization model with the objective of minimizing the expected total supply chain cost while maintaining customer service level. The developed multi-product, multi-period, multi-echelon robust mixed-integer linear programming model is then solved using the CPLEX optimization studio and guidance related to future areas of research is given.     

A survey of optimization models on cancer chemotherapy treatment planning

While chemotherapy is an effective method for treating cancers such as colorectal cancer, its effectiveness may be dampened by the drug resistance and it may have significant side effects due to the destruction of normal cells during the treatment. As a result, there is a need for research on choosing an optimal chemotherapy treatment plan that minimizes the number of cancerous cells while ensuring that the total toxicity is below an allowable limit. In this paper, we summarize the mathematical models applied to the optimal design of the cancer chemotherapy. We first elaborate on a typical optimization model and classify relevant literature with respect to modeling methods: Optimal control model (OCM) and others. We further classify the OCM models with respect to the solution method used. We discuss the limitations of the existing research and provide several directions for further research in optimizing chemotherapy treatment planning.     

A genetic algorithm with neural network fitness function evaluation for IMRT beam angle optimization

Intensity Modulated Radiotherapy Treatment (IMRT) is a technique used in the treatment of cancer, where the radiation beams are modulated by a multileaf collimator allowing the irradiation of the patient using non-uniform radiation fields from selected angles. Beam angle optimization consists in trying to find the best set of angles that should be used in IMRT planning. The choice of this set of angles is patient and pathology dependent and, in clinical practice, most of the times it is made using a trial and error procedure or simply using equidistantly distributed angles. In this paper we propose a genetic algorithm that aims at calculating good sets of angles in an automated way, given a predetermined number of angles. We consider the discretization of all possible angles in the interval [0 \(^{\circ }\) , 360 \(^{\circ }\) ], and each individual is represented by a chromosome with 360 binary genes. As the calculation of a given individual’s fitness is very expensive in terms of computational time, the genetic algorithm uses a neural network as a surrogate model to calculate the fitness of most of the individuals in the population. To explicitly consider the estimation error that can result from the use of this surrogate model, the fitness of each individual is represented by an interval of values and not by a single crisp value. The genetic algorithm is capable of finding improved solutions, when compared to the usual equidistant solution applied in clinical practice. The genetic algorithm will be described and computational results will be shown.     

Column generation for IMRT cancer therapy optimization with implementable segments

A radiation beam passes through normal tissue to reach tumor. The latest devices for the radiotherapy of cancer provide intensity modulated radiation treatment, or IMRT. This method refines cancer treatment by varying the intensity profile across the face of a radiation beam. Intensity modulation is usually accomplished by partitioning each beam, distinguished by its angle of entry, into an array of smaller sized units, called beamlets, assigned different intensities. Planning treatment calls for an optimization over beamlet intensities to maximize the dose delivered to the targeted tumor while keeping the distribution of dose throughout the various organs within physician prescribed bounds. The choice of beam angles can be entered into the optimization as well. A common method to produce an intensity pattern is to block out different parts of the beam for different amounts of time. This can be done sliding narrow blocks (leafs) of unit width into the beam from either of two opposing sides to create different beam shapes called segments. A sequence of segments with their exposure times is superimposed to yield the dose distribution actually received in the patient. Current two stage treatment is derived in separate steps: optimization over independently considered beamlet intensities, and generation of a sequence of segments to approximate the planned intensity map. The approximation degrades the solution, and the separate search for segments adds to planning time. We present a mixed integer programming alternative employing column generation to optimize dose over segments themselves. Only segments that can be realized with delivery devices are generated, and adjustments made for the effects of block edges, so that the optimized plans are directly implementable. Preliminary testing demonstrates gains in both planning efficiency and quality of the plans produced. 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.     

A light-propagation model for aircraft trajectory planning

Predicted air traffic growth is expected to double the number of flights over the next 20 years. If current means of air traffic control are maintained, airspace capacity will reach its limits. The need for increasing airspace capacity motivates improved aircraft trajectory planning in 4D (space+time). In order to generate sets of conflict-free 4D trajectories, we introduce a new nature-inspired algorithm: the light propagation algorithm (LPA). This algorithm is a wavefront propagation method that yields approximate geodesic solutions (minimal-in-time solutions) for the path planning problem, in the particular case of air-traffic congestion. In simulations, LPA yields encouraging results on real-world traffic over France while satisfying the specific constraints in air-traffic management.     

A planning model for urban housing developments

Summary A planning model for urban housing projects is developed within the framework of systems analysis. The first part gives a cost model of housing projects. Costs are shown to depend on the costs of building sites, construction costs, costs for streets and for parking facilities. The planning model takes factual and legal constraints into consideration. A housing benefit function for the evaluation of urban housing projects is developed by making use of factor analysis. Cost model and benefit model of housing projects are combined in a cost-benefit-analysis for urban planning. The model is shown to be operational by pointing out results derived in an empirical study of a large housing project in Berlin.

---

Zusammenfassung Ein Modell für die Planung öffentlicher Investitionen im Wohnungsbau wird entwickelt. Ausgangspunkt ist eine Systemanalyse der Kosten städtischer Wohngebiete. Die Kosten hängen von den Gebäudekosten, den Grundstückskosten, den Straßenkosten und den Kosten für das gewählte Parksystem ab. Das Planungsmodell berücksichtigt faktische und rechtliche Nebenbedingungen, die der Städteplaner bei seinen Entwürfen zu beachten hat. Ein methodischer Ansatz für die Bewertung städtischer Wohngebiete wird aufgezeigt. Wohnwerte und Kosten werden abschließend in einer Kosten-Nutzen-Analyse städtischer Wohngebiete zusammengefaßt. Die Operationalität des Modells wird an einem praktischen Beispiel nachgewiesen.

---

---

This paper is based on research carried out withO. M. Ungers, A. Tönjes, K. Viebering, M. Wegener, andK. P. Kistner. See for detailsH. Albach andO. M. Ungers:Optimale Wohngebietsplanung, Band I, Wiesbaden 1969.     

A stochastic model for drilling optimization

Drilling optimization problems in oilfields are usually formulated and solved by using deterministic mathematical models, in which uncertain (indeterminate) factors or random issues are not taken into consideration. However, it has been widely experienced that random factors (such as those from soil layers, drill bits, and surface equipment) greatly affect the drilling performance. This paper introduces a new stochastic model for describing such random effects. This model, when used to optimization design, is more practical and provides a better characterization for real oilfield situations as compared with other deterministic models, and has been demonstrated to be more efficient in solving real design problems of drilling optimizations.     

A model for strategic planning under uncertainty

Summary In this paper the multi-period strategic planning problem for a consumer sumer product manufacturing chain is considered. Our discussion is focused on investment decisions which, are economically optimal over the whole planning horizonT, while meeting customer demands and conforming to technological requirements. In strategic planning, time and uncertainty play important roles. The uncertainties in the model are due to different levels of forecast demands, cost estimates and equipment behaviour. The main aim of this paper is to develop and analyse a multiperiod stochastic model representing the entire manufacturing chain, from the acquisitions of raw material to the delivering of final products. The resulting optimization problem is computationally intractable because of the enormous, and sometimes unrealistic, number of scenarios that must be considered in order to identify the optimal planning strategy. We propose two different solution approaches; firstly, we apply a scenario risk analysis giving the related results of experiments on a particular real data set. We then describe and investigate an Integer Stochastic Programming formulation of the problem and propose, as a solution technique, a variation of Benders decomposition method, namely theL-shaped method.     

A multi-periodic optimization formulation for bike planning and bike utilization

The number of policy initiatives to promote the use of bike, or the combined use of bicycle and public transport for one trip, has grown considerably over the past decade as part of the search for more sustainable transport solutions. This paper presents an optimization formulation to design a bike-sharing system for travel inside small communities, or as a means to extend public transport for access and egress trips. The mathematical model attempts to optimize a bike-sharing system by determining the minimum required bike fleet size that minimizes simultaneously unmet demand, unutilized bikes, and the need to transport empty bikes between rental stations to meet demand. The proposed approach is applied to an example problem and is shown to be successful, ultimately providing a new managerial tool for planning and analyzing bike utilization more effectively.