KLUEDO RSS FeedNeueste Dokumente / Latest documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 19 Jun 2013 08:27:31 +0200Wed, 19 Jun 2013 08:27:31 +0200On the Generality of the Greedy Algorithm for Solving Matroid Base Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535
It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or \(k\)-sum objective functions. Lara Turner; Matthias Ehrgott; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535Wed, 19 Jun 2013 08:27:31 +0200The Multi Terminal q-FlowLoc Problem: A Heuristic
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290
In this paper the multi terminal q-FlowLoc problem (q-MT-FlowLoc) is introduced. FlowLoc problems combine two well-known modeling tools: (dynamic) network flows and locational analysis. Since the q-MT-FlowLoc problem is NP-hard we give a mixed integer programming formulation and propose a heuristic which obtains a feasible solution by calculating a maximum flow in a special graph H. If this flow is also a minimum cost flow, various versions of the heuristic can be obtained by the use of different cost functions. The quality of this solutions is compared.Stephanie Heller; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290Wed, 02 Mar 2011 16:46:24 +0100Universal Shortest Paths
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230
We introduce the universal shortest path problem (Univ-SPP) which generalizes both - classical and new - shortest path problems. Starting with the definition of the even more general universal combinatorial optimization problem (Univ-COP), we show that a variety of objective functions for general combinatorial problems can be modeled if all feasible solutions have the same cardinality. Since this assumption is, in general, not satisfied when considering shortest paths, we give two alternative definitions for Univ-SPP, one based on a sequence of cardinality contrained subproblems, the other using an auxiliary construction to establish uniform length for all paths between source and sink. Both alternatives are shown to be (strongly) NP-hard and they can be formulated as quadratic integer or mixed integer linear programs. On graphs with specific assumptions on edge costs and path lengths, the second version of Univ-SPP can be solved as classical sum shortest path problem.Lara Turner; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230Mon, 16 Aug 2010 11:00:30 +0200Interdisziplinäres Seminar: „Fachdidaktik Chemie und Mathematik“ - Ausarbeitungen und Unterrichtsentwürfe
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2079
Im Sommersemester 2008 führte die AG Optimierung, FB Mathematik zusammen mit dem FB Chemie und dem FB Pädagogik ein interdisziplinäres Seminar zur „Fachdidaktik Chemie und Mathematik“ durch. Durch dieses integrative Lehrveranstaltungskonzept sollte die Nachhaltigkeit der Ausbildung gestärkt und die Verknüpfung von Allgemeiner Didaktik mit der Fachdidaktik sowie zwischen verschiedenen Fachbereichen gefördert werden. In dieser speziellen Veranstaltung erarbeiteten sich die Teilnehmer Inhalte in der Schnittmenge von Chemie und Mathematik, nämlich Kristallgeometrie, Analysis und Titration sowie Graphentheorie und Trennverfahren. Ihre Erkenntnisse wurden im Rahmen von Seminarvorträgen präsentiert und ausgearbeitet. Im folgenden Report befinden sich die Ausarbeitungen, welche Lernziele und Kompetenzen, Sach-, Methodische und Didaktische Analysen sowie Unterrichtsentwürfe umfassen.Florentine Bunke; Horst W. Hamacher; Anne M. Schwahnreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2079Wed, 08 Apr 2009 15:18:45 +0200A Note On Inverse Max Flow Problem Under Chebyshev Norm
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2056
In this paper, we study the inverse maximum flow problem under \(\ell_\infty\)-norm and show that this problem can be solved by finding a maximum capacity path on a modified graph. Moreover, we consider an extension of the problem where we minimize the number of perturbations among all the optimal solutions of Chebyshev norm. This bicriteria version of the inverse maximum flow problem can also be solved in strongly polynomial time by finding a minimum \(s - t\) cut on the modified graph with a new capacity function.Cigdem Güler; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2056Thu, 15 Jan 2009 15:19:44 +0100A new sequential extraction heuristic for optimising the delivery of cancer radiation treatment using multileaf collimators
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1930
Finding a delivery plan for cancer radiation treatment using multileaf collimators operating in ''step-and-shoot mode'' can be formulated mathematically as a problem of decomposing an integer matrix into a weighted sum of binary matrices having the consecutive-ones property - and sometimes other properties related to the collimator technology. The efficiency of the delivery plan is measured by both the sum of weights in the decomposition, known as the total beam-on time, and the number of different binary matrices appearing in it, referred to as the cardinality, the latter being closely related to the set-up time of the treatment. In practice, the total beam-on time is usually restricted to its minimum possible value, (which is easy to find), and a decomposition that minimises cardinality (subject to this restriction) is sought.Davaasteren Baatar; Natashia Boland; Robert Johnston; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1930Fri, 25 Jan 2008 22:43:20 +0100Capacity Inverse Minimum Cost Flow Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1914
Given a directed graph G = (N,A) with arc capacities u and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector u' for the arc set A such that a given feasible flow x' is optimal with respect to the modified capacities. Among all capacity vectors u' satisfying this condition, we would like to find one with minimum ||u' - u|| value. We consider two distance measures for ||u' - u||, rectilinear and Chebyshev distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NP-hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the Chebyshev norm. In the latter case we propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number of affected arcs. We also present computational results for this heuristic.Cigdem Güler; Horst Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1914Mon, 03 Dec 2007 12:01:57 +0100Polyhedral Analysis of Uncapacitated Single Allocation p-Hub Center Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1858
In contrast to p-hub problems with a summation objective (p-hub median), minmax hub problems (p-hub center) have not attained much attention in the literature. In this paper, we give a polyhedral analysis of the uncapacitated single allocation p-hub center problem (USApHCP). The analysis will be based on a radius formulation which currently yields the most efficient solution procedures. We show which of the valid inequalities in this formulation are facet-defining and present non-elementary classes of facets, for which we propose separation problems. A major part in our argumentation will be the close connection between polytopes of the USApHCP and the uncapacitated p-facility location (pUFL). Hence, the new classes of facets can also be used to improve pUFL formulations.Silke Jütte; Elena Gavriliouk; Horst Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1858Thu, 26 Apr 2007 16:11:15 +0200Minimum Cut Bases in Undirected Networks
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1857
Given an undirected, connected network G = (V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as its graph theoretic counterpart, the cycle basis problem. We consider two versions of the problem, the unconstrained and the fundamental cut basis problem. For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem and is thus solvable in strongly polynomial time. The complexity of this algorithm improves the complexity of the best algorithms for the cycle basis problem, such that it is preferable for cycle basis problems in planar graphs. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each, from a spanning tree T is shown to be NP-hard. We present heuristics, integer programming formulations and summarize first experiences with numerical tests.Florentine Bunke; Horst W. Hamacher; Francesco Maffioli; Anne Schwahnpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1857Thu, 26 Apr 2007 16:10:59 +0200Scheduling and Location (ScheLoc): Makespan Problem with Variable Release Dates
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1835
While in classical scheduling theory the locations of machines are assumed to be fixed we will show how to tackle location and scheduling problems simultaneously. Obviously, this integrated approach enhances the modeling power of scheduling for various real-life problems. In this paper, we present in an exemplary way theory and a solution algorithm for a specific type of a scheduling and a rather general, planar location problem, respectively. More general results and a report on numerical tests will be presented in a subsequent paper.Donatas Elvikis; Horst W. Hamacher; Marcel T. Kalschpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1835Sun, 11 Feb 2007 14:52:09 +0100Decomposition of Matrices and Static Multileaf Collimators: A Survey
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1810
Multileaf Collimators (MLC) consist of (currently 20-100) pairs of movable metal leaves which are used to block radiation in Intensity Modulated Radiation Therapy (IMRT). The leaves modulate a uniform source of radiation to achieve given intensity profiles. The modulation process is modeled by the decomposition of a given non-negative integer matrix into a non-negative linear combination of matrices with the (strict) consecutive ones property.Matthias Ehrgott; Horst W. Hamacher; Marc Nußbaumpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1810Tue, 21 Nov 2006 13:41:32 +0100Acquisition Prioritization: A Multicriteria Approach Based on a Case Study
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1798
Selection of new projects is one of the major decision making activities in any company. Given a set of potential projects to invest, a subset which matches the company's strategy and internal resources best has to be selected. In this paper, we propose a multicriteria model for portfolio selection of projects, where we take into consideration that each of the potential projects has several - usually conflicting - values.Horst W. Hamacher; Stefan Ruzika; Akin Tanatmispreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1798Wed, 08 Nov 2006 23:24:46 +0100Semi-Simultaneous Flows and Binary Constrained (Integer) Linear Programs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1753
Linear and integer programs are considered whose coefficient matrices can be partitioned into K consecutive ones matrices. Mimicking the special case of K=1 which is well-known to be equivalent to a network flow problem we show that these programs can be transformed to a generalized network flow problem which we call semi-simultaneous (se-sim) network flow problem. Feasibility conditions for se-sim flows are established and methods for finding initial feasible se-sim flows are derived. Optimal se-sim flows are characterized by a generalization of the negative cycle theorem for the minimum cost flow problem. The issue of improving a given flow is addressed both from a theoretical and practical point of view. The paper concludes with a summary and some suggestions for possible future work in this area.Alexander Engau; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1753Wed, 12 Jul 2006 18:03:36 +0200Hub Cover and Hub Center Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1748
Using covering problems (CoP) combined with binary search is a well-known and successful solution approach for solving continuous center problems. In this paper, we show that this is also true for center hub location problems in networks. We introduce and compare various formulations for hub covering problems (HCoP) and analyse the feasibility polyhedron of the most promising one. Computational results using benchmark instances are presented. These results show that the new solution approach performs better in most examples.Horst W. Hamacher; Tanja Meyerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1748Mon, 03 Jul 2006 19:31:22 +0200Stop Location Design in Public Transportation Networks: Covering and Accessibility Objectives
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1727
In StopLoc we consider the location of new stops along the edges of an existing public transportation network. Examples of StopLoc include the location of bus stops along some given bus routes or of railway stations along the tracks in a railway system. In order to measure the ''convenience'' of the location decision for potential customers in given demand facilities, two objectives are proposed. In the first one, we give an upper bound on reaching a closest station from any of the demand facilities and minimize the number of stations. In the second objective, we fix the number of new stations and minimize the sum of the distances between demand facilities and stations. The resulting two problems CovStopLoc and AccessStopLoc are solved by a reduction to a classical set covering and a restricted location problem, respectively. We implement the general ideas in two different environments - the plane, where demand facilities are represented by coordinates and in networks, where they are nodes of a graph.Dwi Retnani Poetranto; Horst. W. Hamacher; Simone Horn; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1727Mon, 24 Apr 2006 19:02:34 +0200Multiple Objective Minimum Cost Flow Problems: A Review
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1677
In this paper, theory and algorithms for solving the multiple objective minimum cost flow problem are reviewed. For both the continuous and integer case exact and approximation algorithms are presented. In addition, a section on compromise solutions summarizes corresponding results. The reference list consists of all papers known to the autheors which deal with the multiple objective minimum cost flow problem.Horst W. Hamacher; Christian Pedersen; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1677Thu, 27 Oct 2005 16:08:17 +0200Finding Representative Systems for Discrete Bicriteria Optimization Problems by Box Algorithms
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1655
Given a discrete bicriteria optimization problem (DBOP), we propose two versions of an approximation procedure, the box algorithm, which results in a representation of the complete set of nondominated solutions by a finite representative system Rep satisfying the following quality features.Horst W. Hamacher; Christian Roed Pedersen; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1655Wed, 17 Aug 2005 16:14:06 +0200Decomposition of Integer Matrices and Multileaf Collimator Sequencing
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1582
In this paper we consider the problem of decomposing an integer matrix into a weighted sum of binary matrices that have to strict consecutive ones property.Davaatseren Baatar; Horst W. Hamacher; Matthias Ehrgott; Gerhard J. Woegingerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1582Mon, 08 Nov 2004 11:12:15 +0100Algorithms for Time-Dependent Bicriteria Shortest Path Problems (revised version)
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1581
In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature.Horst W. Hamacher; Stefan Ruzika; Stevanus A. Tjandrapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1581Thu, 28 Oct 2004 13:21:33 +0200Algorithms for Time Dependent Bicriteria Shortest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1450
We generalize the classical shortest path problem in two ways. We consider two - in general contradicting - objective functions and introduce a time dependency of the cost which is caused by a traversal time on each arc. The resulting problem, called time-dependent bicriteria shortest path problem (TdBiSP) has several interesting practical applications, but has not attained much attention in the literature.Horst W. Hamacher; Stevanus A. Tjandrapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1450Wed, 12 Nov 2003 14:23:26 +0100Earliest Arrival Flows with Time-Dependent Data
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1449
In this paper we discuss an earliest arrival flow problem of a network having arc travel times and capacities that vary with time over a finite time horizon T. We also consider the possibility to wait (or park) at a node before departingon outgoing arc. This waiting is bounded by the value of maximum waiting time and the node capacity which also vary with time.Horst W. Hamacher; Stevanus A. Tjandrapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1449Wed, 12 Nov 2003 12:49:13 +0100Optimizacíon lineal en las clases de matemáticas
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1431
Las matemáticas son atribuidas en general a algo no claro y sólo para matemáticos. La imagen de las matemáticas para los escolares, es la de una ciencia, la cual se sirve sólo de si misma. Es importante hacer frente al prejuicio de que las matemáticas distan lejos de toda utilidad práctica. La matemática es una ciencia al servicio de todas las dem´as ciencias, de cuya ayuda se necesita en casi todos los campos de la vida. La matemática de la escuela debería despertar en cualquier ámbito de la vida de los escolares el interés sobre ...Horst W. Hamacher; Stefanie Müllerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1431Sat, 13 Sep 2003 10:49:54 +0200Linear Optimization in School Mathematics
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1430
Linear Optimization is an important area from applied mathematics. A lot of practical problems can be modelled and solved with this technique. This publication shall help to introduce this topic to pupils. The process of modelling, the reduction of problems to their significant attributes shall be described. The linear programms will be solved by using the simplex method. Many examples illustrate the topic.Horst W. Hamacher; Stefanie Müllerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1430Sat, 13 Sep 2003 10:47:10 +0200Lista de productos y álgebra lineal
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1429
A mediados del año 1997 la publicación de los denominados TIMMS-Estudios (Third International Mathematics and Science Study) causó un importante impacto en el público alemán. El motivo de esto fue el rendimiento escolar conseguido en la rama de matemáticas y ciencias naturales del octavo curso, el cual estaba situado en un campo internacional, donde particularmente en el ámbito matemático el conjunto de los estados del norte-, oeste-, y del este de Europa que forman parte del TIMSS - sin mencionar a la mayoría de los paises asiáticos - habían conseguido claramente mejores rendimiento. En definitiva mostraban un peor rendimiento los escolares alemanes con respecto a los paises vecinos y con los ....Florentine Bunke; Horst W. Hamacher; Andreas Maurer; Stefanie Müllerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1429Sat, 13 Sep 2003 10:41:07 +0200Bills of material and linear algebra
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1428
This publication tries to develop mathematical subjects for school from realistic problems. The center of this report are business planning and decision problems which occur in almost all companies. The main topics are: Calculation of raw material demand for given orders, consumption of existing stock and the lot sizing.Florentine Bunke; Horst W. Hamacher; Andreas Maurer; Stefanie Müllerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1428Sat, 13 Sep 2003 10:33:05 +0200