Refine
Year of publication
Document Type
- Preprint (42)
- Report (13)
- Article (1)
- Course Material (1)
- Working Paper (1)
Has Fulltext
- yes (58)
Keywords
- Mathematikunterricht (9)
- Modellierung (9)
- praxisorientiert (9)
- Lineare Algebra (6)
- modelling (6)
- integer programming (4)
- linear algebra (4)
- mathematical education (4)
- praxis orientated (4)
- Intensity modulated radiation therapy (3)
Faculty / Organisational entity
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.
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.
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.
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.
Stop Location Design in Public Transportation Networks: Covering and Accessibility Objectives
(2006)
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.
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.
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.
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.
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.