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 +0200Universal 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 +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 +0100Minimum 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 +0100Integrated Scheduling and Location Models: Single Machine Makespan Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1335
Scheduling and location models are often used to tackle problems in production, logistics, and supply chain management. Instead of treating these models independent of each other, as is usually done in the literature, we consider in this paper an integrated model in which the locations of machines define release times for jobs. Polynomial solution algorithms are presented for single machine problems in which the scheduling part can be solved by the earliest release time rule.Holger Hennes; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1335Mon, 10 Jun 2002 00:00:00 +0200Minimizing Beam-On Time in Cancer Radiation Treatment Using Multileaf Collimators
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1279
Natashia Boland; Horst W. Hamacher; Frank Lenzenpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1279Sun, 10 Feb 2002 00:00:00 +0100Stücklisten und lineare Algebra
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1268
Mit der vorliegenden Veröffentlichung soll der Versuch unternommen werden, mathematischen Schulstoff aus konkreten Problemen herzuentwickeln. Im Mittelpunkt der vorliegenden Arbeit stehen betriebswirtschaftliche Planungs- und Entscheidungsprobleme, wie sie von fast allen Wirtschaftsunternehmen zu lösen sind. Dabei wird im besonderen auf folgende Optimierungsprobleme eingegangen: Berechnung des Rohstoffbedarfs bei gegebenen Bestellungen, Aufarbeitung von vorhandenen Lagerbeständen und das Stücklistenproblem.Florentine Bunke; Horst W. Hamacher; Andreas Maurer; Stefanie Müllerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1268Thu, 06 Dec 2001 00:00:00 +0100Standortplanung im Mathematikunterricht
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1266
Fragestellungen der Standortplanung sollen den Mathematikunterricht der Schule bereichern, dort behandelt und gelöst werden. In dieser Arbeit werden planare Standortprobleme vorgestellt, die im Mathematikunterricht behandelt werden können. Die Probleme Produktion von Halbleiterplatinen, Planung eines Feuerwehrhauses und das Zentrallagerproblem, die ausnahmlos real und nicht konstruiert sind, werden ausführlich durchgearbeitet, so dass es schnell möglich ist, daraus Unterrichtseinheiten zu entwickeln.Matthias Ehrgott; Angela Euteneuer; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1266Fri, 30 Nov 2001 00:00:00 +0100Locating New Stops in a Railway Network
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1209
Given a railway network together with information on the population and their use of the railway infrastructure, we are considering the e ffects of introducing new train stops in the existing railway network. One e ffect concerns the accessibility of the railway infrastructure to the population, measured in how far people live from their nearest train stop. The second effect we study is the change in travel time for the railway customers that is induced by new train stops. Based on these two models, we introduce two combinatorial optimization problems and give NP-hardness results for them. We suggest an algorithmic approach for the model based on travel time and give first experimental results.Horst W. Hamacher; Annegret Liebers; Anita Schöbel; Dorothea Wagner; Frank Wagnerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1209Thu, 10 May 2001 00:00:00 +0200Some Complexity Results for k-Cardinality Minimum Cut Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1140
Many polynomially solvable combinatorial optimization problems (COP) become NP when we require solutions to satisfy an additional cardinality constraint. This family of problems has been considered only recently. We study a newproblem of this family: the k-cardinality minimum cut problem. Given an undirected edge-weighted graph the k-cardinality minimum cut problem is to find a partition of the vertex set V in two sets V 1 , V 2 such that the number of the edges between V 1 and V 2 is exactly k and the sum of the weights of these edges is minimal. A variant of this problem is the k-cardinality minimum s-t cut problem where s and t are fixed vertices and we have the additional request that s belongs to V 1 and t belongs to V 2 . We also consider other variants where the number of edges of the cut is constrained to be either less or greater than k. For all these problems we show complexity results in the most significant graph classes.Maurizio Bruglieri; Matthias Ehrgott; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1140Thu, 07 Sep 2000 00:00:00 +0200Polyhedral Properties of the Uncapacitated Multiple Allocation Hub Location Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1132
We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet defining. We show its superior computational performance by benchmarking it on a well known data set.Horst W. Hamacher; Martine Labbé; Stefan Nickel; Tim Sonnebornpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1132Tue, 29 Aug 2000 00:00:00 +0200Multicriteria network location problems with sumb objectives
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/487
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.Horst W. Hamacher; Stefan Nickel; Martine Labbepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/487Mon, 03 Apr 2000 00:00:00 +0200