@article{BestuzhevaHijaziCoffrin2019, author = {Bestuzheva, Ksenia and Hijazi, Hassan and Coffrin, Carleton}, title = {Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching}, volume = {32}, journal = {INFORMS Journal on Computing}, number = {3}, publisher = {INFORMS Institute for Operations Research and the Management Sciences}, address = {5521 Research Park Drive, Suite 200, Catonsville, MD 21228 USA}, doi = {https://doi.org/10.1287/ijoc.2019.0900}, pages = {682 -- 696}, year = {2019}, abstract = {This paper studies mixed-integer nonlinear programs featuring disjunctive constraints and trigonometric functions and presents a strengthened version of the Convex Quadratic relaxation of the Optimal Transmission Switching problem. We first characterize the convex hull of univariate quadratic on/off constraints in the space of original variables using perspective functions. We then introduce new tight quadratic relaxations for trigonometric functions featuring variables with asymmetrical bounds. These results are used to further tighten recent convex relaxations introduced for the Optimal Transmission Switching problem in Power Systems. Using the proposed improvements, along with bound propagation, on 23 medium-size test cases in the PGLib benchmark library with a relaxation gap of more than 1\%, we reduce the gap to less than 1\% on 5 instances. The tightened model has promising computational results when compared to state-of-the-art formulations.}, language = {en} } @inproceedings{AndersonHendelLeBodicetal.2018, author = {Anderson, Daniel and Hendel, Gregor and Le Bodic, Pierre and Viernickel, Jan Merlin}, title = {Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation}, booktitle = {AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence}, year = {2018}, abstract = {We propose a simple and general online method to measure the search progress within the branch-and-bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.}, language = {de} } @inproceedings{GleixnerSteffy2019, author = {Gleixner, Ambros and Steffy, Daniel}, title = {Linear Programming using Limited-Precision Oracles}, booktitle = {A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019}, doi = {10.1007/978-3-030-17953-3_30}, pages = {399 -- 412}, year = {2019}, abstract = {Linear programming is a foundational tool for many aspects of integer and combinatorial optimization. This work studies the complexity of solving linear programs exactly over the rational numbers through use of an oracle capable of returning limited-precision LP solutions. It is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. Previous work has often considered oracles that provide solutions of an arbitrary specified precision. While this leads to polynomial-time algorithms, the level of precision required is often unrealistic for practical computation. In contrast, our work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.}, language = {en} } @inproceedings{Serrano2019, author = {Serrano, Felipe}, title = {Intersection cuts for factorable MINLP}, volume = {11480}, booktitle = {A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019}, doi = {10.1007/978-3-030-17953-3_29}, pages = {385 -- 398}, year = {2019}, abstract = {Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.}, language = {en} } @article{GamrathBertholdHeinzetal.2019, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-driven fix-and-propagate heuristics for mixed integer programming}, volume = {11}, journal = {Mathematical Programming Computation}, number = {4}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {10.1007/s12532-019-00159-1}, pages = {675 -- 702}, year = {2019}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60 \% of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.}, language = {en} } @misc{Wyczik2018, type = {Master Thesis}, author = {Wyczik, Christopher}, title = {Optimierung von Deployment- und Umgebungs-Integrit{\"a}t durch ein dezentrales Konfigurationsrepository auf Basis einer Blockchain}, pages = {44}, year = {2018}, abstract = {Viele Firmen nutzen f{\"u}r ihre eigenen Softwareentwicklungen verschiedene Server mit unterschiedlichen Konfigurationen. Manche Server werden dazu eingestzt das Verhalten einer Software in einer bestimmten Umgebung zu testen und andere dienen zur Bereitstellung der Software f{\"u}r den Endnutzer. Hierbei ist es wichtig, dass die Konfiguration der Server regelm{\"a}ßig {\"u}berpr{\"u}ft wird. Eine solche Sicherstellung der Deployment- und Umgebungs-Integrit{\"a}t wird meistens durch eine Mitarbeiter der Firma oder durch einen externen Dienstleister erbracht. D.h. die Firma muss sich auf die Zuverl{\"a}ssigkeit eines Mitarbeiters oder einer externen Dienstleistung verlassen, bie zunehmender Komplexit{\"a}t ist sie sogar abh{\"a}ngig. Das Ziel dieser Masterarbeit ist es, zu untersuchen, ob die Sicherstellung der Deployment- und Umgebungs-Integrit{\"a}t durch automatisierte kryptografische Beweise, anstelle externer Dienstleistungen oder anderer Mitarbeiter, gew{\"a}hrleistet werden kann. Als Anwendungsfall dient die Toll Collect GmbH. Im ersten Teil dieser Arbeit wird das Matheamtische Modell einer Blockchain erl{\"a}utert. die Blockchain wurde erstmals in einem Dokument, welches unter dem Pseudonym Satoshi Nakamoto ver{\"o}ffentlicht wurde, beschrieben. Die erste große Anwendungen der Blockchain ist das dezentrale Zahlungssystem Bitcoin. Im zweiten Teil dieser Arbeit wird die Softwareimplementierung vorgestellt, welche im Rahmen dieser Arbeit entstanden ist. Mithilfe dieses Programms kann die Deployment- und Umgebungs-Integrit{\"a}t durch eine heirf{\"u}hr entwickelte Blockchainl{\"o}sung dezentralisiert werden. Es wird außerdem der {\"U}bergang vom Mathematischen Modell zur Implementierung gezeigt.}, language = {de} } @article{WitzigGleixner2020, author = {Witzig, Jakob and Gleixner, Ambros}, title = {Conflict-Driven Heuristics for Mixed Integer Programming}, volume = {33}, journal = {INFORMS Journal on Computing}, number = {2}, doi = {10.1287/ijoc.2020.0973}, pages = {706 -- 720}, year = {2020}, abstract = {Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.}, language = {en} } @article{GleixnerHendelGamrathetal.2021, author = {Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp M. and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and L{\"u}bbecke, Marco and Mittelmann, Hans and Ozyurt, Derya and Ralphs, Ted and Salvagnin, Domenico and Shinano, Yuji}, title = {MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, year = {2021}, abstract = {We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.}, language = {en} } @inproceedings{SerranoMuñoz2020, author = {Serrano, Felipe and Muñoz, Gonzalo}, title = {Maximal Quadratic-Free Sets}, booktitle = {Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020}, doi = {10.1007/978-3-030-45771-6_24}, pages = {307 -- 321}, year = {2020}, abstract = {The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we show how to construct maximal S-free sets when S is defined as a general quadratic inequality. Our maximal S-free sets are such that efficient separation of a vertex in LP-based approaches to quadratically constrained problems is guaranteed. To the best of our knowledge, this work is the first to provide maximal quadratic-free sets.}, language = {en} } @article{SunRehfeldtBraziletal.2020, author = {Sun, Yahui and Rehfeldt, Daniel and Brazil, Marcus and Thomas, Doreen and Halgamuge, Saman}, title = {A Physarum-Inspired Algorithm for Minimum-Cost Relay Node Placement in Wireless Sensor Networks}, journal = {IEEE/ACM Transactions on Networking}, doi = {10.1109/TNET.2020.2971770}, year = {2020}, language = {en} } @article{ShinanoAchterbergBertholdetal.2013, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Vigerske, Stefan and Winkler, Michael}, title = {制約整数計画ソルバ SCIP の並列化}, volume = {61}, journal = {統計数理}, number = {1}, pages = {47 -- 78}, year = {2013}, abstract = {制約整数計画(CIP: Constraint Integer Programs)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming),充足可能性問題(SAT: Satisfability Problem)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP(Solving Constraint Integer Programs)は,CIP を解くソルバとして実装され,Zuse Institute Berlin(ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発された SCIP に対する2 種類の並列化拡張を紹介する.一つは,複数計算ノード間で大規模に並列動作する ParaSCIPである.もう一つは,複数コアと共有メモリを持つ 1 台の計算機上で(スレッド)並列で動作する FiberSCIP である.ParaSCIP は,HLRN II スーパーコンピュータ上で,一つのインスタンスを解くために最大 7,168 コアを利用した動作実績がある.また,統計数理研究所の Fujitsu PRIMERGY RX200S5 上でも,最大 512 コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5 上では,これまでに最適解が得られていなかった MIPLIB2010のインスタンスである dg012142 に最適解を与えた.}, language = {ja} } @inproceedings{CaoGleixnerMiltenberger2016, author = {Cao, Karl-Ki{\^e}n and Gleixner, Ambros and Miltenberger, Matthias}, title = {Methoden zur Reduktion der Rechenzeit linearer Optimierungsmodelle in der Energiewirtschaft - Eine Performance-Analyse}, booktitle = {EnInnov 2016: 14. Symposium Energieinnovation 2016}, year = {2016}, abstract = {Dieser Beitrag stellt m{\"o}gliche Ans{\"a}tze zur Reduktion der Rechenzeit von linearen Optimierungsproblemen mit energiewirtschaftlichem Anwendungshintergrund vor. Diese Ans{\"a}tze bilden im Allgemeinen die Grundlage f{\"u}r konzeptionelle Strategien zur Beschleunigung von Energiesystemmodellen. Zu den einfachsten Beschleunigungsstrategien z{\"a}hlt die Verkleinerung der Modelldimensionen, was beispielsweise durch {\"A}ndern der zeitlichen, r{\"a}umlichen oder technologischen Aufl{\"o}sung eines Energiesystemmodells erreicht werden kann. Diese Strategien sind zwar h{\"a}ufig ein Teil der Methodik in der Energiesystemanalyse, systematische Benchmarks zur Bewertung ihrer Effektivit{\"a}t werden jedoch meist nicht durchgef{\"u}hrt. Die vorliegende Arbeit adressiert genau diesen Sachverhalt. Hierzu werden Modellinstanzen des Modells REMix in verschiedenen Gr{\"o}ßenordnungen mittels einer Performance-Benchmark-Analyse untersucht. Die Ergebnisse legen zum einen den Schluss nahe, dass verk{\"u}rzte Betrachtungszeitr{\"a}ume das gr{\"o}ßte Potential unter den hier analysierten Strategien zur Reduktion von Rechenzeit bieten. Zum anderen empfiehlt sich die Verwendung des Barrier-L{\"o}sungsverfahrens mit multiplen Threads unter Vernachl{\"a}ssigung des Cross-Over.}, language = {de} } @inproceedings{D'AndreagiovanniGleixner2016, author = {D'Andreagiovanni, Fabio and Gleixner, Ambros}, title = {Towards an accurate solution of wireless network design problems}, booktitle = {Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016}, doi = {10.1007/978-3-319-45587-7_12}, pages = {135 -- 147}, year = {2016}, abstract = {The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models.}, language = {en} } @inproceedings{DevriendtGleixnerNordstroem2020, author = {Devriendt, Jo and Gleixner, Ambros and Nordstr{\"o}m, Jakob}, title = {Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search}, volume = {12296}, booktitle = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020}, publisher = {Springer}, pages = {xxiv -- xxvi}, year = {2020}, abstract = {Conflict-driven Pseudo-Boolean (PB) solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though PB solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear program (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven PB search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis over linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best of two worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut.}, language = {en} } @article{品野2014, author = {品野, 勇治}, title = {最適化研究における数値実験を中心とした アプリケーション駆動研究サイクル}, volume = {59}, journal = {機関誌「オペレーションズ・リサーチ」}, number = {5}, pages = {247 -- 253}, year = {2014}, abstract = {最適化研究におけるアプリケーション駆動研究サイクルを紹介する.アプリケーション駆動研究サイクルは,学術機関での研究と企業における研究成果の利用とのつながりを良くする点では優れている.一方で,ソフトウェア開発・維持に多大な労力を要するため,日本の大学や研究機関における実施には困難さが伴う.ZIBにおいてアプリケーション駆動研究サイクルが,比較的うまく機能している背景を説明する.また,日本においてアプリケーション駆動研究サイクルを活性化するための第一歩として,論文投稿時に,論文中の数値実験に利用した全データ提出の義務化を提案したい.}, language = {ja} } @article{藤澤品野2014, author = {藤澤, 克樹 and 品野, 勇治}, title = {最適化と計算の今後 ―大規模問題をどこまで解決できるのか?―}, volume = {59}, journal = {機関誌「オペレーションズ・リサーチ」}, number = {1}, pages = {11 -- 19}, year = {2014}, abstract = {近年,大規模かつ複雑な最適化問題を高速に解く需要はさまざまな産業界や学術分野において急速に高まりつつある.これからの研究においては最先端理論 (Theory)+超大規模実データ (Practice)+最新計算技術(Computation) の三つを有機的に組み合わせることによって,実用に耐えうる解決策の提示と大規模最適化問題を扱う際の先例となることが求められている.本稿では最適化と計算に関する最新の傾向に触れるとともに,最適化の計算の今後についても考えていきたい.}, language = {ja} } @article{RehfeldtKochShinano2023, author = {Rehfeldt, Daniel and Koch, Thorsten and Shinano, Yuji}, title = {Faster exact solution of sparse MaxCut and QUBO problems}, volume = {15}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-023-00236-6}, pages = {445 -- 470}, year = {2023}, abstract = {The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.}, language = {en} } @inproceedings{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, booktitle = {OR 2018: International Conference on Operations Research}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances.}, language = {en} } @misc{OPUS4-8937, title = {データ格付けサービス実現のための数理基盤の構築}, volume = {91}, editor = {Fujisawa, Katsuki and Kaji, Shizuo and Ishihara, Toru and Kondo, Masaaki and Shinano, Yuji and Tanigawa, Takuji and Nakayama, Naoko}, publisher = {Institute of Mathematics for Industry, Kyushu University}, address = {Graduate School of Mathematics, Kyushu University Motooka 744, Nishi-ku, Fukuoka, 819-0395, JAPAN}, issn = {2188-1200}, year = {2022}, language = {ja} } @misc{OPUS4-8935, title = {Construction of Mathematical Basis for Realizing Data Rating Service}, volume = {90}, editor = {Fujisawa, Katsuki and Kaji, Shizuo and Ishihara, Toru and Kondo, Masaaki and Shinano, Yuji and Tanigawa, Takuji and Nakayama, Naoko}, publisher = {Institute of Mathematics for Industry, Kyushu University}, address = {Graduate School of Mathematics, Kyushu University Motooka 744, Nishi-ku, Fukuoka, 819-0395, JAPAN}, issn = {2188-1200}, year = {2022}, language = {en} }