liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Holmberg, Kaj, ProfessorORCID iD iconorcid.org/0000-0001-5907-0087
Publications (10 of 70) Show all publications
Olsson, P.-M. & Holmberg, K. (2020). Exploiting parallelization and synergy in derivative free optimization. Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Exploiting parallelization and synergy in derivative free optimization
2020 (English)Report (Other academic)
Abstract [en]

Real life optimization often concerns difficult objective functions, in two aspects, namely that gradients are unavailable, and that evaluation of the objective function takes a long time. Such problems are often attacked with model building algorithms, where an approximation of the function is constructed and solved, in order to find a new promising point to evaluate. We study several ways of saving time by using parallel calculations in the context of model building algorithms, which is not trivial, since such algorithms are inherently sequential. We present a number of ideas that has been implemented and tested on a large number of known test functions, and a few new ones. The computational results reveal that some ideas are quite promising.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2020. p. 18
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2020:4
Keywords
Derivative-free optimization, parallel algorithms, applications of mathematical programming
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-164133 (URN)LiTH-MAT-R--2020/04--SE (ISRN)
Available from: 2020-03-06 Created: 2020-03-06 Last updated: 2020-03-12Bibliographically approved
Holmberg, K. (2020). Optimal proportional representation. Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Optimal proportional representation
2020 (English)Report (Other academic)
Abstract [en]

In a democratic proportional election system, it is vital that the mandates in the parliament are allocated as proportionally as possible to the number of votes the parties got in the election. We formulate an optimization model for allocation of seats in a parliament so as to minimize the disproportionality. By applying separable programming techniques, we obtain an easily solvable problem, and present a method for solving it optimally. The obtained solution is the feasible solution that has the minimal disproportionality (with the measure chosen), even in the presence of a parliament threshold, which is not always the case for the practical procedures used in many countries. We apply the approach to real life data from the last three elections in Sweden, and show that the result is better, i.e. more proportional, than what was obtained with the modified Sainte-Laguë method, which is presently used. A natural suggestion would be to use our method instead.

We also consider the issue about constituencies, and suggest a procedure, based on the same kind of optimization problem, for allocating mandates in the constituencies, without changing the overall allocation with respect to parties. The numbers of mandates for the constituencies are based on the number of votes given, not on estimated numbers of inhabitants entitled to vote. This removes the need for compensatory mandates, and makes the question about sizes of the constituencies less important.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2020
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2020:3
Keywords
OR in government; democracy; proportional representation; Gallagher index; Sainte-Laguë index
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-164134 (URN)LiTH-MAT-R--2020/03--SE (ISRN)
Available from: 2020-03-06 Created: 2020-03-06 Last updated: 2020-03-12Bibliographically approved
Holmberg, K. (2019). A new method for optimal proportional representation. Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>A new method for optimal proportional representation
2019 (English)Report (Other academic)
Abstract [en]

In a democratic proportional election system, it is vital that the mandates in the parliament are allocated as proportionally as possible to the number of votes the parties got in the election. We formulate an optimization model for allocation of seats in a parliament so as to minimize the disproportionality. By applying separable programming techniques, we obtain an easily solvable problem, and present a method for solving it optimally. The obtained solution is thus the feasible solution that has the minimal disproportionality (with the measure chosen), in contrast to the heuristic procedures used in many countries. We apply the approach to real life data from the last three elections in Sweden, and show that the result is better, i.e. more proportional, than what was obtained with the “adjusted odd number rule”, which is presently used. A natural suggestion would be to use our method instead.

We also consider the issue about constituencies, and suggest a procedure, based on the same kind of optimization problem, for allocating mandates in the constituencies, without changing the overall allocation with respect to parties. In our approach, the numbers of mandates for the constituencies are based on the number of votes given, not on estimated numbers of inhabitants. This removes the need for fixed and equalization mandates, and also makes the question about sizes of the constituencies less important.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2019. p. 20
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2019:1
Keywords
Democracy, proportional representation, the adjusted odd number rule
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-154458 (URN)LiTH-MAT-R--2019/01--SE (ISRN)
Available from: 2019-02-13 Created: 2019-02-13 Last updated: 2019-02-26Bibliographically approved
Holmberg, K. (2018). Prepared Test Instances Extracted from OpenStreetMapData Using Different Network Reductions. Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Prepared Test Instances Extracted from OpenStreetMapData Using Different Network Reductions
2018 (English)Report (Other academic)
Abstract [en]

We investigate the effect of different reductions when importing networksfrom OpenStreetMap data. We describe the network reductions and report computationaltests for doing the network extraction and reduction. We also show the effect ofthe reductions by solving a few standard optimization problems in the resulting networks.Computational tests show that the reductions have a dramatic effect on thenetwork size and the time needed for solving the optimization problems. In many cases,the reductions are necessary in order to be able to solve the optimization problem inreasonable time. A practical result of this work is a set of networks that will be usedas benchmarks in future research, and are publically available for other researchers.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2018. p. 25
Series
LiTH-MAT-R, ISSN 0348-2960 ; 4
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-147333 (URN)LiTH-MAT-R--2018/04--SE (ISRN)
Available from: 2018-04-18 Created: 2018-04-18 Last updated: 2018-04-26Bibliographically approved
Holmberg, K. (2016). Projecting points on the convex hull. Linköping University Electronic Press
Open this publication in new window or tab >>Projecting points on the convex hull
2016 (English)Report (Other academic)
Abstract [en]

We discuss the problem of projecting points on their convex hull. Points in the interior of the convex hull are moved outwards to the boundary of the convex hull. While finding the convex hull is a well treated problem, projecting each interior point on the convex hull is not. It is a harder problem, since each point has to be treated. We first discuss a solution approach in two dimensions, and then generalize it to three dimensions. After some significant improvements and changes, we arrive at efficient solutions method for the three dimensional case, using various column and/or constraint generation techniques.

Place, publisher, year, edition, pages
Linköping University Electronic Press, 2016. p. 51
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2016:06
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-128202 (URN)LiTH-MAT-R--2016/06--SE (ISRN)
Available from: 2016-05-23 Created: 2016-05-23 Last updated: 2016-09-28Bibliographically approved
Holmberg, K. (2016). The (Over) Zealous Snow Remover Problem. Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>The (Over) Zealous Snow Remover Problem
2016 (English)Report (Other academic)
Abstract [en]

Planning snow removal is a difficult, infrequently occurring optimization problem, concerning complicated routing of vehicles. Clearing a street includes several different activities, and the tours must be allowed to contain subtours. The streets are classified into different types, each type requiring different activities. We address the problem facing a single vehicle, including details such as precedence requirements and turning penalties. We describe a solution approach based on a reformulation to an asymmetric traveling salesman problem in an extended graph, plus a heuristic for finding feasible solutions. The method have been implemented and tested on real life examples, and the solution times are short enough to allow online usage. We compare two different principles for the number of sweeps on a normal street, encountered in discussions with snow removal contractors. A principle using a first sweep in the middle of the street around the block, in order to quickly allow usage of the streets, is found to yield interesting theoretical and practical difficulties.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2016. p. 33
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2016:04
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-127028 (URN)LiTH-MAT-R--2016/04--SE (ISRN)
Available from: 2016-04-13 Created: 2016-04-13 Last updated: 2016-11-24Bibliographically approved
Holmberg, K. (2015). Computational Results for Map Matching by Optimization. Linköping University Electronic Press
Open this publication in new window or tab >>Computational Results for Map Matching by Optimization
2015 (English)Report (Other academic)
Abstract [en]

The problem of map matching appears when evaluating GPS-tracks recorded by service vehicles, and is used to associate the sequences of GPS-points to links in a graph. Difficulties are errors in the GPS-coordinates and possible lack of GPS-points on short street segments. This paper reports computational tests on integer programming models for the problem, and on several heuristic methods, based on shortest paths and rural postman problems. We present extensive computational results for several methods and for both artificial and real life test cases.

Place, publisher, year, edition, pages
Linköping University Electronic Press, 2015. p. 104
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2015:02
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-113945 (URN)LiTH-MAT-R--2015/02--SE (ISRN)
Available from: 2015-02-03 Created: 2015-02-03 Last updated: 2015-02-03
Holmberg, K. (2015). Heuristics for the weighted k-Chinese/rural postman problem with a hint of fixed costs with applications to urban snow removal. Linköping University Electronic Press
Open this publication in new window or tab >>Heuristics for the weighted k-Chinese/rural postman problem with a hint of fixed costs with applications to urban snow removal
2015 (English)Report (Other academic)
Abstract [en]

We describe a weighted version of the k-Chinese or k-rural postman problem that occurs in the context of snow removal. The problem concerns the questions of which vehicle shall do each task and how the vehicles shall travel between tasks. We also consider different numbers of vehicles, in view of a fixed cost for each vehicle. We describe and discuss heuristic solution approaches, based on usable substructures, such as Chinese/rural postman problems, meta-heuristics, k-means clustering and local search improvements by moving cycles. The methods have been implemented and tested on real life examples.

Place, publisher, year, edition, pages
Linköping University Electronic Press, 2015. p. 113
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2015:13
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-122168 (URN)LiTH-MAT-R--2015/13--SE (ISRN)
Available from: 2015-10-23 Created: 2015-10-23 Last updated: 2015-10-23Bibliographically approved
Holmberg, K. (2015). Map Matching by Optimization. Linköping University Electronic Press
Open this publication in new window or tab >>Map Matching by Optimization
2015 (English)Report (Other academic)
Abstract [en]

The problem of map matching appears when evaluating GPS-tracks recorded by service vehicles, and utilizing GPS-information in graphs suitable for route optimization. The task is to associate sequences of GPS-points to links in a graph, suitable for optimization, and thereby obtain paths or tours in the graph. Difficulties are errors in the GPS-coordinates and possible lack of GPS-points on short street segments. We apply mathematical modeling to the problem, in the form of integer programming, and do computational tests of the solvability of the models. In addition to integer programming, we develop several heuristic methods for off-line solution of this problem, based on heuristics, shortest paths and rural postman problems. All methods are computationally tested, and summarized results are reported.

Place, publisher, year, edition, pages
Linköping University Electronic Press, 2015. p. 74
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2015:01
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-113944 (URN)LiTH-MAT-R--2015/01--SE (ISRN)
Available from: 2015-02-03 Created: 2015-02-03 Last updated: 2015-02-03
Holmberg, K. (2015). On Using OpenStreetMap and GPS for Optimization. Linköping University Electronic Press
Open this publication in new window or tab >>On Using OpenStreetMap and GPS for Optimization
2015 (English)Report (Other academic)
Abstract [en]

Data from OpenStreetMap can be a valuable tool in route optimization of many kinds. With GPS data, analyses of trips can be made. In this paper, we discuss how to extract such data and transform it into forms that are useful for optimization purposes. We also discuss obtaining coordinates from such data. Sets of test problems, for future use, are presented and extracted.

Place, publisher, year, edition, pages
Linköping University Electronic Press, 2015. p. 35
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2015:15
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-122509 (URN)LiTH-MAT-R--2015/15--SE (ISRN)
Available from: 2015-11-06 Created: 2015-11-06 Last updated: 2015-11-06Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-5907-0087

Search in DiVA

Show all publications