KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 04 May 2011 15:59:41 +0200Wed, 04 May 2011 15:59:41 +0200Modeling profit sharing in combinatorial exchanges by network flows
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2317
In this paper we study the possibilities of sharing profit in combinatorial procurement auctions and exchanges. Bundles of heterogeneous items are offered by the sellers, and the buyers can then place bundle bids on sets of these items. That way, both sellers and buyers can express synergies between items and avoid the well-known risk of exposure (see, e.g., [3]). The reassignment of items to participants is known as the Winner Determination Problem (WDP). We propose solving the WDP by using a Set Covering formulation, because profits are potentially higher than with the usual Set Partitioning formulation, and subsidies are unnecessary. The achieved benefit is then to be distributed amongst the participants of the auction, a process which is known as profit sharing. The literature on profit sharing provides various desirable criteria. We focus on three main properties we would like to guarantee: Budget balance, meaning that no more money is distributed than profit was generated, individual rationality, which guarantees to each player that participation does not lead to a loss, and the core property, which provides every subcoalition with enough money to keep them from separating. We characterize all profit sharing schemes that satisfy these three conditions by a monetary flow network and state necessary conditions on the solution of the WDP for the existence of such a profit sharing. Finally, we establish a connection to the famous VCG payment scheme [2, 8, 19], and the Shapley Value [17].H. Ackermann; H. Ewe; K.-H. Küfer; M. Schröderreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2317Wed, 04 May 2011 15:59:41 +0200Trade-off bounds and their effect in multi-criteria IMRT planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2140
One approach to multi-criteria IMRT planning is to automatically calculate a data set of Pareto-optimal plans for a given planning problem in a first phase, and then interactively explore the solution space and decide for the clinically best treatment plan in a second phase. The challenge of computing the plan data set is to assure that all clinically meaningful plans are covered and that as many as possible clinically irrelevant plans are excluded to keep computation times within reasonable limits. In this work, we focus on the approximation of the clinically relevant part of the Pareto surface, the process that consititutes the first phase. It is possible that two plans on the Parteto surface have a very small, clinically insignificant difference in one criterion and a significant difference in one other criterion. For such cases, only the plan that is clinically clearly superior should be included into the data set. To achieve this during the Pareto surface approximation, we propose to introduce bounds that restrict the relative quality between plans, so called tradeoff bounds. We show how to integrate these trade-off bounds into the approximation scheme and study their effects.J. I. Serna; M. Monz; K.-H. Küfer; C. Thiekereporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2140Fri, 16 Oct 2009 08:57:36 +0200A constraint programming approach for the two-dimensional rectangular packing problem with orthogonal orientations
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2046
We propose a constraint-based approach for the two-dimensional rectangular packing problem with orthogonal orientations. This problem is to arrange a set of rectangles that can be rotated by 90 degrees into a rectangle of minimal size such that no two rectangles overlap. It arises in the placement of electronic devices during the layout of 2.5D System-in-Package integrated electronic systems. Moffitt et al. [8] solve the packing without orientations with a branch and bound approach and use constraint propagation. We generalize their propagation techniques to allow orientations. Our approach is compared to a mixed-integer program and we provide results that outperform it.M. Berger; M. Schröder; K.-H. Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2046Thu, 15 Jan 2009 15:21:01 +0100A novel non-linear approach to minimal area rectangular packing
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1981
This paper disscuses the minimal area rectangular packing problem of how to pack a set of specified, non-overlapping rectangels into a rectangular container of minimal area. We investigate different mathematical programming approaches of this and introduce a novel approach based on non-linear optimization and the \\\"tunneling effect\\\" achieved by a relaxation of the non-overlapping constraints.V. Maag; M. Berger; A. Winterfeld; K.-H. Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1981Wed, 18 Jun 2008 15:29:02 +0200Pareto navigation – systematic multicriteria-based IMRT treatment plan determination
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1982
Background and purpose Inherently, IMRT treatment planning involves compromising between different planning goals. Multi-criteria IMRT planning directly addresses this compromising and thus makes it more systematic. Usually, several plans are computed from which the planner selects the most promising following a certain procedure. Applying Pareto navigation for this selection step simultaneously increases the variety of planning options and eases the identification of the most promising plan. Material and methods Pareto navigation is an interactive multi-criteria optimization method that consists of the two navigation mechanisms “selection” and “restriction”. The former allows the formulation of wishes whereas the latter allows the exclusion of unwanted plans. They are realized as optimization problems on the so-called plan bundle – a set constructed from precomputed plans. They can be approximately reformulated so that their solution time is a small fraction of a second. Thus, the user can be provided with immediate feedback regarding his or her decisions.M. Monz; K.-H. Küfer; T. Bortfeld; C. Thiekereporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1982Wed, 18 Jun 2008 15:28:56 +0200Smooth intensity maps and the Bortfeld-Boyer sequencer
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1962
It has been empirically verified that smoother intensity maps can be expected to produce shorter sequences when step-and-shoot collimation is the method of choice. This work studies the length of sequences obtained by the sequencing algorithm by Bortfeld and Boyer using a probabilistic approach. The results of this work build a theoretical foundation for the up to now only empirically validated fact that if smoothness of intensity maps is considered during their calculation, the solutions can be expected to be more easily applied.Ph. Süss; K.-H. Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1962Wed, 28 May 2008 10:22:43 +0200Balancing control and simplicity: a variable aggregation method in intensity modulated radiation therapy planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1953
It is commonly believed that not all degrees of freedom are needed to produce good solutions for the treatment planning problem in intensity modulated radiotherapy treatment (IMRT). However, typical methods to exploit this fact have either increased the complexity of the optimization problem or were heuristic in nature. In this work we introduce a technique based on adaptively refining variable clusters to successively attain better treatment plans. The approach creates approximate solutions based on smaller models that may get arbitrarily close to the optimal solution. Although the method is illustrated using a specific treatment planning model, the components constituting the variable clustering and the adaptive refinement are independent of the particular optimization problem.Ph. Süss; K.-H. Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1953Mon, 19 May 2008 13:50:33 +0200A dynamic algorithm for beam orientations in multicriteria IMRT planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1806
For the last decade, optimization of beam orientations in intensitymodulated radiation therapy (IMRT) has been shown to be successful in improving the treatment plan. Unfortunately, the quality of a set of beam orientations depends heavily on its corresponding beam intensity proles. Usually, a stochastic selector is used for optimizing beam orientation, and then a single objective inverse treatment planning algorithm is used for the optimization of beam intensity proles. The overall time needed to solve the inverse planning for every random selection of beam orientations becomes excessive. Recently, considerable improvement has been made in optimizing beam intensity proles by using multiple objective inverse treatment planning. Such an approach results in a variety of beam intensity proles for every selection of beam orientations, making the dependence between beam orientations and its intensity proles less important. We take advantage of this property to present a dynamic algorithm for beam orientation in IMRT which is based on multicriteria inverse planning. The algorithm approximates beam intensity proles iteratively instead of doing it for every selection of beam orientation, saving a considerable amount of calculation time. Every iteration goes from an N-beam plan to a plan with N + 1 beams. Beam selection criteria are based on a score function that minimizes the deviation from the prescribed dose, in addition to a reject-accept criterion. To illustrate the eciency of the algorithm it has been applied to an articial example where optimality is trivial and to three real clinical cases: a prostate carcinoma, a tumor in the head and neck region and a paraspinal tumor. In comparison to the standard equally spaced beam plans, improvements are reported in all of the three clinical examples, even, in some cases with a fewer number of beams.S. Azizi Sultan; K.-H. Küferreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1806Wed, 15 Nov 2006 15:03:38 +0100Multicriteria optimization in intensity modulated radiotherapy planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1649
Inverse treatment planning of intensity modulated radiothrapy is a multicriteria optimization problem: planners have to find optimal compromises between a sufficiently high dose in tumor tissue that garantuee a high tumor control, and, dangerous overdosing of critical structures, in order to avoid high normal tissue complcication problems. The approach presented in this work demonstrates how to state a flexible generic multicriteria model of the IMRT planning problem and how to produce clinically highly relevant Pareto-solutions. The model is imbedded in a principal concept of Reverse Engineering, a general optimization paradigm for design problems. Relevant parts of the Pareto-set are approximated by using extreme compromises as cornerstone solutions, a concept that is always feasible if box constraints for objective funtions are available. A major practical drawback of generic multicriteria concepts trying to compute or approximate parts of the Pareto-set is the high computational effort. This problem can be overcome by exploitation of an inherent asymmetry of the IMRT planning problem and an adaptive approximation scheme for optimal solutions based on an adaptive clustering preprocessing technique. Finally, a coherent approach for calculating and selecting solutions in a real-timeinteractive decision-making process is presented. The paper is concluded with clinical examples and a discussion of ongoing research topics.K.-H. Küfer; M. Monz; A. Scherrer; P. Süss; F. Alonso; A.S.A. Sultan; Th. Bortfeld; D. Craft; Chr. Thiekereporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1649Tue, 05 Jul 2005 14:45:16 +0200IMRT planning on adaptive volume structures – a significant advance of computational complexity
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1553
In intensity-modulated radiotherapy (IMRT) planning the oncologist faces the challenging task of finding a treatment plan that he considers to be an ideal compromise of the inherently contradictive goals of delivering a sufficiently high dose to the target while widely sparing critical structures. The search for this a priori unknown compromise typically requires the computation of several plans, i.e. the solution of several optimization problems. This accumulates to a high computational expense due to the large scale of these problems - a consequence of the discrete problem formulation. This paper presents the adaptive clustering method as a new algorithmic concept to overcome these difficulties. The computations are performed on an individually adapted structure of voxel clusters rather than on the original voxels leading to a decisively reduced computational complexity as numerical examples on real clinical data demonstrate. In contrast to many other similar concepts, the typical trade-off between a reduction in computational complexity and a loss in exactness can be avoided: the adaptive clustering method produces the optimum of the original problem. This flexible method can be applied to both single- and multi-criteria optimization methods based on most of the convex evaluation functions used in practiceA. Scherrer; K.-H. Küfer; M. Monz; F. Alonso; T. Bortfeldreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1553Mon, 26 Jul 2004 10:54:03 +0200Intensity-Modulated Radiotherapy - A Large Scale Multi-Criteria Programming Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1500
Radiation therapy planning is always a tight rope walk between dangerous insufficient dose in the target volume and life threatening overdosing of organs at risk. Finding ideal balances between these inherently contradictory goals challenges dosimetrists and physicians in their daily practice. Today’s planning systems are typically based on a single evaluation function that measures the quality of a radiation treatment plan. Unfortunately, such a one dimensional approach cannot satisfactorily map the different backgrounds of physicians and the patient dependent necessities. So, too often a time consuming iteration process between evaluation of dose distribution and redefinition of the evaluation function is needed. In this paper we propose a generic multi-criteria approach based on Pareto’s solution concept. For each entity of interest - target volume or organ at risk a structure dependent evaluation function is defined measuring deviations from ideal doses that are calculated from statistical functions. A reasonable bunch of clinically meaningful Pareto optimal solutions are stored in a data base, which can be interactively searched by physicians. The system guarantees dynamical planning as well as the discussion of tradeoffs between different entities. Mathematically, we model the upcoming inverse problem as a multi-criteria linear programming problem. Because of the large scale nature of the problem it is not possible to solve the problem in a 3D-setting without adaptive reduction by appropriate approximation schemes. Our approach is twofold: First, the discretization of the continuous problem is based on an adaptive hierarchical clustering process which is used for a local refinement of constraints during the optimization procedure. Second, the set of Pareto optimal solutions is approximated by an adaptive grid of representatives that are found by a hybrid process of calculating extreme compromises and interpolation methods.T. Bortfeld; K-H. Küfer; M. Monz; A. Scherrer; C. Thieke; H. Trinkhausreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1500Tue, 10 Feb 2004 09:55:04 +0100Inverse radiation therapy planning a multiple objective optimisation approach
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/847
For some decades radiation therapy has been proved successful in cancer treatment. It is the major task of clinical radiation treatment planning to realise on the one hand a high level dose of radiation in the cancer tissue in order to obtain maximum tumour control. On the other hand it is obvious that it is absolutely necessary to keep in the tissue outside the tumour, particularly in organs at risk, the unavoidable radiation as low as possible. No doubt, these two objectives of treatment planning high level dose in the tumour, low radiation outside the tumour have a basically contradictory nature. Therefore, it is no surprise that inverse mathematical models with dose distribution bounds tend to be infeasible in most cases. Thus, there is need for approximations compromising between overdosing the organs at risk and underdosing the target volume. Differing from the currently used time consuming iterative approach, which measures deviation from an ideal (non-achievable) treatment plan using recursively trial-and-error weights for the organs of interest, we go a new way trying to avoid a priori weight choices and consider the treatment planning problem as a multiple objective linear programming problem: with each organ of interest, target tissue as well as organs at risk, we associate an objective function measuring the maximal deviation from the prescribed doses. We build up a data base of relatively few efficient solutions representing and approximating the variety of Pareto solutions of the multiple objective linear programming problem. This data base can be easily scanned by physicians looking for an adequate treatment plan with the aid of an appropriate online tool.Horst W. Hamacher; K.-H. Küferpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/847Mon, 03 Apr 2000 00:00:00 +0200