Special issue on: Computational discrete optimization
- PDF / 188,771 Bytes
- 3 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 179 Views
Special issue on: Computational discrete optimization Arie M. C. A. Koster1 · Clemens Thielen2 Accepted: 16 September 2020 / Published online: 21 October 2020 © The Author(s) 2020
Mathematics Subject Classification 90-08 · 90C10 · 90C27 In a world where decisions are made on the basis of ever-growing amounts of available data, computational efficiency is a key property of almost every modern optimization algorithm. As many optimization problems are NP-hard, computationally efficient algorithms cannot be expected in the general context. The development of algorithms that nevertheless perform good in practice (with respect to solution time and quality) is an important corner stone of the success of operations research methods in the last decades. These algorithms can be either problem-specific or general-purpose like branch and cut for (mixed) integer linear programming. Accordingly, a high number of contributions at the 30th European Conference on Operational Research (EURO 2019) that took place in Dublin in June 2019 consider algorithm improvements and novel algorithms for the efficient (exact or heuristic) solution of optimization problems. This, in particular, holds for the streams on Mixed Integer Programming and Algorithms on Graphs. The aim of this special issue has been to highlight some of these high-quality contributions. Both theoretical and more applied manuscripts were welcome, provided the computational contribution was significant. Submissions were, however, not restricted to contributions from these streams or even from the conference. In total, we received eight submissions for this special issue. Six of these submissions have been accepted to be published in this issue of EURO Journal on Computational Optimization. In the following, we briefly highlight the novelty of these articles:
B
Arie M. C. A. Koster [email protected] Clemens Thielen [email protected]
1
Lehrstuhl II für Mathematik, RWTH Aachen University, Pontdriesch 10–12, 52062 Aachen, Germany
2
TUM Campus Straubing for Biotechnology and Sustainability, Weihenstephan-Triesdorf University of Applied Sciences, Am Essigberg 3, 94315 Straubing, Germany
123
202
A. M. C. A. Koster, C. Thielen
– As many discrete optimization problems can be modeled as mixed integer linear programs (MILPs), improving the performance of MILP solvers instantly increases the solvability for a multitude of optimization problems. Besides branch and bound, cutting planes, and primal heuristics, presolve techniques have a significant impact on MILP solver performance. In Gemander et al. (2020), Gemander et al. consider a new hashing-based pairing mechanism to consider two rows or columns simultaneously. By this, formulations can be strengthened further and the solution times of larger instances can be decreased. – Another aspect that negatively impacts the performance of MILP solvers is dual degeneracy, i.e., the presence of multiple optimal bases in linear programs. This issue has been rarely studied so far. Gamrath et al. (2020) study the presenc
Data Loading...
