### Refine

#### Year of publication

#### Document Type

- Preprint (37)
- Report (8)
- Working Paper (1)

#### Language

- English (46) (remove)

#### Keywords

- integer programming (4)
- Intensity modulated radiation therapy (3)
- Mathematikunterricht (3)
- Modellierung (3)
- modelling (3)
- praxisorientiert (3)
- Beam-on time (2)
- Combinatorial optimization (2)
- Decomposition cardinality (2)
- Field splitting (2)
- Lineare Algebra (2)
- Multileaf collimator sequencing (2)
- facets (2)
- hub location (2)
- linear algebra (2)
- mathematical education (2)
- network flows (2)
- praxis orientated (2)
- valid inequalities (2)
- (dynamic) network flows (1)
- Algorithmics (1)
- Approximation (1)
- Box Algorithms (1)
- Continuous Location (1)
- Decision support (1)
- Decomposition of integer matrices (1)
- Discrete Bicriteria Optimization (1)
- Dynamic cut (1)
- Earliest arrival augmenting path (1)
- Education (1)
- Finite Dominating Sets (1)
- FlowLoc (1)
- Gauge Distances (1)
- Graph coloring (1)
- Greedy Algorithm (1)
- Greedy algorithm (1)
- Grid Graphs (1)
- Hierarchies (1)
- Label correcting algorithm (1)
- Label setting algorithm (1)
- Lineare Optimierung (1)
- Location Theory (1)
- Location problems (1)
- Locational Planning (1)
- Machine Scheduling (1)
- Matroids (1)
- Multicriteria optimization (1)
- Multiple criteria analysis (1)
- Multiple criteria optimization (1)
- Multiple objective optimization (1)
- Network flows (1)
- Polyhedral Gauges (1)
- Project prioritization (1)
- Project selection (1)
- Rehabilitation clinics (1)
- Representation (1)
- Sandwich Algorithm (1)
- Scheduling (1)
- Simplex (1)
- Standortplanung (1)
- Stücklisten (1)
- Timetabling (1)
- Uniform matroids (1)
- Universal objective function (1)
- bicriteria shortest path problem (1)
- bills of materials (1)
- branch and cut (1)
- cancer (1)
- cancer radiation therapy (1)
- cardinality constraint combinatorial optimization (1)
- center and median problems (1)
- computational complexity (1)
- consecutive ones matrix (1)
- consecutive ones property (1)
- cut basis problem (1)
- efficient solution (1)
- facility location (1)
- graph and network algorithm (1)
- heuristic (1)
- hub covering (1)
- intensity map segmentation (1)
- inverse mathematical models (1)
- inverse optimization (1)
- k-cardinality minimum cut (1)
- label setting algorithm (1)
- linear optimization (1)
- linear programming (1)
- location theory (1)
- locational analysis (1)
- matrix decomposition (1)
- maximum capacity path (1)
- maximum flows (1)
- minimum cut (1)
- multileaf collimator (1)
- multileaf collimator sequencing (1)
- multiliead collimator sequencing (1)
- multiple objective linear programming problem (1)
- network flow (1)
- network location (1)
- optimization (1)
- radiation therapy (1)
- radiotherapy (1)
- representative systems (1)
- scheduling theory (1)
- shortest path problem (1)
- simplex (1)
- sink location (1)
- time-dependent shortest path problem (1)
- treatment planning (1)
- universal objective function (1)
- variable cardinality case (1)

#### Faculty / Organisational entity

- Fachbereich Mathematik (43)
- Fraunhofer (ITWM) (3)

Weighted k-cardinality trees
(1992)

We consider the k -CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil-field leasing and facility layout. While the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k-CARD TREE, and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex huLl of the integer solutions is studied.

Max ordering (MO) optimization is introduced as tool for modelling production
planning with unknown lot sizes and in scenario modelling. In MO optimization a feasible solution set \(X\) and, for each \(x\in X, Q\) individual objective functions \(f_1(x),\dots,f_Q(x)\) are given. The max ordering objective
\(g(x):=max\) {\(f_1(x),\dots,f_Q(x)\)} is then minimized over all \(x\in X\).
The paper discusses complexity results and describes exact and approximative
algorithms for the case where \(X\) is the solution set of combinatorial
optimization problems and network flow problems, respectively.

We investigate two versions of multiple objective minimum spanning tree
problems defined on a network with vectorial weights. First, we want to minimize the maximum of Q linear objective functions taken over the set of all spanning trees (max linear spanning tree problem ML-ST). Secondly, we look for efficient spanning trees (multi criteria spanning tree problem MC-ST). Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance
between two consecutive solutions is less than a given accuracy.

Finding "good" cycles in graphs is a problem of great interest in graph theory as well as in locational analysis. We show that the center and median problems are NP hard in general graphs. This result holds both for the variable cardinality case (i.e. all cycles of the graph are considered) and the fixed cardinality case (i.e. only cycles with a given cardinality p are feasible). Hence it is of interest to investigate special cases where the problem is solvable in polynomial time. In grid graphs, the variable cardinality case is, for instance, trivially solvable if the shape of the cycle can be chosen freely. If the shape is fixed to be a rectangle one can analyse rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a com plete characterization of the optimal cycles and closed form expressions of the optimal objective values are given, yielding polynomial time algorithms for all cases of center rectangle problems. Finally, it is shown that center cycles can be chosen as rectangles for small cardinalities such that the center cycle problem in grid graphs is in these cases completely solved.

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.

Location problems with Q (in general conflicting) criteria are considered. After reviewing previous results of the authors dealing with lexicographic and Pareto location the main focus of the paper is on max-ordering locations. In these location problems the worst of the single objectives is minimized. After discussing some general results (including reductions to single criterion problems and the relation to lexicographic and Pareto locations) three solution techniques are introduced and exemplified using one location problem class, each: The direct approach, the decision space approach and the objective space approach. In the resulting solution algorithms emphasis is on the representation of the underlying geometric idea without fully exploring the computational complexity issue. A further specialization of max-ordering locations is obtained by introducing lexicographic max-ordering locations, which can be found efficiently. The paper is concluded by some ideas about future research topics related to max-ordering location problems.

The Weber problem for a given finite set of existing facilities {cal E}x = {Ex_1,Ex_2, ... ,Ex_M} subset R^2 with positive weights w_m (m = 1, ... ,M) is to find a new facility X* in R^2 such that sum_{m=1}^{M} w_{m}d(X,Ex_m) is minimized for some distance function d. In this paper we consider distances defined by polyhedral gauges. A variation of this problem is obtained if barriers are introduced which are convex polygonal subsets of the plane where neither location of new facilities nor traveling is allowed. Such barriers like lakes, military regions, national parks or mountains are frequently encountered in practice.From a mathematical point of view barrier problems are difficult, since the prensence of barriers destroys the convexity of the objective function. Nevertheless, this paper establishes a descretization result: One of the grid points in the grid defined by the existing facilities and the fuundamental directions of the gauge distances can be proved to be an optimal location. Thus the barrier problem can be solved with a polynomial algorithm.

The problem of finding an optimal location X* minimizing the maximum Euclidean distance to existing facilities is well solved by e.g. the Elzinga-Hearn algorithm. In practical situations X* will however often not be feasible. We therefore suggest in this note a polynomial algorithm which will find an optimal location X^F in a feasible subset F of the plane R^2

In this paper network location problems with several objectives are discussed, where every single objective is a classical median objective function. We will lock at the problem of finding Pareto optimal locations and lexicographically optimal locations. It is shown that for Pareto optimal locations in undirected networks no node dominance result can be shown. Structural results as well as efficient algorithms for these multi-criteria problems are developed. In the special case of a tree network a generalization of Goldman's dominance algorithm for finding Pareto locations is presented.

There are several good reasons to introduce classification schemes for optimization problems including, for instance, the ability for concise problem statement opposed to verbal, often ambiguous, descriptions or simple data encoding and information retrieval in bibliographical information systems or software libraries. In some branches like scheduling and queuing theory classification is therefore a widely accepted and appreciated tool. The aim of this paper is to propose a 5-position classification which can be used to cover all location problems. We will provide a list of currentliy available symbols and indicate its usefulness in a - necessarily non-comprehensive - list of classical location problems. The classification scheme is in use since 1992 and has since proved to be useful in research, software development, classroom, and for overview articles.